

10212003, 08:34 PM

Senior Contributor


Join Date: May 2003
Posts: 805


Best fit algorithm for circle given points
I'm looking for a best fit algorithm to generate a circle from a set of XY points. I have used linear regression apps to fit polynomials, but can't find any VB code for circles. Or maybe someone knows of a method to use the polynomial fit to derive circles? Any help appreciated.


10212003, 10:05 PM


Code Meister
Retired Moderator * Guru *


Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441


Well.....since a circle is of the form x*x + y*y = r*r, you could try plotting x*x vs y*y and use linear regression....

__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!"  Edmund Blackadder

10212003, 10:28 PM


Ultimate Contributor
* Expert *


Join Date: Jun 2003
Location: New York, NY
Posts: 1,929


Quote: Originally Posted by waits77 I'm looking for a best fit algorithm to generate a circle from a set of XY points. I have used linear regression apps to fit polynomials, but can't find any VB code for circles. Or maybe someone knows of a method to use the polynomial fit to derive circles? Any help appreciated.
Are you talking about dawing a circle given 3 sets of (X,Y) coordinates?
This is something I was looking at a while ago, and I came up with this:
x1,y1 x2,y2 and x3,y3 are your 3 points, and x,y is the center of your circle.
r = sqr((x1x)^2+(y1y)^2) = sqr((x2x)^2+(y2y)^2) = sqr((x3x)^2+(y3y)^2)
solve for x and y and then for r and you'll have your circle.

__________________
"Fortunately, I live in the United States of America, where we are gradually coming to understand that nothing we do is ever our fault, especially if it is really stupid."  Dave Barry

10222003, 12:21 AM


Code Meister
Retired Moderator * Guru *


Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441


Blindwig: What you have is how to determine a circle when you have 3 points guaranteed to lie on the circumference.
What waits77 wants, I think, is how to determine the best circle given a number of points (more than 3) that may or may not lie on the circumference.

__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!"  Edmund Blackadder

10222003, 03:27 AM

Senior Contributor


Join Date: May 2003
Posts: 805


BillSoo is correct. I can calculate a circle through three points using straight formulas. Examples can be found at MathHelp. What I want to do is best fit a circle to a set of 4 or more points.
BillSoo, I don't know how to write my own linear regression algorithm to determine X, Y and R. I could come up with a simple (meaning slow) routine to do a straight least squares fit with no optimization, but I'll be fitting thousands of circles in a single run.


10222003, 12:25 PM


Ultimate Contributor
* Expert *


Join Date: Jun 2003
Location: New York, NY
Posts: 1,929


