I have a system of quadratics, obtained from three mechanical links, fixed at one end and free at the other. The intersection point of the three free ends is required.

$AC=\sqrt{(A_x-C_x)^2+(A_y-C_y)^2+(A_z-C_z)^2}$

$BC=\sqrt{(B_x-C_x)^2+(B_y-C_y)^2+(B_z-C_z)^2}$

$FC=\sqrt{(F_x-C_x)^2+(F_y-C_y)^2+(F_z-C_z)^2}$

Where C_x,y,z are the unknowns. I am halfway through solving by substitution and it is really messy. Does anyone know of a slightly more elegant way of solving these? Any techniques I should research. I want to avoid doing it numerically if possible. Many Thanks James

-
What is a mechanical link? –  Heberto del Rio May 30 '13 at 20:04
Just an arm or lever - these ones are fixed by ball joints at one end and free to move at the other. –  James Izzard May 30 '13 at 20:06

So basically what you have are three circles and you want to find the point where they intersect. I am going to show you how to use linear algebra to solve your problem with an example.

Suppose that your three circles are: $C_1=(-3, 50), r_1=41$, $C_2=(11,-2), r_2=13$, and $C_3=(13,34), r_3=25$. Let us write the equations of the three circles:

\begin{align*} x^2 + 6x + 9 + y^2 - 100y + 2500 &= 1681\\ x^2 - 22x + 121 + y^2 + 4y + 4 &= 169\\ x^2 - 26x + 169 + y^2 - 68y + 1156 &= 625 \end{align*}

After re arranging them we have:

\begin{align*} x^2 + y^2 &= -6x + 100y - 828\\ x^2 + y^2 &= 22x - 4y + 44\\ x^2 + y^2 &= 26x + 68y - 700 \end{align*}

And finally this can be transformed in the following linear system:

\begin{align*} -6x + 100y - 828 &= 22x - 4y + 44\\ -6x + 100y - 828 &= 26x + 68y - 700 \end{align*}

which reduces to:

\begin{align*} -28x + 104y &= 872\\ -32x + 32y &= 128 \end{align*}

whose solution is: $(6,10)$. The tale of the story is the following, The system of linear equations is solely formed from the data: centers and radii.

-
I really like the quadratic to linear transformation - but how do you get to the two solutions from the quadratics? I am actually dealing with spheres instead of circles - but the concept of what you say seems to still follow. Thanks for providing such a detailed explanation. –  James Izzard May 31 '13 at 7:30
Having had a closer look at this - The method you propose works for the first case of eliminating the quadratic components but does not for the second. I think this is because my initial x,y,z coordinates for the three known root points are a mix of positive and negatives from the coordinate origin. This must mean that in some cases the required solution requires using the positive quadratic solution and in other cases the negative quadratic solution is required. I am guessing this method is equivalent to using the positive quadratic solutions? –  James Izzard May 31 '13 at 8:27
Ok fantastic - I have just worked it all the way through and can now see what was happening. If you substitute the linear expressions for x y and z back into the original quadratics - you get your two solutions out. Thanks very much. Exactly what I was looking for. –  James Izzard Jun 1 '13 at 21:24

Squaring and reordering the equations yields: $$\begin{array}{ccccccccc} C_x^2 + C_y^2 + C_z^2 & = & 2A_xC_x & + & 2A_yC_y & + & 2A_zC_z & + & |AC|^2 - (A_x^2+A_y^2+A_z^2) \\ C_x^2 + C_y^2 + C_z^2 & = & 2B_xC_x & + & 2B_yC_y & + & 2B_zC_z & + & |BC|^2 - (B_x^2+B_y^2+B_z^2) \\ C_x^2 + C_y^2 + C_z^2 & = & 2F_xC_x & + & 2F_yC_y & + & 2F_zC_z & + & |FC|^2 - (F_x^2+F_y^2+F_z^2) \\ \end{array}$$

Let $A_r = |AC|^2-(A_x^2+A_y^2+A_z^2)$ (and similarly for $B_r$ and $F_r$). Subtracting the last equation from the previous two reduces this to: $$\begin{array}{ccccccc} 2(A_x-F_x)C_x & + & 2(A_y-F_y)C_y & + & 2(A_z-F_z)C_z & = & F_r - A_r \\ 2(B_x-F_x)C_x & + & 2(B_y-F_y)C_y & + & 2(B_z-F_z)C_z & = & F_r - B_r \\ \end{array}$$

This is an under-determined system of equations which can be solved to obtain the general solution in the form $(C_x,C_y,C_z)=(P_x+v_xt,P_y+v_yt,P_z+v_zt)$ for some point $P=(P_x,P_y,P_z)$ and vector $(v_x,v_y,v_z)$, where $t$ can be any real number. Plugging these into any of the first three equations above yields a quadratic equation with unknown $t$, solving of which should be easy enough (and the solution can be used to obtain $(C_x,C_y,C_z)$ afterwards).

If you're going to implement this on a computer, there are a few corner cases that might need to be considered (e.g. some coordinates of the points being equal, thus resulting in zero coefficients in the system of equations; solutions not existing; ...).

-
Hi Peter. This looks really promising -thanks very much for taking the time. I am struggling to follow you from the two under-determined equations to your general solution, but am still working on it. Would you be able to suggest any resources I could have a look at to better follow this? Thanks again. James –  James Izzard Jun 1 '13 at 15:08