Still working to recover. Please don't edit quite yet.
Triangulation in three dimension
| This article contains content from Wikipedia An article on this subject has been nominated for deletion on Wikipedia: Wikipedia:Articles for deletion/ Triangulation in three dimension Current versions of the GNU FDL article on WP may contain information useful to the improvement of this article |
WP+ NO DEL |
- Should this subject be given attention by an expert, they may find this article redundant to the Wikipedia:Wikipedia:Trilateration article, to which it has been made a redirect. Or, this may contain useful information that the Trilateration article leaves out
In mathematics, triangulation in three dimensions is a method of finding the location of a point in three dimensions based on other known coordinates and distances, it is commonly used in Wikipedia:surveying and Wikipedia:astronomy. Wikipedia:Triangulation is also used in two dimensions to find the location of a point on a plane, this is commonly used in Wikipedia:navigation to plot positions on a map.
| This article may contain material from Wikipedia An article on this subject has been redirected to another page on WP: Triangulation in three dimension Current versions of the GNU FDL article on Wikipedia may contain information useful to the improvement of this article |
WP R E D |
Contents
One method to triangulate a location in 3D[edit]
This method uses Wikipedia:vector analysis to determine the Wikipedia: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 radii of three Wikipedia:spheres 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 Wikipedia:axis of symmetry between three spheres.
Development[edit]
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.
By the Wikipedia:law of cosines,
- <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>
700px|thumb|Figure 2. The normals are dropped on the sides from the apex and their intersections with AB, AC and BC are determined.
The projection[1] of AD onto AB and AC, and the projection of BD onto BC results in,
- <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>
700px|thumb|Figure 3. The red normals intersect at a common point.
The three Wikipedia:unit normals to AB, AC and BC in the plane of ABC are:
- <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>
- <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>
- <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 vectors 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>
Solving for mAB, mAC and mBC
- <math>\begin{vmatrix}
m_{AB} \\ m_{AC} \\ m_{BC} \\ \end{vmatrix} =(H^{T}H)^{-1}H^{T}\mathbf{g}</math>
Spreadsheet formula[edit]
A Wikipedia:spreadsheet command for calculating this is,
- 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 Wikipedia:least squares solution[2] 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>
Alternatively, solve the system of equations for mAB, mAC and mBC:
<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>
The unit normal to the plane of ABC is,
- <math>\mathbf{N_D}=\dfrac{\mathbf{AC}\times\mathbf{AB}}{\left \Vert{\mathbf{AC}\times\mathbf{AB}} \right \|}</math>
Solution[edit]
- <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>
where
- <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[edit]
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 = rA = radius of sphere centered at A,
- BD = rB = radius of sphere centered at B, and
- CD = rC = radius of sphere centered at C,
such that,
- <math>r_A \le r_B \le r_C</math>
then the three spheres intersect if and only if,
- <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[edit]
- <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>
- <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>
- <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>
- <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>
- <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>
- <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>
- <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>
- <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>
- <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>
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>
- <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>
- <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>
- <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[edit]
Deleted image removed: 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. Deleted image removed: 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.
See also[edit]
- Wikipedia:Sphere
- Wikipedia:Radii
- Wikipedia:Coordinates
- Wikipedia:Apex (geometry)
- Wikipedia:Law of cosines
- Wikipedia:Unit normal
- Plane
- Wikipedia:Spreadsheet
- Wikipedia:Least squares
- Wikipedia:Trilateration
- Wikipedia:GPS
- Wikipedia:Dot product
- Wikipedia:Cross product
- Magnitude
- Wikipedia:Vector analysis
- Wikipedia:Linear algebra
- Wikipedia:Matrix algebra
References[edit]
- ↑ Borisenko, A. I. and Tarapov, I. E., (1968) "Vector and Tensor Analysis", General Publishing Company, p. 6. ISBN 0-486-63833-2
- ↑ Leon, Steven J. (1980) "Linear Algebra", Macmillan Publishing Co., Inc., p. 152. ISBN 0-02-369870-5
