# Find a circle center with spatial points Classic List Threaded 9 messages Reply | Threaded
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,
Adrien I.

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
Reply | Threaded
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
Reply | Threaded
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
Reply | Threaded
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
Reply | Threaded
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
Reply | Threaded
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
Reply | Threaded
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 Here's a toy R script that fits circle parameters to noisy data, using optim: x0 = 10 y0 = 5 r = 4 n = 50 sd = .3 rad = runif(n) * 2 * pi x = x0 + r * cos(rad) + rnorm(n, sd = sd) y = y0 + r * sin(rad) + rnorm(n, sd = sd) plot(x, y, asp = 1) SSdist2circ = function(par, x, y)  {         x0 = par         y0 = par         r = par         sum(abs(sqrt((x-x0)^2+(y-y0)^2) - r)) } plotCirc = function(x0, y0, r, ...) {         sq = seq(0, 2 * pi, length.out = 100)         lines(x0 + r * cos(sq), y0 + r * sin(sq), ...) } # model: plotCirc(x0, y0, r, col = 'blue') # fitted: p = optim(c(x0 = 0, y0 = 0, r = 1), SSdist2circ, x = x, y = y) plotCirc(p\$par, p\$par, p\$par, col = 'red') On 18/03/16 23:28, Chris Reudenbach wrote: > 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.java> After 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-- Edzer Pebesma Institute for Geoinformatics  (ifgi),  University of Münster Heisenbergstraße 2, 48149 Münster, Germany; +49 251 83 33081 Journal of Statistical Software:   http://www.jstatsoft.org/Computers & Geosciences:   http://elsevier.com/locate/cageo/Spatial Statistics Society http://www.spatialstatistics.info_______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo signature.asc (501 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 And here's a package that implements that, along with finding an initial point via the 3-point sampling circle method and a function for making test data: https://github.com/barryrowlingson/circlefitter/tree/masterno documentation, of course, except the README... And no license... Edzer wrote a chunk of it... I don't think he'll mind :) the least-squares method works pretty well for fairly point data that defines the circle pretty well, but if you do points over a small arc then I've had cases where the centre is on the wrong side of the circle. I'm not sure if the optimiser has found the global minimum is over there or whether it has just missed a minimum at the true x,y,r values. But data with a large radius variance on a short arc section is hard to tell which way it is arcing... At some point I still might implement the methods in that paper... Barry On Sat, Mar 19, 2016 at 12:54 PM, Edzer Pebesma <[hidden email]> wrote: > Here's a toy R script that fits circle parameters to noisy data, using > optim: > > x0 = 10 > y0 = 5 > r = 4 > > n = 50 > sd = .3 > > rad = runif(n) * 2 * pi > x = x0 + r * cos(rad) + rnorm(n, sd = sd) > y = y0 + r * sin(rad) + rnorm(n, sd = sd) > plot(x, y, asp = 1) > > SSdist2circ = function(par, x, y)  { >         x0 = par >         y0 = par >         r = par >         sum(abs(sqrt((x-x0)^2+(y-y0)^2) - r)) > } > > > plotCirc = function(x0, y0, r, ...) { >         sq = seq(0, 2 * pi, length.out = 100) >         lines(x0 + r * cos(sq), y0 + r * sin(sq), ...) > } > > # model: > plotCirc(x0, y0, r, col = 'blue') > # fitted: > p = optim(c(x0 = 0, y0 = 0, r = 1), SSdist2circ, x = x, y = y) > plotCirc(p\$par, p\$par, p\$par, col = 'red') > > > On 18/03/16 23:28, Chris Reudenbach wrote: >> 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.java>> After 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> > -- > Edzer Pebesma > Institute for Geoinformatics  (ifgi),  University of Münster > Heisenbergstraße 2, 48149 Münster, Germany; +49 251 83 33081 > Journal of Statistical Software:   http://www.jstatsoft.org/> Computers & Geosciences:   http://elsevier.com/locate/cageo/> Spatial Statistics Society http://www.spatialstatistics.info> > > _______________________________________________ > 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
Reply | Threaded
Open this post in threaded view
|

## Re: Find a circle center with spatial points

 In reply to this post by Chris Reudenbach Hello Chris, Thanks for your help, I try to find how I can use the java script but I don't really understand these parts: "After download you should for standalone compilation delete line 37 "package org.spaceroots;" compile it with: *" javac CircleFitter.java -Xlint:uncheckedthen you can run it with:java CircleFitter input.file"* *"grab the output in a file using a OS depending pipe"* Have I to download an application wich permit to work on java script, or all can be done with R (I have never work with java so i'm a little bit lost). Thank you again. Adrien I. Cet e-mail a été envoyé depuis un ordinateur protégé par Avast. www.avast.com <#DDB4FAA8-2DD7-40BB-A1B8-4E2AA1F9FDF2> 2016-03-18 23:28 GMT+01:00 Chris Reudenbach <[hidden email]>: > 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.java> After 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>         [[alternative HTML version deleted]] _______________________________________________ R-sig-Geo mailing list [hidden email] https://stat.ethz.ch/mailman/listinfo/r-sig-geo