|
#REDIRECT [[Triangulation]]
{{multiple issues|confusing=April 2011|lead missing=April 2011|orphan=April 2011|refimprove=April 2011}}
{{expert|date=April 2011}}
In [[vector analysis]], [[triangulation]] is a method of finding points in [[three dimensional]] spaces using distances, angles and vector functions such as [[magnitude]], [[dot product]] and [[cross product]]. Among its uses are in [[surveying]], [[navigation]], and [[astronomy]].
This article describes a method for determining the [[coordinates]] of the point where three lines meet, given the [[scalar]] lengths of the lines and the coordinates of their bases. If these three lines are the radii of three [[sphere]]s of known centers, this method can be used to calculate the intersection of the three spheres ''if they intersect''. In the event that the three spheres don't intersect, this method obtains the closest solution to the axis of symmetry between three spheres.
== Development ==
Three sticks of known lengths ''AD, BD, CD'' are anchored in the ground at known coordinates '''A, B, C'''. 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'''. In the mirror case, '''D'''' is sub-apex where the three sticks would meet below the plane of '''A, B, C''' as well.
<br />
[[image: triangulation_illust_02.gif]]
<br />
By the [[law of cosines]],
<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 />
<br />
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,
[[image: facesABD_ACD_BCD_2.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 />
<br />
The three [[unit normal]]s to '''AB''', '''AC''' and '''BC''' in the [[Plane (geometry)|plane]] of ABC are:
<br />
[[image: Intersect_normals_ABC_3.gif]]
<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 />
<br />
== Condition for intersection ==
If ''AD, BD, CD'' are arranged as,
<br />
:<math>AD \le BD \le CD</math><br />
Then ''AD, BD, CD'' intersect if and only if,<br />
:<math>AD+BD \ge AB \ge BD-AD</math><br />
:<math>AD+CD \ge AC \ge CD-AD</math><br />
:<math>BD+CD \ge BC \ge CD-BD</math><br /><br />
<br />
Viz, if <br />
''AD''=r<sub>A</sub>=radius of sphere centered at '''A''',<br />
''BD''=r<sub>B</sub>=radius of sphere centered at '''B''', and <br />
''CD''=r<sub>C</sub>=radius of sphere centered at '''C''',<br />
such that, <br />
:<math>r_A \le r_B \le r_C</math><br />
then the three spheres intersect if and only if,<br />
:<math>r_A+r_B \ge AB \ge r_B-r_A</math><br />
:<math>r_A+r_C \ge AC \ge r_C-r_A</math><br />
:<math>r_B+r_C \ge BC \ge r_C-r_B</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 />
== Example ==
[[image: Example_00_triang_02.gif]]
<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/triangulation03.xls Example of a spreadsheet that calculates solutions to this problem]
| 