# Find a circle center with spatial points

9 messages
Open this post in threaded view
|

## Find a circle center with spatial points

Dear all,

I need some advices for a problem I have on R.
So, I have points with latitude and longitude. These points seem to be part of a circle, and I need to determine the center of this circle (automatically). So, if you have an idea of the methods for it, It would be great,

Thank you,

ps: you can see an exemple of points here.

 Cet e-mail a été envoyé depuis un ordinateur protégé par Avast. www.avast.com

_______________________________________________
R-sig-Geo mailing list
[hidden email]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 library(rgeos) gCentroid http://www.rdocumentation.org/packages/rgeos/functions/topo-unary-gCentroidAssuming its a circle that would be the center. Then you need to decide how much of a difference between that and your existing point is acceptable to still call them the same point. Enjoy, Alex On 03/18/2016 02:12 AM, Adrien Inacio wrote: > Dear all, > > I need some advices for a problem I have on R. > So, I have points with latitude and longitude. These points seem to be part > of a circle, and I need to determine the center of this circle > (automatically). So, if you have an idea of the methods for it, It would be > great, > > Thank you, > Adrien I. > > ps: you can see an exemple of points here. > > [image: Images intégrées 1] > > > Cet e-mail a été envoyé depuis un ordinateur protégé par Avast. > www.avast.com > > <#-7691127820984744905_DDB4FAA8-2DD7-40BB-A1B8-4E2AA1F9FDF2> > > > > _______________________________________________ > R-sig-Geo mailing list > [hidden email] > https://stat.ethz.ch/mailman/listinfo/r-sig-geo> _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 On Fri, Mar 18, 2016 at 2:43 PM, Alex Mandel <[hidden email]> wrote: > library(rgeos) > gCentroid > > http://www.rdocumentation.org/packages/rgeos/functions/topo-unary-gCentroid> > Assuming its a circle that would be the center. Only if you have points uniformly (or uniform-randomly) distributed round the full extent of the circle. From Adrien's plot it looks like he's got an arc there.  It seems more like a three-parameter optimisation problem. Find x, y, and r that define the circle that minimises the sum of squared distances from data points to the circle.  I'm not sure how you'd choose a good initial x,y,r for your optimiser since I suspect the surface you're optimising over is not unimodal... You could try taking lots of random samples of three points from your data and computing the unique circle that fits those points, then using the mean (or possibly median, there's a fair chance of massive outliers) value as the initial values. A quick googling has actually found this little paper on the subject: http://www.spaceroots.org/documents/circle/circle-fitting.pdfSo I'll shut up now. Barry _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 Because it seems to be an arc and not a circle issue that you can solve the problem by picking arbitrary two points of your assumed "arc" then construct (calculate)  the perpendicular bisector of the line between them and do so for another arbitrary two points of the assumed "arc". The intersection of the perpendicular lines is the assumed center of the arc. If you iterate over all points this should be a pretty good estimation of the real center. cheers Chris Am 18.03.2016 um 18:36 schrieb Barry Rowlingson: > On Fri, Mar 18, 2016 at 2:43 PM, Alex Mandel <[hidden email]> wrote: >> library(rgeos) >> gCentroid >> >> http://www.rdocumentation.org/packages/rgeos/functions/topo-unary-gCentroid>> >> Assuming its a circle that would be the center. > Only if you have points uniformly (or uniform-randomly) distributed > round the full extent of the circle. From Adrien's plot it looks like > he's got an arc there. > >   It seems more like a three-parameter optimisation problem. Find x, y, > and r that define the circle that minimises the sum of squared > distances from data points to the circle. > >   I'm not sure how you'd choose a good initial x,y,r for your optimiser > since I suspect the surface you're optimising over is not unimodal... > You could try taking lots of random samples of three points from your > data and computing the unique circle that fits those points, then > using the mean (or possibly median, there's a fair chance of massive > outliers) value as the initial values. > > A quick googling has actually found this little paper on the subject: > > http://www.spaceroots.org/documents/circle/circle-fitting.pdf> > So I'll shut up now. > > Barry > > _______________________________________________ > R-sig-Geo mailing list > [hidden email] > https://stat.ethz.ch/mailman/listinfo/r-sig-geo> _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 On Fri, Mar 18, 2016 at 6:49 PM, Chris Reudenbach <[hidden email]> wrote: > Because it seems to be an arc and not a circle issue that you can solve the > problem by > picking arbitrary two points of your assumed "arc" then construct > (calculate)  the perpendicular bisector of > the line between them and do so for another arbitrary two points of the > assumed "arc". > > The intersection of the perpendicular lines is the assumed center of the > arc. > > If you iterate over all points this should be a pretty good estimation of > the real center.  This is the  "sample 3 points and find the fitted circle" idea, you are likely to get massive "outliers" and if you take the mean coordinate it could fail horribly. See the paper I linked to for an example. They use the median to get an initial "robust" estimate of x,y,R, and then use some specialised optimisation to improve the estimate - you can't just throw it into "optim"!  Not sure I understand the maths in it yet though.... Barry _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 Oops :-[ , Barry thanks for clarification , I got it now. I don't understand the math either but as a kind of "reparation" for not reading well enough I found the authors java code. https://www.spaceroots.org/documents/circle/CircleFitter.javaAfter download you should for standalone compilation delete line 37 "package org.spaceroots;" compile it with:   javac CircleFitter.java -Xlint:unchecked then you can run it with: java CircleFitter input.file The input data should be formated like: # input # x y 0 5 1 4.5 2.5 4 3 3.5 4 2 5 0 the above input yields initial circle: -001.69467803 -000.69446643 006.23578103 converged after 7 iterations final circle: -001.34339845 -001.34426151 006.44308386 with the format x,y,radius which at least make sense with respect to the data. You easily can  run it from R by system() and grab the output in a file using a OS depending pipe or you may run it using the rJava package which could be more complex. cheers Chris if you want you can call it from R with javaR Am 18.03.2016 um 20:11 schrieb Barry Rowlingson: > On Fri, Mar 18, 2016 at 6:49 PM, Chris Reudenbach > <[hidden email]> wrote: >> Because it seems to be an arc and not a circle issue that you can solve the >> problem by >> picking arbitrary two points of your assumed "arc" then construct >> (calculate)  the perpendicular bisector of >> the line between them and do so for another arbitrary two points of the >> assumed "arc". >> >> The intersection of the perpendicular lines is the assumed center of the >> arc. >> >> If you iterate over all points this should be a pretty good estimation of >> the real center. >   This is the  "sample 3 points and find the fitted circle" idea, you > are likely to get massive "outliers" and if you take the mean > coordinate it could fail horribly. See the paper I linked to for an > example. They use the median to get an initial "robust" estimate of > x,y,R, and then use some specialised optimisation to improve the > estimate - you can't just throw it into "optim"! > >   Not sure I understand the maths in it yet though.... > > Barry > _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Open this post in threaded view
|