- Forward


Triangulation
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Getting Started
Back SMYC Forward
  • Surveying:
    • Triangulation is the process of determining the location of a point using angles formed between it and points with known locations
    • Trialateration is the process of determining the location of a point using the distances between it and points with known locations
  • For Our Purposes:
    • We won't distinguish between the two
Using Distances in One Dimension
Back SMYC Forward
  • The Problem:
    • Given one or more points with known locations, determine the location of a point using the distances between it and those points
  • Notation:
    • \(p \in \mathbb{R}\) denotes a point
    • \(\cal{C(p, \ell)}\) denotes the set of points that are exactly distance \(\ell\) from \(p\)
Using Distances in One Dimension (cont.)
Back SMYC Forward
  • With One Known Location:
    • Given the location of the point \(p\) and the distance from \(p\) to \(a\), determine the location of the point \(a\)
  • A Specific Example:
    • \(p\) is located at 4
    • The distance from \(p\) to \(a\) is 2
  • Visualization:
    • images/triangulation_1d_one-point.png
Using Distances in One Dimension (cont.)
Back SMYC Forward
  • With One Known Location (cont.):
    • You can see from the example that the problem is under-identified when there is only one known location
  • A Specific Example with Two Known Locations:
    • \(p\) is located at 4
    • The distance from \(p\) to \(a\) is 2
    • \(q\) is located at 9
    • The distance from \(q\) to \(a\) is 3
  • Visualization:
    • images/triangulation_1d_two-points.png
Using Distances in Two Dimensions
Back SMYC Forward
  • Generalizing the Notation:
    • \(p \in \mathbb{R}^2\) now denotes a point on the plane (i.e., in two dimensions)
  • Recall:
    • A circle is the set of points in a plane that are a given distance (called the radius) from a given point (called the center)
  • The Implication:
    • We need to find the intersections of circles
Using Distances in Two Dimensions (cont.)
Back SMYC Forward
  • An Example:
    • \(p = (2.0, 3.0)\) and \(\ell(p) = 5.0\)
    • \(q = (4.5, 10.0)\) and \(\ell(q) = 3.0\)
    • \(r = (7.5, 6.5)\) and \(\ell(r) = 2.5\)
  • Visualization:
    • images/triangulation_2d.png
Using Distances in Two Dimensions (cont.)
Back SMYC Forward
  • Recall:
    • Letting \((h, k)\) denote the center of the circle, and \(r\) denote its radius, the circle is defined as the set of points \((x, y)\) that satisfy:
      \( \sqrt{(x - h)^2 + (y - k)^2} = r \)
  • Squaring Both Sides:
    • \( (x - h)^2 + (y - k)^2 = r^2 \)
Using Distances in Two Dimensions (cont.)
Back SMYC Forward
  • Intersection of Two Circles:
    • They may not intersect
    • They may intersect at one point
    • They may intersect at two points
  • Finding the Intersection:
    • Requires a little algebra, but isn't difficult (as long as you account for the different possibilities)
There's Always More to Learn
Back -