JMU
Computational Geometry
An Introduction (in 2D)


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Background
Computing the Angle formed by a Ray
Computing the Angle between two Rays
Computing the Angle between two Lines
Calculating Distances
The Distance from a Point to a Line
The Distance from a Point to a Line (cont.)

The Minimum Distance from a Point to a Ray

images/point-to-ray.gif
The Distance from a Point to a Line (cont.)
  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.)
The Distance from a Point to a Line (cont.)
The Distance from a Point to a Line Segment

One Case

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

Another Case

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

Distinguishing Between Cases - One Method

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

Distinguishing Between Cases - Another Method

images/point-to-segment4.gif
Some Useful Results