Archived

This topic is now archived and is closed to further replies.

PSioNiC

How to calculate circle with 3 points

Recommended Posts

PSioNiC    122
If you are given 3 coordinates in 2d (or 3d if anyone knows) space, how to you calculate the circle (or sphere) that lies on all three points ? I have already come up with one algorythm, but its lengthly and couldn''t be used in real-time. Is their a simple algorythm that does this ?

Share this post


Link to post
Share on other sites
Aprosenf    372
You need 4 points to define a sphere in 3-D space, but only 3 for a circle in 2-D space. I''ll try to solve the 2-D problem.

First, test if the three points are colinear (i.e. if the lie on a line). If they are, there is no solution. Next, calculate the perpindicular bisectors of the segments AB abd BC, and find where they intersect. I''m not sure if the following will work:

  
// The points are (x1, y1), (x2, y2), and (x3, y3)


if(((x1 == x2) && (y1 == y2)) || ((x1 == x3) && (y1 == y3)) || ((x2 == x3) && (y2 == y3)))
return; // Test if two points coincide

if(((x1 == x2) && (x1 == x3)) || ((y1 == y2) && (y2 == y3)))
return; // Test if they''re on hor/ver line

if((y2 - y1) / (x2 - x1) == (y3 - y2) / (x3 - x2))
return; // Test if they''re colinear


double m1, b1, m2, b2;

m1 = (x1 - x2) / (y2 - y1); // Negative reciprocal

b1 = (y1 + y2) / 2. - m1 * (x1 + x2) / 2.; // Point-slope on the midpoint of AB

m2 = (x2 - x3) / (y3 - y2);
b2 = (y2 + y3) / 2. - m2 * (x2 + x3) / 2.;

double ix, iy;

ix = (b2 - b1) / (m1 - m2);
iy = m1 * ix + b1;

And then (ix, iy) should be the center of the circle. Just make sure to test for a divide-by-0 and adjust accordingly.

Share this post


Link to post
Share on other sites
cliffhawkens    122
...actually, you only need two points for a 2D circle, assuming it is indeed a true circle: you need a center point and a point along the circumference.

You can easily find the radius with:

sqrt(
((circumference_x-center_x)*(circumference_x-center_x))
+
((circumference_y-center_y)*((circumference_y-center_y))
);

the subtractions being to translate to relative coords.
With the result you could then use a sine-wave or similar method to calculate the rest of the points along that circle.

for(int x=-radius; x<=radius; x++)
{
drawpoint(x,radius*sin((radius/(2*PI))*x));
drawpoint(x,-(radius*sin((radius/(2*PI))*x)));
}


Obviously not optimized, and I'm not even certain it's correct as it's just something I thought up...who knows, maybe the equations aren't even correct: just a suggestion, though.
-----------------
...and unless you're really lucky, it's unlikely that you could derive a perfect circle from three points.

(o= erydo =o)
>


Edited by - cliffhawkens on February 5, 2002 11:40:02 PM

Share this post


Link to post
Share on other sites
Aprosenf    372
cliffhawkens, what PSioNic meant was how to find a circle that passes through three given points. It''s obvious how to do it if you already have the center point and one other point on the circle. If you''re looking for the circle that passes through two given points, there are an infinite number, and they all have their centers on the line that is the perpindicular bisector of the segment that connects the two points. That''s why the unique center of the circle that passes through three points (if it exists at all) lies on the intersection of the three perpindicular bisectors of the sides of the triangle formed by the three points (you can prove that all three intersect at one point using coordinate geometry). You only need to calculate the intersection of two of these perpindicular bisectors (calculating the others would be redundant). The point that is the center of the circle that passes through the three points of a triangle is known as its circumcenter . For you geometry buffs out there, the point that is the center of the circle that is tangent to the three sides of a triangle is called its incenter , and is the intersection of the three angle bisectors of a triangle (which also all intersect at one point). The other two "center" points of a triangle are the orthocenter , which is the intersection of the three altitudes of a triangle (which could be outside the triangle) and the centroid , which is the intersection of the three medians of a triangle, and is also the triangle''s center of mass. Intersetingly, the circumcenter, centroid, and orthocenter of a triangle all lie along the same line, called the Euler line , and the centroid is 1/3 of the way from the circumcenter to the orthocenter.

Share this post


Link to post
Share on other sites
FatRay    122
edit: ignore Rays babbling.
been reading too much.

Then you have the Ass-Card off the table.




[edited by - fatray on September 2, 2002 11:20:01 AM]

Share this post


Link to post
Share on other sites
alvaro    21263
If you want to do it in 3D, do the following.

If your points are A, B and C, find the intersection of the following planes:
- the one that contains A, B and C;
- the perpendicular bisector of A and B;
- the perpendicular bisector of A and C.

That point is the center O of the circle. The radius is the distance from O to A.

That should be pretty easy to implement. If you need more details, I can write some code.

Share this post


Link to post
Share on other sites