Quote: Originally Posted by waits77 BillSoo is correct. I can calculate a circle through three points using straight formulas. Examples can be found at MathHelp. What I want to do is best fit a circle to a set of 4 or more points.
BillSoo, I don't know how to write my own linear regression algorithm to determine X, Y and R. I could come up with a simple (meaning slow) routine to do a straight least squares fit with no optimization, but I'll be fitting thousands of circles in a single run.
Hmm, well I'm not a math expert, so I'll just say one more thing and then I'll leave it to you two. Here's how I might do it:
If I have a list of points (let's just say 5 points):
Circle(1) = DefineCircleFrom3Points(p(1), p(2), p(3))
Circle(2) = DefineCircleFrom3Points(p(2), p(3), p(4))
Circle(3) = DefineCircleFrom3Points(p(3), p(4), p(5))
Circle(4) = DefineCircleFrom3Points(p(4), p(5), p(1))
Circle(5) = DefineCircleFrom3Points(p(5), p(1), p(2))
FinalCircle=AverageCircle(Circle(1), Circle(2), ..., Circle(5))
..just an idea, don't know if that would work or not...

__________________
"Fortunately, I live in the United States of America, where we are gradually coming to understand that nothing we do is ever our fault, especially if it is really stupid."  Dave Barry

10222003, 12:39 PM

Senior Contributor


Join Date: May 2003
Posts: 805


blindwig,
Thanks for the input. Your solution might provide an acceptable estimation, in some cases. I'll take a look at it, but I think I'm going to have to do a least squares fit to get the level of precision required. However, your solution might yield excellent starting values for the fit routine!


10222003, 03:40 PM


Code Meister
Retired Moderator * Guru *


Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441


If you start with only 5 points, you can do OK that way. The number of permutations becomes rather daunting though when you have, say, 100 points...
As it happens, I wrote an example of line fitting via the method of least squares in the Code Library. Check it out here:
http://www.xtremevbtalk.com/t44870.html

__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!"  Edmund Blackadder

10222003, 04:01 PM

Senior Contributor


Join Date: May 2003
Posts: 805


Thanks BillSoo,
I downloaded the project and will look at the code this evening.


10222003, 04:10 PM

Centurion


Join Date: Oct 2003
Location: San Francisco
Posts: 177


centerX = 1000 ' or any value you like
centerY = 1000
radius = 100
pi = 3.14159
for k=0 to 2 * pi step .01 ' or a larger step if you like
x = sin(k) * radius + centerX
y = cos(k) * radius + centerY
pset(x,y)
next k


10222003, 04:18 PM

Senior Contributor


Join Date: May 2003
Posts: 805


tony873004,
unless i'm misreading this, it looks like you're defining a bunch of points on a given circle. in other words, you pick the values for x, y and r and then define xy points on the circle. i'm going the other way. i have a bunch of xy points and i want the circle x, y and r that comes closest to passing through all the points. am i just missing what you said?


10222003, 04:24 PM

Centurion


Join Date: Oct 2003
Location: San Francisco
Posts: 177


No, that's what it is. Sorry, I misunderstood your question.


10242003, 06:43 AM

Senior Contributor


Join Date: May 2003
Posts: 805


BillSoo,
I've been looking at your code but don't have a clue about modifying it to handle circles. Do you know of any tutorials on developing regression algoritms?
Quote: Originally Posted by BillSoo As it happens, I wrote an example of line fitting via the method of least squares in the Code Library. Check it out here:
http://www.xtremevbtalk.com/t44870.html


10242003, 07:50 AM


Senior Contributor
* Expert *


Join Date: Sep 2002
Location: Karlsruhe, Germany
Posts: 1,319


Just for information, the distance from the Radius of the circle to an
arbitrary point, in the direction of a straight line drawn from the center
of the circle, is
((xpxc)^2 + (ypyc)^2)^(1/2)  R
Where xp,yp=point and xc,yc=center, R=radius.
I just don't know how you'd get the center, maybe do a mean of all
xp and yp...Then you can expand the radius outwards and then optimize
over the points gained from said formula


10242003, 08:04 AM


Algorithms 'R' Us
Forum Leader * Guru *


Join Date: Jun 2002
Location: Canberra
Posts: 4,127


Quote: Originally Posted by waits77 BillSoo,
I've been looking at your code but don't have a clue about modifying it to handle circles. Do you know of any tutorials on developing regression algoritms?
I'm not surprised you would have trouble!
The basic linearregression techniques are not so easily extended into nonlinear cases, and among nonlinear cases, conic sections (circles, ellipses, etc) are, well, let's say, nontrivial
For nonlinear geometric bestfits, the most common approach is to use a GaussNewton method, which will iterate through a series of linear leastsquare fitting stages, updating its guess at each stage. An algebraic fit can be used as the initial guess.
Here's an interesting, albeit challenging, outline:
http://www.math.temple.edu/~renault/ellipses.html

__________________
Cogito, ergo codo

10242003, 08:19 AM

Senior Contributor


Join Date: May 2003
Posts: 805


MathImagics,
Thanks, that's getting closer. I'm sorry to say that I'll have to do some studying to comprehend the article at your link. and even more to implement.


10242003, 08:21 AM


Algorithms 'R' Us
Forum Leader * Guru *


Join Date: Jun 2002
Location: Canberra
Posts: 4,127


Chernov & Lesort at U.Alabama appear to be an excellent source of knowledge about current understanding of this problem  they've even got some "C" examples (looks like a few thousand lines!). Start here: http://www.math.uab.edu/cl/cl1/

__________________
Cogito, ergo codo

10242003, 08:25 AM


Algorithms 'R' Us
Forum Leader * Guru *


Join Date: Jun 2002
Location: Canberra
Posts: 4,127


Quote: Originally Posted by waits77 I'm sorry to say that I'll have to do some studying to comprehend the article ... and even more to implement.
I suspect it would require some hard yakka for me, also, were I to attempt same
But we probably know now why there's no VB code snippet available!
Good luck, keep us apprised of your progress!

__________________
Cogito, ergo codo

10242003, 08:18 PM


Algorithms 'R' Us
Forum Leader * Guru *


Join Date: Jun 2002
Location: Canberra
Posts: 4,127


Maybe not so hard! I think we can take a few shortcuts now I've absorbed Chernov & Lesort.
As you can see from the literature, fitting conics requires iterative techniques, in this case we are theoretically searching in three dimensions, i.e. for an X, Y, and R, that minimises
F = SUM[ square of each point distance from circle(X,Y,R)]
Evaluation of F is proportional to the Number of Points in the sample, i.e. costs NP flops (each flop has 2 MULs and a SQRT) so any generalpurpose approach needs to be optimised, and the traditional approach is to use a Newtonlike method of the form
guess[n+1] = some function(guess[n]).
The practical problem is designing the algorithm what's the best f() that will provide iterative convergence.
But we must remember that generally these algorithms are trying to handle any data, even if the data is unusual (e.g. multiple solutions, points in a line, points already on a circle, etc), and to always terminate, avoiding getting stuck in "folds" of the solution surface being searched. And to do all this for maybe thousands of points.
In your real life application, however, we know a lot about our data, and can take advantage of this to simplify the procedure.
Quote:
1. You have a relatively small number of points
2. They will probably always be in a rectangle whose bounds can be predicted.
3. If there are multiple solutions, probably any of them will do.
3. A bounding rectangle for the solution can probably also be predicted.
4. We have plenty of time to compute the solution. Our glider is not moving at the speed of light, and compared to a Pentium 4 isn't really moving at all!

These conditions enable us, IMHO, to forego the need to use convergentiteration algorithms, and to simply use the relative power of our CPU to find the solution.
Chernov & Lesort's paper did provide one important tip (as well as those neat 3d graphs of the LSF function).
We need only search in 2 dimensions! The radius of the "best fit" circle at any given point is a function of the point, so a bruteforce algorithm needs only search a rectangle of the xyplane.
So we simply evaluate F for each search grid point, and pick the best.
I knocked up a demo program, using a search grid of 256x256 (64K search grid). It can do a 32point fit in just 1 second on a P2 (1mhz) in a VB exe.
Here's a screen shot. We can still add an iterative search algorithm if needs be, but maybe this will be fast enough.
Meanwhile, I'll see if can get a fix on what Chenov & Lesort finally come up with in that paper (I'm still curious)

__________________
Cogito, ergo codo
Last edited by MathImagics; 10242003 at 08:27 PM.

10242003, 08:33 PM


Algorithms 'R' Us
Forum Leader * Guru *


Join Date: Jun 2002
Location: Canberra
Posts: 4,127


BTW  the rather fetching colourgradients in the background plot (a plot of LSF() value at each point) are an artifice of the 256colour conversion. The program actually draws a greyscale!
The plot corresponds to a vertical view of the 3d F plots featured in the Chernov & Lesort paper, with black = high F, and white = best fit ( F = 0).

__________________
Cogito, ergo codo

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)


Thread Tools 

Display Modes 
Linear Mode

Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off





