|
#REDIRECT [[Triangulation]]
<!-- Please do not remove or change this AfD message until the issue is settled -->
{{Article for deletion/dated|page=Triangulation in three dimensions|timestamp=20120904021807|year=2012|month=September|day=4|substed=yes|help=off}}
<!-- For administrator use only: {{Old AfD multi|page=Triangulation in three dimensions|date=4 September 2012|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
{{Multiple issues
| refimprove=April 2011
| expert = April 2011}}
In mathematics, '''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 two 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 (mathematics)|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 [[Euclidean vector|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 ==
: <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,
:<math>AD \le BD \le CD</math>
Then ''AD, BD, CD'' intersect if and only if,
:<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>
Viz, if
: ''AD'' = ''r''<sub>''A''</sub> = radius of sphere centered at '''A''',
: ''BD'' = ''r''<sub>''B''</sub> = radius of sphere centered at '''B''', and
: ''CD'' = ''r''<sub>''C''</sub> = radius of sphere centered at '''C''',
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 three 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 (geometry)|Plane]]
* [[Spreadsheet]]
* [[Least squares]]
* [[Trilateration]]
* [[GPS]]
* [[Dot product]]
* [[Cross product]]
* [[Magnitude (vector)|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]]
| 