Saturday, February 25, 2012

Best Fit Circle: find the center using Excel

Finding the center of a best fit circle depends on minimizing the same function we were concerned with in finding the radius, except that we are going to view it as a function of the center instead of as a function of the radius:

where a and b are the x- and y-coordinates, respectively, of the center and r is given by
What we have here is a function of two variables.  It looks like three variables until you realize that r is calculated in terms of the other two.  So, we can do a three dimensional plot and see what the scoop is.  I used Maxima to do this and obtained a very good view of the surface near the best fit center of the points I have been using in all of my investigations of this problem.  Here is the 3D plot:

What we are most encouraged to see in this graph is that it looks very smooth and it looks like there is exactly one point that is the lowest point.  This lowest point is where the SSE function is minimized and constitutes the best center of the circle.  We can use the method of steepest descent to find this value - something which I've often read about and have a broad picture of but have never gotten into all of the fine details.  But here is the idea:  a drop of water falls on to the surface of this shape - somewhere.  That's our first guess.  The water flows in the direction of steepest descent - so we figure out which way that is.  Then we take another guess in the direction we determined is steepest and we do the same thing until everywhere we look around, we'd have to go up.  (I have more ideas about it than I'm telling right now, but those will have to wait.)

We can get Excel to do all the hard work for us if we set up a spreadsheet and use Excel's Solver.  Here is a video on how to do that:

The spreadsheet I am using in the video can by downloaded here.
For a Maxima approach see here.

No comments: