|
#REDIRECT [[Triangulation]]
{{Multiple issues
| refimprove=April 2011
| orphan=April 2011
| confusing=April 2011
|expert = April 2011}}
'''Triangulation in three dimensions''' is a method of finding the ___location of a point in [[three dimensional|three dimensions]] based on other known coordinates and distances, it is commonly used in [[surveying]] and [[astronomy]].
[[Triangulation]] is also used in 2 dimensions to find the ___location of a point on a [[Plane (geometry)|plane]], this is commonly used in [[navigation]] to plot positions on a map.
==One method to triangulate a ___location in 3D==
This method uses [[vector analysis]] to determine the [[coordinates]] of the point where three lines meet given the [[scalar]] lengths of the lines and the coordinates of their bases. First treat these three lines as if they are the [[Radius|radii]] of three [[sphere]]s of known centers (these known centres being the coordinates of the known end of each line), this method can then 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 ==
[[File:Triangulation illust.gif|600px|thumb|Figure 1. The apex and its mirror reflection about the plane of ABC precipitate D and D'.]]
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 />
<br />
<br />
By the [[law of cosines]],
<br />
<br />
:<math>
(BD)^2 = (AB)^2+(AD)^2-2(AB)(AD)\cos(\angle{BAD})
</math>
:<math>
(CD)^2 = (AC)^2+(AD)^2-2(AC)(AD)\cos(\angle{CAD})
</math>
:<math>
(CD)^2 = (BC)^2+(BD)^2-2(BC)(BD)\cos(\angle{CBD})
</math>
<br />
<br />
<br />
<br />
<br />
[[image:facesABD ACD BCD 2.gif|700px|thumb|Figure 2. The normals are dropped on the sides from the apex and their intersections with AB, AC and BC are determined.]]
<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,
<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>
:<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>
:<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 />
[[image:Intersect normals ABC 3.gif|700px|thumb|Figure 3. The red normals intersect at a common point.]]<br />
The three [[unit normal]]s to '''AB''', '''AC''' and '''BC''' in the [[Plane (geometry)|plane]] of ABC are:
<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>
Then the three [[vector]]s intersect at a common point:
:<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>''
:<math>\begin{vmatrix}
m_{AB} \\
m_{AC} \\
m_{BC} \\
\end{vmatrix}
=(H^{T}H)^{-1}H^{T}\mathbf{g}</math>
== 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.
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,
:<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 />
Alternatively, solve the system of equations for ''m<sub>AB</sub>'', ''m<sub>AC</sub>'' and ''m<sub>BC</sub>'':
<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 />
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>
== 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>
<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 />
where
<br />
:<math>
M_{AB}D=AD\sqrt{1- \left [\dfrac{(AD)^2+(AB)^2-(BD)^2}{(AB)(AD)} \right ]^2}</math>
:<math>
M_{AC}D=AD\sqrt{1- \left [\dfrac{(AD)^2+(AC)^2-(BD)^2}{(AC)(AD)} \right ]^2}</math>
:<math>
M_{BC}D=BD\sqrt{1- \left [\dfrac{(BD)^2+(BC)^2-(CD)^2}{(BC)(BD)} \right ]^2}</math>
== Condition for intersection ==
If ''AD, BD, CD'' are assigned according to the arrangement,
<br />
:<math>AD \le BD \le CD</math>
Then ''AD, BD, CD'' intersect if and only if,<br />
:<math>AD+BD \ge AB \ge BD-AD</math>
:<math>AD+CD \ge AC \ge CD-AD</math>
:<math>BD+CD \ge BC \ge CD-BD</math>
<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>
then the three spheres intersect if and only if,<br />
:<math>r_A+r_B \ge AB \ge r_B-r_A</math>
:<math>r_A+r_C \ge AC \ge r_C-r_A</math>
:<math>r_B+r_C \ge BC \ge r_C-r_B</math>
== Decoding vector formulas ==
:<math>
\mathbf{A}=(x_A, y_A, z_A)</math>
:<math>
\mathbf{B}=(x_B, y_B, z_B)</math>
:<math>
\mathbf{C}=(x_C, y_C, z_C)</math>
<br />
:<math>
\mathbf{AB}=(x_B-x_A, y_B-y_A, z_B-z_A)</math>
:<math>
\mathbf{AC}=(x_C-x_A, y_C-y_A, z_C-z_A)</math>
:<math>
\mathbf{BC}=(x_C-x_B, y_C-y_B, z_C-z_B)</math>
<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>
:<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>
:<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 />
:<math>
AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2+(z_B-z_A)^2}</math>
:<math>
AC=\sqrt{(x_C-x_A)^2+(y_C-y_A)^2+(z_C-z_A)^2}</math>
:<math>
BC=\sqrt{(x_C-x_B)^2+(y_C-y_B)^2+(z_C-z_B)^2}</math>
<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 />
:<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 />
:<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 />
:<math>
\mathbf{M_{AB}}=(M_{ABx},M_{ABy},M_{ABz})</math>
:<math>
\mathbf{M_{AC}}=(M_{ACx},M_{ACy},M_{ACz})</math>
:<math>
\mathbf{M_{BC}}=(M_{BCx},M_{BCy},M_{BCz})</math>
<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>
:<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>
:<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>
:<math>
\mathbf{N_{AB}}=(N_{ABx},N_{ABy},N_{ABz})</math>
:<math>
\mathbf{N_{AC}}=(N_{ACx},N_{ACy},N_{ACz})</math>
:<math>
\mathbf{N_{BC}}=(N_{BCx},N_{BCy},N_{BCz})</math>
:<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>
:<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>
:<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>
:<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>
:<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>
:<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>
:<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>
:<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>
:<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 />
The equation of the line of the axis of symmetery of 3 spheres is,
:<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 />
:<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 />
:<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 />
:<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>
== Example ==
<!-- Deleted image removed: [[Image: 3 spheres2abcplane.gif|750px|thumb|Figure 4. The data is input into the equations to obtain the solution. The shaded area is the plane of ABC. A, B and C are the centers of each of the three spheres.]] --><!--
<br />
<br />-->
<!-- Deleted image removed: [[Image:3 spheres2ABCcenters.gif|750px|thumb|Figure 5. Showing points D and D' as the result of 3 intersecting spheres at centers A, B, C from data given in Figure 4. The line adjoining D and D' imbedded in the interiors of all three spheres is the axis of symmetry of the three spheres.]] --><!--
<br />
<br />-->
== See also ==
* [[Sphere]]
* [[Radii]]
* [[Coordinates]]
* [[Apex (geometry)]]
* [[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 --->
== External links ==
* [http://jons-math.bravehost.com/triangulation/triangulation03.xls Example of a spreadsheet that calculates solutions to this problem]
[[Category:Mathematics articles related to geometry]]
[[Category:Vector calculus]]
[[Category:Linear algebra]]
[[Category:Trigonometry]]
| 