mathgeometrytrilateration

TULIP Trilateration in 2-D algorithm in simpler form


I found an algorithm to do trilateration in 2-D this link. But the formulas are too complicated. What is happening here? Can you please break it down to terms like dot product, cross product, distance etc?


Solution

  • Let P be the unknown point. (Bold for 2D vectors.)

    Write the implicit equations of circles 1 and 2:

    (P - P1)² = d1²

    (P - P2)² = d2²

    Substract memberwise and rearrange:

    2.(P2 - P1).P = d1² - d2² + P2² - P1²

    Similarly with circles 1 and 3:

    2.(P3 - P1).P = d1² - d3² + P3² - P1²

    Looking closely, you will notice that this forms a system of two linear equations in two unknowns:

    2.(X2 - X1).X + 2.(Y2 - Y1).Y = d1² - d2² + P2² - P1²

    2.(X3 - X1).X + 2.(Y3 - Y1).Y = d1² - d3² + P3² - P1²

    Use Cramer's rule, or if you insist on using vector calculus, work it out as follows.

    Rewrite the system as:

    A.P = a

    B.P = b

    Compute vectors perpendicular to A and B in the xy plane, using cross products A' = A /\ 1z and B' = B /\ 1z, and express P as a linear combination of these:

    P = u . A' + v . B'

    Performing a dot product with A and B gives, after simplification:

    A.P = a = v . A.B'

    B.P = b = u . B.A'

    Note that A.B' = A.(B /\ 1z) = 1z.(A /\ B) = -1z.(B /\ A) = -B.(A /\ 1z) = -B.A' (mixed product).

    All in all:

    P = [ (- b.A + a.B) /\ 1z ] / [ 1z.(A /\ B) ]

    (which is a rewrite of Cramer's result.)