9
$\begingroup$

Given the three coordinates $(x_1, y_1, z_1)$, $(x_2, y_2, z_2)$, $(x_3, y_3, z_3)$ defining a circle in 3D space, how to find the coordinates of the center of the circle $(x_0, y_0, z_0)$?

$\endgroup$
  • $\begingroup$ @Behaviour I don't think this is an exact duplicate because the answers to the previous question only work in 2D. $\endgroup$ – Rahul Dec 21 '14 at 2:36
3
$\begingroup$

There are plenty of online articles for the 2D case. A simple google search will show that this link provides a good explanation about how this is done in 2D. It also shows how to construct the circle center geometrically. So, what you need to do is

1) Find a plane from the 3 points and create a 2D coordinate system on that plane.
2) Convert all 3 points to that 2D coordinate system.
3) Find the circle center using the link above.
4) Convert the circle center (in 2D) back to 3D.

Edit 1: I added the steps for creating a local coordinate system (CS) on a plane defined by 3 points

1) Compute unit vector n1 from P1 and P2. Use this as the x-axis for the local CS.
2) Compute unit vector n2 from P1 and P3.
3) Use n1 x n2 (where 'x' means the cross product) as the z-axis of the local CS.
4) Use (n1 x n2) x n1 as the y-axis of the local CS.
5) Now, you have a local coordinate system, I hope that you know how to convert P1, P2 and P3 to this local CS. After the conversion, the new coordinates for these 3 points should all have their z values = 0.0. You can then use their (x, y) values to find the center of the circle.

If you have all 3 points collinear, you cannot create a local CS and you cannot find a circle from 3 collinear points either.

$\endgroup$
  • $\begingroup$ Can you demonstrate how to convert from a 3D system to a 2D system? $\endgroup$ – Dylan Dec 21 '14 at 22:38
  • $\begingroup$ I added more details to my answer. Hope it helps. $\endgroup$ – fang Dec 22 '14 at 4:16
  • $\begingroup$ That's an interesting method. I still prefer my own method, which is exactly the same but without the change of coordinates. $\endgroup$ – Dylan Dec 22 '14 at 8:22
  • $\begingroup$ @Dylan: Your method creates bisecting planes. My method converst 3D coordinates to 2D coordinates and create bisecting lines. So, yes they are theoretically the same. But working in 2D is easier to visualize the picture for most people. $\endgroup$ – fang Dec 22 '14 at 18:24
3
$\begingroup$

In fact, we have to solve the following system

$\cases{(x_0-x_1)^2+(y_0-y_1)^2+(z_0-z_1)^2=R^2\\ (x_0-x_2)^2+(y_0-y_2)^2+(z_0-z_2)^2=R^2\\ (x_0-x_3)^2+(y_0-y_3)^2+(z_0-z_3)^2=R^2\\ \left|\begin{array}{} x_0 & y_0 & z_0 & 1\\ x_1 & y_1 & z_1 & 1\\ x_2 & y_2 & z_2 & 1\\ x_3 & y_3 & z_3 & 1\\ \end{array}\right|=0}$

But I hope that somebody will write a nicer way.

Update. It seems the following.

Put $r_i=(x_i,y_i,z_i)$. Then the problem transformes to the following

$$\|r_1\|^2-2(r_0,r_1)= \|r_2\|^2-2(r_0,r_2)= \|r_3\|^2-2(r_0,r_3).$$

There exist real numbers $\mu_1, \mu_2, \mu_3$ such that $\mu_1+\mu_2+\mu_3=1$ and $r_0=\mu_1 r_1+\mu_2 r_2+\mu_3 r_3.$ We can find these numbers from a system of linear equations:

$$\mu_1+\mu_2+\mu_3=1$$

$$(1-2\mu_1) (r_1,r_1)-2\mu_2 (r_2,r_1)-2\mu_3 (r_3,r_1)=$$ $$-2\mu_1 (r_1,r_2)+(1-2\mu_2)(r_2,r_2)-2\mu_3 (r_2,r_3)=$$ $$-2\mu_1 (r_1,r_3)-2\mu_2(r_2,r_3)+(1-2\mu_3) (r_3,r_3).$$

$\endgroup$
  • $\begingroup$ The problem is you don't know R at this moment. $\endgroup$ – fang Dec 21 '14 at 20:54
  • $\begingroup$ @fang This is the smallest problem, :-) because we can easily eliminate $R$ and reduce the first three equations to two. $\endgroup$ – Alex Ravsky Dec 21 '14 at 20:59
  • $\begingroup$ That is true. But it is not immediately clear to non-math-savy developers.:-) $\endgroup$ – fang Dec 21 '14 at 21:13
  • $\begingroup$ @fang 4 equations in 4 unknowns - hard to be more clear. +1 $\endgroup$ – Mark McClure Dec 21 '14 at 21:27
  • $\begingroup$ Not so clear for nonlinear equations. At least to me. :-) $\endgroup$ – fang Dec 21 '14 at 21:30
