- Forward


Computational Geometry
An Introduction (in 2D)


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • Shapes:
    • We need to perform a variety of calculations involving points, lines, line segements, and polygons (on the plane)
  • Norms and Metrics:
    • We will use the Euclidean norm (and the metric generated by it)
Computing the Angle formed by a Ray
Back Forward
  • Visualization:
    • images/angle-of-ray.gif
  • Calculation:
    • \(\alpha = \tan^{-1} (a_{2} / a_{1})\)
Computing the Angle between two Rays
Back Forward
  • Visualization:
    • images/angle-between-rays.gif
  • Calculation:
    • \(\theta = \alpha_{b} - \alpha_{a}\)
Computing the Angle between two Lines
Back Forward
  • Visualization:
    • images/angle-between-lines.gif
  • Gaining Understanding:
    • Translate the point of intersection (and the other points) to the origin
    • Proceed as with rays
Calculating Distances
Back Forward
  • Remember the Distance Between Two Points?
    • \(d(\bs{p}, \bs{q}) = ||\bs{p} - \bs{q}|| = \sqrt{(p_{1} - q_{1})^{2} + (p_{2} - q_{2})^{2}}\)
  • What is the Distance from a Point to...
    • a line?
    • a line segment?
    • a polygon?
The Distance from a Point to a Line
Back Forward
  • Some Observations:
    • A line contains an infinite number of distance
    • We could calculate the distance to any of them
  • A Common Practice:
    • Use the minimum distance
The Distance from a Point to a Line (cont.)
Back Forward

The Minimum Distance from a Point to a Ray

images/point-to-ray.gif
The Distance from a Point to a Line (cont.)
Back Forward
  1. The problem: \(\mbox{argmin } ||\bs{b} - \bs{p}|| = \mbox{argmin } ||\bs{b} - \bs{p}||^{2}\)
  2. \(\bs{p} = \lambda \bs{a}\)
  3. Re-stating the problem: \(\mbox{min}_{\lambda} Z(\lambda) = ||\bs{b} - \lambda \bs{a}||^{2}\)
  4. \(\frac{dZ}{d \lambda} = 2 \bs{a} \cdot (\bs{a} \lambda - \bs{b})\)
  5. \(\frac{dZ}{d \lambda} = 0 \Rightarrow \bs{a} \cdot (\bs{a} \lambda\bs{a} - \bs{b}) = 0\)
  6. \(\Rightarrow \lambda = \frac{\bs{a} \cdot \bs{b}}{\bs{a} \cdot \bs{a}}\)
  7. \(\bs{p} = \lambda \bs{a} = \frac{\bs{a} \cdot \bs{b}}{\bs{a} \cdot \bs{a}} \bs{a}\)
The Distance from a Point to a Line (cont.)
Back Forward
  • A Particularly Interesting Step:
    • \(\bs{a} \cdot (\bs{a} \lambda - \bs{b}) = 0\)
  • Interpretation:
    • The inner product of \(\bs{a}\) and \((\bs{a} \lambda - \bs{b})\) is 0
    • The "line defining the minimum distance" is perpendicular to the ray
The Distance from a Point to a Line (cont.)
Back Forward
  • The General Case:
    • Denote the line \(A\) through \(\bs{a}\) and \(\bs{b}\) by \(\{ \lambda \bs{a} + (1 - \lambda) \bs{b}: \lambda \in \mathbb{R} \}\)
  • The Distance:
    • \(d(\bs{c}, A) = \frac{| (a_{2}-b_{2})c_{1} + (b_{1}-a_{1})c_{2} + (a_{1}b_{2} - b_{1}a_{2}) |}{||\bs{a}-\bs{b}||}\)
The Distance from a Point to a Line Segment
Back Forward

One Case

images/point-to-segment1.gif
The Distance from a Point to a Line Segment (cont.)
Back Forward

Another Case

images/point-to-segment2.gif
The Distance from a Point to a Line Segment (cont.)
Back Forward

Distinguishing Between Cases - One Method

images/point-to-segment3.gif
The Distance from a Point to a Line Segment (cont.)
Back Forward

Distinguishing Between Cases - Another Method

images/point-to-segment4.gif
Some Useful Results
Back Forward
  • Manipulating Norms:
    • \(||\bs{a}+\bs{b}||^{2} = ||\bs{a}||^{2} + ||\bs{b}||^{2} + 2 \bs{a} \cdot \bs{b}\)
  • Schwartz's Inequality:
    • \(|\bs{a} \cdot \bs{b}| \leq ||\bs{a}|| \enspace ||\bs{b}||\)
There's Always More to Learn
Back -