PDA

View Full Version : circumcicle

01-27-2002, 02:25 PM
Can anybody help me with fitting a circle to three 3D points. I know the formula for fitting 3 2d points with circumcircle. i need some help with 3d points. thanks in advance.

s_p_oneil
01-31-2002, 05:52 AM
For 3D do you mean a circum-sphere, or do you really want a flat 2D circle represtented in 3D space? I'd represent a sphere with its radius and center point. I suppose I'd represent a flat circle with its radius and plane (which would consist of center point and normal).

Either way, the first idea that comes to mind is that 3 non-parallel points in 3D space define a 2D plane. You can solve the 3D problem using your 2D solution if you project those points onto that plane. Then you can use the center and radius from the 2D solution to find the 3D solution. As long as your current algorithm finds the optimal 2D solution, then this method will find the optimal 3D solution.

In the rare case that you have 3 parallel points (which you may still have to handle), just ignore the point in the middle and calculate the center between the other two.

Use a custom projection matrix to project the 3D points onto the 2D plane. I don't have time to figure out and explain how to do this, but hopefully this will be enough for you to solve the problem. If not, perhaps there are others who can help you out on that.

P.S. - If you ever need to solve this problem for more than 3 points, you should go ahead and buy a book on Computational Geometry.