2
$\begingroup$

I think using a projection into 2D might be the easiest way to actually calculate. If the points are $A, B, C$ then find

$$\begin{align} \mathbf{u_1} & = B-A \\ \mathbf{w_1} &= (C-A) \times \mathbf{u_1} \\ \mathbf{u} & = \mathbf{u_1} / | \mathbf{u_1} | \\ \mathbf{w} & = \mathbf{w_1} / | \mathbf{w_1} | \\ \mathbf{v} & = \mathbf{w} \times \mathbf{u} \\ \end{align}$$

This gives three orthogonal unit vectors with $\mathbf{u}$ and $\mathbf{v}$ spanning the plane.

Get 2D coordinated by taking the dot products of $(B-A)$ and $(C-A)$ with $\mathbf{u}$ and $\mathbf{v}$. Let

$$\begin{align} b & = (b_x,0) = ( (B-A) \cdot \mathbf{u} , 0 ) \\ c &= (c_x,c_y) = ( (C-A) \cdot \mathbf{u}, (C-A)\cdot \mathbf{v} ) \\ \end{align}$$

We know the center must lie on the line $x= b_x/2$. Let this point be $(b_x/2,h)$. The distance from c must be the same as the distance from the origin $$(c_x-b_x/2)^2 + (c_y - h)^2 = (b_x/2)^2 + h^2$$ So $$h = \frac{(c_x-b_x/2)^2 + c_y^2 - (b_x/2)^2}{ 2 c_y } $$

The actual center can then be recovered by taking $A + (b_x/2)\mathbf{u} + h \mathbf{v}$.

This is a nice explicit calculation.

$\endgroup$
2
$\begingroup$

Another possible way.

The equation of a sphere in 3D space can be written as: $$ x^2+y^2+z^2-2\alpha x -2\beta y -2\gamma z +d=0 $$ where $(\alpha,\beta,\gamma)$ are the coordinate of the center $O$ and $d=\alpha^2+\beta^2+\gamma^2-R^2$

Given three points $A=(x_A,y_A,z_A)$, $B=(x_B,y_B,z_B)$, $C=(x_C,y_C,z_C)$, substituting in this equation we find three linear equations in $\alpha$,$\beta$, $\gamma$ and $d$ that we can write in the form: $$ x_A\alpha+y_A\beta+z_A\gamma=\dfrac{d-|A|^2}{2} $$ $$ x_B\alpha+y_B\beta+z_B\gamma=\dfrac{d-|B|^2}{2} $$ $$ x_C\alpha+y_C\beta+z_C\gamma=\dfrac{d-|C|^2}{2} $$ where $|A|^2=x_A^2+y_A^2+z_A^2$, $|B|^2=x_B^2+y_B^2+z_B^2$ and $|C|^2=x_C^2+y_C^2+z_C^2$.

From these equations, we can find $\alpha$, $\beta$ and $\gamma$ as functions of $d$ and this corresponds to the fact that there are infinite spheres passing through the given points.

Now, the circle that we want is the maximum circle of the sphere that has the center on the plane that contain the three points and this menas that the three vectors $OA$,$OB$ and $OC$ are linearly dependent, so we must have:

$$ \det \begin{bmatrix} \alpha-x_A &\beta-y_A &\gamma-z_A\\ \alpha-x_B &\beta-y_B &\gamma-z_B\\ \alpha-x_C &\beta-y_C &\gamma-z_C\\ \end{bmatrix}=0 $$ with abit of calculus we can see that this reduces to: $$ \alpha \det \begin{bmatrix} 1 &y_A &z_A\\ 1 &y_B &z_B\\ 1 &y_C &z_C\\ \end{bmatrix}+ \beta \det \begin{bmatrix} x_A &1 &z_A\\ x_B &1 &z_B\\ x_C &1 &z_C\\ \end{bmatrix}+ \gamma \det \begin{bmatrix} x_A &y_A &1\\ x_B &y_B &1\\ x_C &y_C &1\\ \end{bmatrix}- \det \begin{bmatrix} x_A &y_A &z_A\\ x_B &y_B &z_B\\ x_C &y_C &z_C\\ \end{bmatrix}=0 $$

That is another linear equation from which we can find the coordinates of the center and the radius.

$\endgroup$
1
$\begingroup$

Let the known points be $A(x_1, y_1, z_1)$, $B(x_2, y_2, z_2)$ and $C(x_3, y_3, z_3)$. We want to find $I(x,y,z)$ so that $I$ is coplanar with $A,B,C$ and equidistant from $A,B,C$.

There is a geometric way to solve this. I assume you know how to find the equation of plane from a point and a normal vector? If not, look here.

