|
#REDIRECT [[Triangulation]]
<!--{{multiple issues|confusing=April 2011|lead rewrite=April 2011|orphan=April 2011|unreferenced=April 2011}}
{{expert|date=April 2011}}-->
== Development ==
Three [[sphere]]s of known centers '''A, B, C''' and known [[Radius|radii]] ''AD, BD, CD'' intersect at two points '''D''' and '''D''''. Similarly, three sticks of known length are planted in the ground at known [[coordinates]]. The other ends meet at a calculated [[apex]]. Calculating '''D''' and '''D'''', the projection<ref>Borisenko, A. I. and Tarapov, I. E., (1968) "Vector and Tensor Analysis", General Publishing Company, p. 6. ISBN 0-486-63833-2</ref> of '''AD''' onto '''AB''' and '''AC''', and the projection of '''BD''' onto '''BC''' results in,
<br />
[[image: Triangulation illust.gif]]
<br />
:<math>\mathbf
{M_{AB}} = \mathbf{A}+ AD\cos(\angle{BAD})\dfrac{\mathbf{AB}}{\left \Vert \mathbf{AB} \right \|}=\mathbf{A}+ \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{2(AB)^2} \right ]\mathbf{AB}
</math><br />
:<math>\mathbf
{M_{AC}} = \mathbf{A}+ AD\cos(\angle{CAD})\dfrac{\mathbf{AC}}{\left \Vert \mathbf{AC} \right \|}=\mathbf{A}+ \left [\dfrac{(AD)^2+(AC)^2-(CD)^2}{2(AC)^2} \right ]\mathbf{AC}
</math><br />
:<math>\mathbf
{M_{BC}} = \mathbf{B}+ BD\cos(\angle{CBD})\dfrac{\mathbf{BC}}{\left \Vert \mathbf{BC} \right \|}=\mathbf{B}+ \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{2(BC)^2} \right ]\mathbf{BC}
</math><br />
<br />
::<math>
(BD)^2 = (AB)^2+(AD)^2-2(AB)(AD)\cos(\angle{BAD})
</math><br />
::<math>
(CD)^2 = (AC)^2+(AD)^2-2(AC)(AD)\cos(\angle{CAD})
</math><br />
::<math>
(CD)^2 = (BC)^2+(BD)^2-2(BC)(BD)\cos(\angle{CBD})
</math><br /><br />
::By the [[law of cosines]].
<br />
<br />
The three [[unit normal]]s to '''AB''', '''AC''' and '''BC''' in the [[Plane (geometry)|plane]] of ABC are:
<br /><br />
:<math>
\mathbf{N_{AB}}=\cfrac{\mathbf{AC}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}\mathbf{AB}}{\left \Vert{ \mathbf{AC}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}\mathbf{AB}} \right \|}
</math>
<br />
:<math>
\mathbf{N_{AC}}=\cfrac{\mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}\mathbf{AC}}{\left \Vert{ \mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}\mathbf{AC}} \right \|}
</math>
<br />
:<math>
\mathbf{N_{BC}}=\cfrac{\mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}\mathbf{BC}}{\left \Vert{ \mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}\mathbf{BC}} \right \|}
</math>
<br />
Then the three [[vector]]s intersect at a common point:
<br /><br />
:<math>\mathbf{M_{AB}}+m_{AB}\mathbf{N_{AB}}=
\mathbf{M_{AC}}+m_{AC}\mathbf{N_{AC}}=
\mathbf{M_{BC}}+m_{BC}\mathbf{N_{BC}}</math>
<br /><br />
Solving for ''m<sub>AB</sub>'', ''m<sub>AC</sub>'' and ''m<sub>BC</sub>''
<br /><br />
:<math>\begin{vmatrix}
m_{AB} \\
m_{AC} \\
m_{BC} \\
\end{vmatrix}
=(H^{T}H)^{-1}H^{T}\mathbf{g}</math>
<br />
== Spreadsheet formula ==
A [[spreadsheet]] command for calculating this is,
<br />
:PRODUCT(PRODUCT(MINVERSE(PRODUCT(TRANSPOSE H, H)), TRANSPOSE H), '''g''')
An example of a spreadsheet that does complete calculations of this entire problem is given at the '''External links''' section at the end of this article.
<br /><br />
The the matrix H and the matrix '''g''' in this ''[[least squares]] solution''<ref>Leon, Steven J. (1980) "Linear Algebra", Macmillan Publishing Co., Inc., p. 152. ISBN 0-02-369870-5</ref> are,
<br /><br />
:<math>
H=
\begin{vmatrix}
N_{ABx} & -N_{ACx} & 0 \\
N_{ABy} & -N_{ACy} & 0 \\
N_{ABz} & -N_{ACz} & 0 \\
0 & N_{ACx} & -N_{BCx} \\
0 & N_{ACy} & -N_{BCy} \\
0 & N_{ACz} & -N_{BCz} \\
N_{ABx} & 0 & -N_{BCx} \\
N_{ABy} & 0 & -N_{BCy} \\
N_{ABz} & 0 & -N_{BCz}
\end{vmatrix}
\qquad
\mathbf{g}=
\begin{vmatrix}
M_{ACx}-M_{ABx} \\
M_{ACy}-M_{ABy} \\
M_{ACz}-M_{ABz} \\
M_{BCx}-M_{ACx} \\
M_{BCy}-M_{ACy} \\
M_{BCz}-M_{ACz} \\
M_{BCx}-M_{ABx} \\
M_{BCy}-M_{ABy} \\
M_{BCz}-M_{ABz} \\
\end{vmatrix}
</math><br />
<br />
Alternatively, solve the system of equations for ''m<sub>AB</sub>'', ''m<sub>AC</sub>'' and ''m<sub>BC</sub>'':
<br /><br />
<math>
\begin{align}
N_{ABx}m_{AB}-N_{ACx}m_{AC}&=M_{ACx}-M_{ABx} \\
N_{ACy}m_{AC}-N_{BCy}m_{BC}&=M_{BCy}-M_{ACy} \\
N_{ABz}m_{AB}-N_{BCz}m_{BC}&=M_{BCz}-M_{ABz} \\
\end{align}
</math><br />
<br />
The unit normal to the plane of ABC is,
<br />
:<math>\mathbf{N_D}=\dfrac{\mathbf{AC}\times\mathbf{AB}}{\left \Vert{\mathbf{AC}\times\mathbf{AB}} \right \|}</math>
<br />
== Solution ==
<br />
<math>
\mathbf{D} =
\begin{cases}
\mathbf{M_{AB}}+m_{AB}\mathbf{N_{AB}}+\sqrt{(M_{AB}D)^2-m_{AB}^2}\mathbf{N_D} \\
\mathbf{M_{AC}}+m_{AC}\mathbf{N_{AC}}+\sqrt{(M_{AC}D)^2-m_{AC}^2}\mathbf{N_D} \\
\mathbf{M_{BC}}+m_{BC}\mathbf{N_{BC}}+\sqrt{(M_{BC}D)^2-m_{BC}^2}\mathbf{N_D}
\end{cases}
</math>
<br /><br />
<math>
\mathbf{D'} =
\begin{cases}
\mathbf{M_{AB}}+m_{AB}\mathbf{N_{AB}}-\sqrt{(M_{AB}D)^2-m_{AB}^2}\mathbf{N_D} \\
\mathbf{M_{AC}}+m_{AC}\mathbf{N_{AC}}-\sqrt{(M_{AC}D)^2-m_{AC}^2}\mathbf{N_D} \\
\mathbf{M_{BC}}+m_{BC}\mathbf{N_{BC}}-\sqrt{(M_{BC}D)^2-m_{BC}^2}\mathbf{N_D}
\end{cases}
</math>
<br />
<br />
where
<br />
:<math>
M_{AB}D=AD\sqrt{1- \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{(AB)(AD)} \right ]^2}</math><br />
:<math>
M_{AC}D=AD\sqrt{1- \left [\dfrac{(AD)^2+(AC)^2-(BD)^2}{(AC)(AD)} \right ]^2}</math><br />
:<math>
M_{BC}D=BD\sqrt{1- \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{(BC)(BD)} \right ]^2}</math><br />
<br />
== Decoding vector formulas ==
:<math>
\mathbf{A}=(x_A, y_A, z_A)</math><br />
:<math>
\mathbf{B}=(x_B, y_B, z_B)</math><br />
:<math>
\mathbf{C}=(x_C, y_C, z_C)</math><br />
<br />
:<math>
\mathbf{AB}=(x_B-x_A, y_B-y_A, z_B-z_A)</math><br />
:<math>
\mathbf{AC}=(x_C-x_A, y_C-y_A, z_C-z_A)</math><br />
:<math>
\mathbf{BC}=(x_C-x_B, y_C-y_B, z_C-z_B)</math><br />
<br />
:<math>\mathbf{AC}\bullet\mathbf{AB}=(x_C-x_A)(x_B-x_A)+(y_C-y_A)(y_B-y_A)+(z_C-z_A)(z_B-z_A)</math><br />
:<math>\mathbf{AB}\bullet\mathbf{AC}=(x_C-x_A)(x_B-x_A)+(y_C-y_A)(y_B-y_A)+(z_C-z_A)(z_B-z_A)</math><br />
:<math>\mathbf{AB}\bullet\mathbf{BC}=(x_B-x_A)(x_C-x_B)+(y_B-y_A)(y_C-y_B)+(z_B-z_A)(z_C-z_B)</math><br />
<br />
:<math>
AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2+(z_B-z_A)^2}</math><br />
:<math>
AC=\sqrt{(x_C-x_A)^2+(y_C-y_A)^2+(z_C-z_A)^2}</math><br />
:<math>
BC=\sqrt{(x_C-x_B)^2+(y_C-y_B)^2+(z_C-z_B)^2}</math><br />
<br />
:<math>
\left \Vert{ \mathbf{AC}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}\mathbf{AB}} \right \|
=\sqrt{(AC)^2-\cfrac{(\mathbf{AC}\bullet\mathbf{AB})^2}{(AB)^2}}</math><br />
<br />
:<math>
\left \Vert{ \mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}\mathbf{AC}} \right \|
=\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{AC})^2}{(AC)^2}}</math><br />
<br />
:<math>
\left \Vert{ \mathbf{AB}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}\mathbf{BC}} \right \|
=\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{BC})^2}{(BC)^2}}</math><br />
<br />
:<math>
{M_{ABx}} = {x_A}+ \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{2(AB)^2} \right ](x_B-x_A)
</math>
:<math>
{M_{ABy}} = {y_A}+ \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{2(AB)^2} \right ](y_B-y_A)
</math>
:<math>
{M_{ABz}} = {z_A}+ \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{2(AB)^2} \right ](z_B-z_A)
</math><br />
<br />
:<math>
{M_{ACx}} = {x_A}+ \left [\dfrac{(AD)^2+(AC)^2-(CD)^2}{2(AC)^2} \right ](x_C-x_A)
</math>
:<math>
{M_{ACy}} = {y_A}+ \left [\dfrac{(AD)^2+(AC)^2-(CD)^2}{2(AC)^2} \right ](y_C-y_A)
</math>
:<math>
{M_{ACz}} = {z_A}+ \left [\dfrac{(AD)^2+(AC)^2-(CD)^2}{2(AC)^2} \right ](z_C-z_A)
</math><br />
<br />
:<math>
{M_{BCx}} = {x_B}+ \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{2(BC)^2} \right ](x_C-x_B)
</math>
:<math>
{M_{BCy}} = {y_B}+ \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{2(BC)^2} \right ](y_C-y_B)
</math>
:<math>
{M_{BCz}} = {z_B}+ \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{2(BC)^2} \right ](z_C-z_B)
</math>
<br /><br />
:<math>
{N_{ABx}}=\cfrac{{(x_C-x_A)}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}(x_B-x_A)}{\sqrt{(AC)^2-\cfrac{(\mathbf{AC}\bullet\mathbf{AB})^2}{(AB)^2}}}
</math><br />
:<math>
{N_{ABy}}=\cfrac{{(y_C-y_A)}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}(y_B-y_A)}{\sqrt{(AC)^2-\cfrac{(\mathbf{AC}\bullet\mathbf{AB})^2}{(AB)^2}}}
</math><br />
:<math>
{N_{ABz}}=\cfrac{{(z_C-z_A)}-\cfrac{\mathbf{AC}\bullet\mathbf{AB}}{(AB)^2}(z_B-z_A)}{\sqrt{(AC)^2-\cfrac{(\mathbf{AC}\bullet\mathbf{AB})^2}{(AB)^2}}}
</math><br />
<br />
:<math>
{N_{ACx}}=\cfrac{{(x_B-x_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}(x_C-x_A)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{AC})^2}{(AC)^2}}}
</math><br />
:<math>
{N_{ACy}}=\cfrac{{(y_B-y_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}(y_C-y_A)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{AC})^2}{(AC)^2}}}
</math><br />
:<math>
{N_{ACz}}=\cfrac{{(z_B-z_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{AC}}{(AC)^2}(z_C-z_A)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{AC})^2}{(AC)^2}}}
</math><br />
<br />
:<math>
{N_{BCx}}=\cfrac{{(x_B-x_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}(x_C-x_B)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{BC})^2}{(BC)^2}}}
</math><br />
:<math>
{N_{BCy}}=\cfrac{{(y_B-y_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}(y_C-y_B)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{BC})^2}{(BC)^2}}}
</math><br />
:<math>
{N_{BCz}}=\cfrac{{(z_B-z_A)}-\cfrac{\mathbf{AB}\bullet\mathbf{BC}}{(BC)^2}(z_C-z_B)}{\sqrt{(AB)^2-\cfrac{(\mathbf{AB}\bullet\mathbf{BC})^2}{(BC)^2}}}
</math><br />
<br />
The equation of the line of the axis of symmetery of 3 spheres is,
<br /><br />
:<math>
\cfrac{x-(M_{ABx}+m_{AB}N_{ABx})}{(y_C-y_A)(z_B-z_A)-(y_B-y_A)(z_C-z_A)}=
\cfrac{y-(M_{ABy}+m_{AB}N_{ABy})}{(x_B-x_A)(z_C-z_A)-(x_C-x_A)(z_B-z_A)}=
\cfrac{z-(M_{ABz}+m_{AB}N_{ABz})}{(x_C-x_A)(y_B-y_A)-(x_B-x_A)(y_C-y_A)}
</math><br />
<br />
:<math>
\mathbf{AC}\times\mathbf{AB}=
\begin{vmatrix}
\mathbf{i} & \mathbf{j} & \mathbf{k} \\
x_C-x_A & y_C-y_A & z_C-z_A \\
x_B-x_A & y_B-y_A & z_B-z_A \\
\end{vmatrix}
</math><br />
<br />
:<math>
=\Big((y_C-y_A)(z_B-z_A)-(y_B-y_A)(z_C-z_A),\ (x_B-x_A)(z_C-z_A)-(x_C-x_A)(z_B-z_A),\ (x_C-x_A)(y_B-y_A)-(x_B-x_A)(y_C-y_A)\Big)
</math><br />
<br />
:<math>
\left \Vert{\mathbf{AC}\times\mathbf{AB}} \right \|=
\begin{Bmatrix}
\Big((y_C-y_A)(z_B-z_A)-(y_B-y_A)(z_C-z_A)\Big)^2 +\\
\Big((x_B-x_A)(z_C-z_A)-(x_C-x_A)(z_B-z_A)\Big)^2 +\\
\Big((x_C-x_A)(y_B-y_A)-(x_B-x_A)(y_C-y_A)\Big)^2
\end{Bmatrix}^\frac{1}{2}
</math><br />
<br />
== Discussion ==
While the same result can be obtained using only a few of these many equations, all possibilities are treated here. If the three spheres do not intersect, the least squares solution finds the axis of symmetry of the three spheres, or the closest solution. If the three spheres do intersect, the solution requires only a few of these equations.<br />
== See also ==
* [[Sphere]]
* [[Radii]]
* [[Coordinates]]
* [[Apex]]
* [[Law of cosines]]
* [[Unit normal]]
* [[Plane]]
* [[Spreadsheet]]
* [[Least squares]]
* [[Trilateration]]
* [[GPS]]
* [[Dot product]]
* [[Cross product]]
* [[Magnitude]]
* [[Vector analysis]]
* [[Linear algebra]]
* [[Matrix algebra]]
== References ==
<!--- See [[Wikipedia:Footnotes]] on how to create references using <ref></ref> tags which will then appear here automatically -->
{{Reflist}}
<!--- Categories --->
[[Category:Vector calculus]]
[[Category:Linear algebra]]
[[Category:Trigonometry]]
== External links ==
* [http://jons-math.bravehost.com/triangulation/triangulation00.xls Example of a spreadsheet that calculates solutions to this problem]
| 