flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) (06/01/89)
I need an algorithm to fit a set of data points, obtained experimentally, to the best-fit circle. I have searched through many book son least squares anaylsis, but can only find simple cases. I started to do the math, but it became rather involved very quickly. I would appreciate it if i can get code to do this, or perhaps leads as to where I can continue looking. Thanks in advance.... -- Stephen Corbesero flash@lehi3b15.UUCP VLSI Design Automation Lab flash@lehi3b15.CSEE.Lehigh.EDU Computer Science And Electrical Engineering, usgcorb@vax1.CC.Lehigh.EDU Lehigh University, Bethlehem, PA 18015
flowers@osf.OSF.ORG (Ken Flowers) (06/02/89)
In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: > >I need an algorithm to fit a set of data points, obtained >experimentally, to the best-fit circle. I have searched through many >book son least squares anaylsis, but can only find simple cases. I >started to do the math, but it became rather involved very quickly. > >I would appreciate it if i can get code to do this, or perhaps leads >as to where I can continue looking. > >Thanks in advance.... > >-- >Stephen Corbesero flash@lehi3b15.UUCP >VLSI Design Automation Lab flash@lehi3b15.CSEE.Lehigh.EDU >Computer Science And Electrical Engineering, usgcorb@vax1.CC.Lehigh.EDU >Lehigh University, Bethlehem, PA 18015 Not being a mathmatician, (but I did start a math major at MIT. Finally went on to MechE.) please excuse any level of ignorance. It seems to me that the best fit circle can be simply found by doing the following: 1. Make the center the average point of all the data points. 2. Make the radius the average distance from the center to each data point. This gives also the smallest best fit circle, because as we can see from the two point generalization that an infinate number of circles can fit exactly. Also, if we take a radius significantly larger than the range of the data and then place the data around a small segment of the resulting circle, that seems like a preaty damn good fit also. What it turns out were doing in this case, if we make the radius suffiently large, is creating the best fit line.
flynn@pixel.cps.msu.edu (Patrick J. Flynn) (06/02/89)
In article <1088@osf.OSF.ORG> flowers@osf.org (Ken Flowers) writes: >In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: >> >>I need an algorithm to fit a set of data points, obtained >>experimentally, to the best-fit circle. I have searched through many >>book son least squares anaylsis, but can only find simple cases. I >>started to do the math, but it became rather involved very quickly. >> >It seems to me that the best fit circle can be simply found by doing >the following: > > 1. Make the center the average point of all the data points. > > 2. Make the radius the average distance from the center to each > data point. Unfortunately, if the points are not distributed uniformly along the *entire* circumference, you'll get a biased estimate of the location of the center. A least-squares error criterion to the problem is nonlinear in the `geometric' parameters of the circle (center coordinates and radius), but if you're willing to use iterative techniques, you can get a solution. Minimize f^2(x,y;x0,y0,r) with respect to (x0,y0) and r, where f(x,y;x0,y0,r) = (x-x0)^2 + (y-y0)^2 - r^2 I've used the Levenberg-Marquardt method to solve related problems in the past (you have to watch out for local minima, though). A second approach which avoids the nonlinear stuff: Start choosing triples of points from your point set. Find the circle passing through those points; save the estimates of the center and radius. Then average the estimates. If the points are not very noisy, that might do; otherwise, you might want to trim those estimates. When choosing triples, be careful to choose points which aren't too close together. ------------------------------------------------------------------------------ Pat Flynn, CS, Mich. State U | "Don't eat with your hands, son; use your flynn@cps.msu.edu | entrenching tool." (517) 353-4638 | -Firesign Theatre
toms@ncifcrf.gov (Tom Schneider) (06/02/89)
In article <1088@osf.OSF.ORG> flowers@osf.org (Ken Flowers) writes: >In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: >> >>I need an algorithm to fit a set of data points, obtained >>experimentally, to the best-fit circle. I have searched through many >>book son least squares anaylsis, but can only find simple cases. I >>started to do the math, but it became rather involved very quickly. >> >>Stephen Corbesero flash@lehi3b15.UUCP >>VLSI Design Automation Lab flash@lehi3b15.CSEE.Lehigh.EDU >>Computer Science And Electrical Engineering, usgcorb@vax1.CC.Lehigh.EDU >>Lehigh University, Bethlehem, PA 18015 > 1. Make the center the average point of all the data points. > 2. Make the radius the average distance from the center to each data point. That was my first thought also. But suppose that all of the data points lie on one side of the circle, or are confined to a small angular region. Then this method will fail because it will place the center much to close to the circle. If Stephen knows that the points are pretty well spread around then this method should be pretty good, but it wouldn't be as good as a true least squares fit. Seems to me that should be possible, where one is determining the minimum square radial distance from each point to the circle along radii. (Also an MIT grad, but in biology!) Tom Schneider National Cancer Institute Laboratory of Mathematical Biology Frederick, Maryland 21701-1013 toms@ncifcrf.gov
roy@phri.UUCP (Roy Smith) (06/02/89)
flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: > I need an algorithm to fit a set of data points, obtained > experimentally, to the best-fit circle. There was an article about finding the smallest circle which just encloses a set of points on a plane recently on the net which might be of some interest to you. It appeared in rec.humor.funny. Had something to do with sheep. -- Roy Smith, Public Health Research Institute 455 First Avenue, New York, NY 10016 {allegra,philabs,cmcl2,rutgers,hombre}!phri!roy -or- roy@alanine.phri.nyu.edu "The connector is the network"
bill@ut-emx.UUCP (Bill Jefferys) (06/02/89)
In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes:
#
#I need an algorithm to fit a set of data points, obtained
#experimentally, to the best-fit circle. I have searched through many
#book son least squares anaylsis, but can only find simple cases. I
#started to do the math, but it became rather involved very quickly.
Look in Wayne A. Fuller's _Measurement Error Models_, Chapter 3
(esp. Section 3.2). Published by Wiley, 1987.
Warning: This is not easy going.
Bill Jefferys
#
#I would appreciate it if i can get code to do this, or perhaps leads
#as to where I can continue looking.
#
#Thanks in advance....
#
#--
#Stephen Corbesero flash@lehi3b15.UUCP
#VLSI Design Automation Lab flash@lehi3b15.CSEE.Lehigh.EDU
#Computer Science And Electrical Engineering, usgcorb@vax1.CC.Lehigh.EDU
#Lehigh University, Bethlehem, PA 18015ted@nmsu.edu (Ted Dunning) (06/03/89)
interestingly, while the coordinates of the center of the best fit circle involves a non-linear solution, if you are given the center, then the best fit radius is the root mean square of the distances from the center. using this fact will make a non-linear optimization program for finding the best fit circle converge much more rapidly.
pfenniger@obs.unige.ch (06/08/89)
In article <573@lehi3b15.csee.Lehigh.EDU>, flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: > I need an algorithm to fit a set of data points, obtained > experimentally, to the best-fit circle. I have searched through many > book son least squares anaylsis, but can only find simple cases. I > started to do the math, but it became rather involved very quickly. > The problem can be stated as follow : You have a set of points in cartesian coordinates {Xi, Yi} i = 1, ..., n (n>2). You want to fit to these points in a least square sense the quadratic form of a circle of unknown radius R and center {X0, Y0} : f(X,Y) = (X - X0)^2 + (Y - Y0)^2 - R^2 = a X + b Y + c + X^2 + Y^2 , where a = -2 X0, b = -2 Y0, c = X0^2 + Y0^2 - R^2. In matrix form the problem is to find Z which minimizes the euclidian norm : || A Z - B || where [ a ] Z = [ b ] [ c ] and [ X1 Y1 1 ] [ X1^2 + Y1^2 ] A = [ X2 Y2 1 ] , B = -[ X2^2 + Y2^2 ] . ....... ........... [ Xn Yn 1 ] [ Xn^2 + Yn^2 ] The problem is therefore suited to *linear* least squares, since the unknowns a, b, c in Z enter in a linear way. Then use any modern linear least squares algorithm (e.g. HFTI in Lawson & Hanson, 1974, "Solving Least Squares Problems", Prentice-Hall, NJ ; or Linpack etc.) which just finds this minimum euclidian norm by orthogonal decomposition. This approach is superior to the traditional inversion of a square normal matrix. Note that fitting ellipses or more complicated forms would use essentially the same method, since the additional unknown parameters are also linear. Daniel Pfenniger
wjmartiniii@violet.waterloo.edu (Bill Martin) (06/09/89)
In article <1088@osf.OSF.ORG> flowers@osf.org (Ken Flowers) writes: >In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes: >> >>I need an algorithm to fit a set of data points, obtained >>experimentally, to the best-fit circle. I have searched through many >>-- >It seems to me that the best fit circle can be simply found by doing >the following: > > 1. Make the center the average point of all the data points. > > 2. Make the radius the average distance from the center to each > data point. > With regard to the above approach, consider a large number of points lying on a line. The given algorithm would choose a point on that line as the center of the circle. This is certainly not optimal in general.