Go Back  Xtreme Visual Basic Talk > Legacy Visual Basic (VB 4/5/6) > General > Best fit algorithm for circle given points


Reply
 
Thread Tools Display Modes
  #1  
Old 10-21-2003, 07:34 PM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default 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.
Reply With Quote
  #2  
Old 10-21-2003, 09:05 PM
BillSoo's Avatar
BillSoo BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default

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
Reply With Quote
  #3  
Old 10-21-2003, 09:28 PM
blindwig's Avatar
blindwig blindwig is offline
Ultimate Contributor

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

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((x1-x)^2+(y1-y)^2) = sqr((x2-x)^2+(y2-y)^2) = sqr((x3-x)^2+(y3-y)^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
Reply With Quote
  #4  
Old 10-21-2003, 11:21 PM
BillSoo's Avatar
BillSoo BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default

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
Reply With Quote
  #5  
Old 10-22-2003, 02:27 AM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

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.
Reply With Quote
  #6  
Old 10-22-2003, 11:25 AM
blindwig's Avatar
blindwig blindwig is offline
Ultimate Contributor

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

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
Reply With Quote
  #7  
Old 10-22-2003, 11:39 AM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

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!
Reply With Quote
  #8  
Old 10-22-2003, 02:40 PM
BillSoo's Avatar
BillSoo BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default

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
Reply With Quote
  #9  
Old 10-22-2003, 03:01 PM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

Thanks BillSoo,
I downloaded the project and will look at the code this evening.
Reply With Quote
  #10  
Old 10-22-2003, 03:10 PM
tony873004 tony873004 is offline
Centurion
 
Join Date: Oct 2003
Location: San Francisco
Posts: 177
Default

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
Reply With Quote
  #11  
Old 10-22-2003, 03:18 PM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

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?
Reply With Quote
  #12  
Old 10-22-2003, 03:24 PM
tony873004 tony873004 is offline
Centurion
 
Join Date: Oct 2003
Location: San Francisco
Posts: 177
Default

No, that's what it is. Sorry, I misunderstood your question.
Reply With Quote
  #13  
Old 10-24-2003, 05:43 AM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

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

Reply With Quote
  #14  
Old 10-24-2003, 06:50 AM
Robse's Avatar
Robse Robse is offline
Senior Contributor

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

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

((xp-xc)^2 + (yp-yc)^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
__________________
Posting Guidelines MSDN-VB API List Use [vb]...[/vb] tags for code!
Reply With Quote
  #15  
Old 10-24-2003, 07:04 AM
Mathimagics's Avatar
Mathimagics Mathimagics is offline
Algorithms 'R' Us

Forum Leader
* Guru *
 
Join Date: Jun 2002
Location: Canberra
Posts: 4,123
Default

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 linear-regression techniques are not so easily extended into non-linear cases, and among non-linear cases, conic sections (circles, ellipses, etc) are, well, let's say, non-trivial

For non-linear geometric best-fits, the most common approach is to use a Gauss-Newton method, which will iterate through a series of linear least-square 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
Reply With Quote
  #16  
Old 10-24-2003, 07:19 AM
waits77 waits77 is offline
Senior Contributor
 
Join Date: May 2003
Posts: 805
Default

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.
Reply With Quote
  #17  
Old 10-24-2003, 07:21 AM
Mathimagics's Avatar
Mathimagics Mathimagics is offline
Algorithms 'R' Us

Forum Leader
* Guru *
 
Join Date: Jun 2002
Location: Canberra
Posts: 4,123
Default

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
Reply With Quote
  #18  
Old 10-24-2003, 07:25 AM
Mathimagics's Avatar
Mathimagics Mathimagics is offline
Algorithms 'R' Us

Forum Leader
* Guru *
 
Join Date: Jun 2002
Location: Canberra
Posts: 4,123
Default

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
Reply With Quote
  #19  
Old 10-24-2003, 07:18 PM
Mathimagics's Avatar
Mathimagics Mathimagics is offline
Algorithms 'R' Us

Forum Leader
* Guru *
 
Join Date: Jun 2002
Location: Canberra
Posts: 4,123
Default

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 general-purpose approach needs to be optimised, and the traditional approach is to use a Newton-like 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 convergent-iteration 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 3-d 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 brute-force algorithm needs only search a rectangle of the xy-plane.

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 32-point 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)
Attached Images
File Type: bmp Sample1.bmp (136.7 KB, 67 views)
__________________
Cogito, ergo codo

Last edited by MathImagics; 10-24-2003 at 07:27 PM.
Reply With Quote
  #20  
Old 10-24-2003, 07:33 PM
Mathimagics's Avatar
Mathimagics Mathimagics is offline
Algorithms 'R' Us

Forum Leader
* Guru *
 
Join Date: Jun 2002
Location: Canberra
Posts: 4,123
Default

BTW - the rather fetching colour-gradients in the background plot (a plot of LSF() value at each point) are an artifice of the 256-colour 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
Reply With Quote
Reply


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

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Why am I experiencing problems with this code? Some Guy General 20 06-11-2003 05:15 AM
Highlight Points that's diplayed in the Graph zhen General 4 04-01-2003 07:39 PM
Shortest path with many points stauf General 7 11-20-2002 07:04 AM
Rotating lots of points...eg using cos and sin andreww Game Programming 9 03-24-2002 12:47 AM
Reverse Data Points 123 321 eko General 6 02-17-2002 08:46 AM

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
 
 
-->