|
#REDIRECT [[Triangulation]]
{{multiple issues|confusing=April 2011|lead missing=April 2011|orphan=April 2011|refimprove=April 2011}}
{{expert|date=April 2011}}
== Development ==
Suppose three sticks of known length are anchored in the ground at known coordinates. This development calculates the coordinates of the apex where the other ends of the three sticks will meet. These coordinates are given by the vector '''D'''. '''D'''' is the vector to the coordinates of the apex where the three sticks would meet below the plane of '''A, B, C''' as well. This problem also calculates the axis of symmetry of three intersecting spheres. See the article [[Trilateration|Trilateration]] for the spherical case. Even if the three spheres don't intersect, this problem still calculates their axis of symmetry. This axis is the line drawn between '''D''' and '''D''''. To proceed, 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 lengths ''AD, BD, CD'' are planted in the ground at known [[coordinates]] '''A, B, C'''. 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>
\mathbf{M_{AB}}=(M_{ABx},M_{ABy},M_{ABz})</math><br />
:<math>
\mathbf{M_{AC}}=(M_{ACx},M_{ACy},M_{ACz})</math><br />
:<math>
\mathbf{M_{BC}}=(M_{BCx},M_{BCy},M_{BCz})</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>
\mathbf{N_{AB}}=(N_{ABx},N_{ABy},N_{ABz})</math><br />
:<math>
\mathbf{N_{AC}}=(N_{ACx},N_{ACy},N_{ACz})</math><br />
:<math>
\mathbf{N_{BC}}=(N_{BCx},N_{BCy},N_{BCz})</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 ==
This is a robust solution incorporating all possibilities and accommodating non-intersecting cases with the closest answer using the least squares calculation of matrix H and '''b'''.
<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]
| 