From: Brian Victor <bhv11@...>

Date: Fri, 12 Dec 1997 20:10:41 -0500

Date: Fri, 12 Dec 1997 20:10:41 -0500

At 5:21 PM +1100 12/11/97, Lazlo Toth wrote: >2. Given the coordinates of three points that lie on the arc of a circle, >how do you find the radius and centre of that circle. >JC OK... here we go. :) You've got three points which are known to lie on the arc of a circle: (x1,y1),(x2,y2), and (x3,y3). Now, every line segment which has its endpoints on the a circle can have a perpendicular line at its midpoint which intersects the center of the circle. To find the center, we calculate the line segments and their perpendiculars, and find where the perpendiculars intersect. With those three points, we can draw three lines. We only need two. I'll use from point 1 to 2 and from 2 to 3. At the moment we only need the slope of the lines. We'll figure out their actual locations later. I'm going to refer to the line from point 1 to 2 as line i, and from 2 to 3 as line j. The slope (m) of the line is defined as the change in y divided by the change in x: mi = (y2 - y1) / (x2 - x1) mj = (y3 - y2) / (x3 - x2) Next we need to locate the midpoint of lines i and j. This is the mean value of the coordiantes of the points: yi = (y2 + y1) / 2 xi = (x2 + x1) / 2 yj = (y3 + y2) / 2 xj = (x3 + x2) / 2 Now that we have the slope and a point on each line, we can now create the linear equation for the perpendicular lines. Since the line we're trying to find is perpendicular to the slope we obtained previously, we need to use the slope's opposite recipricol: y - yi = (-1/mi)(x - xi) y = (-1/mi)(x - xi) + yi y = (-1/mi) * x - (-1/mi) * xi + yi Yesterday I showed you how to find the intersection between the two equations y=Ax+B and y=Cx+D. From the above, A can be assigned (-1/mi) and B can be assigned ((-1/mi) * xi + yi). Likewise, C is (-1/mj) and D is ((-1/mj) * xj + yj). After you get this far, use the technique I demonstrated yesterday to find the intersection of those points to find your center point. Note that the code above is rather prone to division by zero errors. This will occur when two of the points on the circle that you are testing are on the same vertical line. In this case, you can check to see if the x coordinates are the same, and if they are, you know that (-1/m) will equal 0. Further note that I derived most of this on the fly and have performed minimal testing on it. It seems to be algebraicly accurate, from what I can see, but if you find any errors, write back and I'll look more closely. If anything, I probably flipped a sign somewhere. To the second part of your question... once you know the center of the circle, to find the radius you simply calculate the distance between the center and one of your points. The Pythagorean theorem comes in handy for this. r = ((centerx - x1)^2 + (centery - y1)^2)^(1/2) Again, you'll very likely want many of these variables to be single or double precision, as integer types probably won't give you the accuracy you want. Hope this helps. If you need any further clarification, write back. -- Brian Victor