Based on that, you can think of $I$ as the intersection of 3 planes:

  1. Since $IA = IB$, $I$ must lie on the perpendicular bisecting plane of line segment $AB$. This is a plane that passes the midpoint $M\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2},\frac{z_1+z_2}{2}\right)$ of $AB$, and is perpendicular to $AB$ (its normal vector is $\overrightarrow{AB}$).

  2. Similar to plane 1 but with line segment $AC$ or $BC$ instead of $AB$

  3. Finally, $I$ must lie on the plane containing the points $A,B,C$. Its normal vector is $\overrightarrow{AB} \times \overrightarrow{AC}$.

Once you have the equations for the above planes, you end up with a linear system of equations, which should be easy to solve. The solution to the system is the coordinate of $I$.

$\endgroup$
1
$\begingroup$

I think this is one of the simplest solution:

Given three points of a circle:
$p1~(p1_x, p1_y, p1_z)^T$
$p2~(p2_x, p2_y, p2_z)^T$
$p3~(p3_x, p3_y, p3_z)^T$

Estimate the circle center:
$p0~(p0_x, p0_y, p0_z)^T$


  1. Estimate vectors $v1$ and $v2$:

$v1 = p2-p1 = (v1_x, v1_y, v1_z)^T $
$v2 = p3-p1 = (v2_x, v2_y, v2_z)^T $

  1. Estimate dot products:

$v11 = v1^T·v1$
$v22 = v2^T·v2$
$v12 = v1^T·v2$

  1. Estimate scalars $k_1$ and $k_2$:

$k_1 = b·v22·(v11 - v12)$

$k_2 = b·v11·(v22 - v12)$

$b = \frac{1}{2·(v11·v22-v12^2)}$

  1. Estimate circle center p0:

$p0 = p1 + k_1·v1 + k_2·v2$

==>

$p0_x = p1_x + k_1·v1_x + k_2·v2_x$
$p0_y = p1_y + k_1·v1_y + k_2·v2_y$
$p0_z = p1_z + k_1·v1_z + k_2·v2_z$

Full derivation and code here: https://github.com/sergarrido/random/tree/master/circle3d

$\endgroup$
-1
$\begingroup$

Let's assume the circle is defined by the 3 points a, b and c, and that the center is denoted d. Following the hints in the answers above the coordinates of points a, b and c can be plugged into the equation of a circle. 3 circle equations and 4 unknowns (3 coordinates of the center c plus the radius) means that we have 2 remaining unknowns for one equation. This equation in fact represents the line passing through the center of the circle, having equal distance to points a, b and c. Intersecting this line with the plane spanned by a, b and c gives the point c. The rest is algebra, making use of some smart substitution of variables:

        Cx = bx-ax
        Cy = by-ay
        Cz = bz-az
        Bx = cx-ax
        By = cy-ay
        Bz = cz-az
        B2 = ax**2-cx**2+ay**2-cy**2+az**2-cz**2
        C2 = ax**2-bx**2+ay**2-by**2+az**2-bz**2

        CByz = Cy*Bz-Cz*By
        CBxz = Cx*Bz-Cz*Bx
        CBxy = Cx*By-Cy*Bx
        ZZ1 = -(Bz-Cz*Bx/Cx)/(By-Cy*Bx/Cx)
        Z01 = -(B2-Bx/Cx*C2)/(2*(By-Cy*Bx/Cx))
        ZZ2 = -(ZZ1*Cy+Cz)/Cx
        Z02 = -(2*Z01*Cy+C2)/(2*Cx)

and finally the coordinates of the center:

        dz = -((Z02-ax)*CByz-(Z01-ay)*CBxz-az*CBxy)/(ZZ2*CByz-ZZ1*CBxz+CBxy)
        dx = ZZ2*dz + Z02
        dy = ZZ1*dz + Z01
$\endgroup$
  • 2
    $\begingroup$ Perhaps a little explanation of your logic would be helpful to the asker? $\endgroup$ – The Count Nov 11 '16 at 15:50
  • $\begingroup$ An explanation would still be nice, even a year and a half later. People are still finding this post when looking for how to fit a circle through three points in 3D =) $\endgroup$ – Mike 'Pomax' Kamermans Jul 7 '18 at 17:41
-1
$\begingroup$

I know this is late but hopefully this can help someone else. I will write it down in steps without explaining too much as I believe the steps are simple enough. Let the points be P1 P2 and P3.

  1. Calculate the plane containing the three points.
  2. Calculate the perpendicular bisectors of the line segments [P1 P2] and [P1 P3] , or any other combination that you want, such that this perpendicular bisector also lies in the plane containing P1,P2 and P3.
  3. The intersection of these 2 perpendicular bisectors should be the center of the cricle.

I can elaborate more if anyone wishes so :-)

$\endgroup$
  • $\begingroup$ this answer just describes, in far less detail, the exact answer @fang already gave in 2014 $\endgroup$ – Mike 'Pomax' Kamermans Jul 7 '18 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.