Computational Geometry

Computational Geometry
An Introduction (in 2D)

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

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

Computing the Angle between two Rays

Computing the Angle between two Lines

Visualization:
Gaining Understanding:
- Translate the point of intersection (and the other points) to the origin
- Proceed as with rays

Calculating Distances

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

Some Observations:
- A line contains an infinite number of points
- We could calculate the distance to any of them
A Common Practice:
- Use the minimum distance (using the Euclidean norm)

The Distance from a Point to a Line (cont.)

The Minimum Distance from a Point to a Ray

The Distance from a Point to a Line (cont.)

The problem: \(\mbox{argmin } ||\bs{b} - \bs{p}|| = \mbox{argmin } ||\bs{b} - \bs{p}||^{2}\)
\(\bs{p} = \lambda \bs{a}\)
Re-stating the problem: \(\mbox{min}_{\lambda} Z(\lambda) = ||\bs{b} - \lambda \bs{a}||^{2}\)
\(\frac{dZ}{d \lambda} = 2 \bs{a} \cdot (\bs{a} \lambda - \bs{b})\)
\(\frac{dZ}{d \lambda} = 0 \Rightarrow \bs{a} \cdot (\lambda\bs{a} - \bs{b}) = 0 / 2 = 0\)
\(\Rightarrow \lambda = \frac{\bs{a} \cdot \bs{b}}{\bs{a} \cdot \bs{a}}\)
\(\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.)

A Particularly Interesting Step:
- \(\bs{a} \cdot (\bs{a} \lambda - \bs{b}) = 0 / 2 = 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.)

Using a Line Instead of a Ray:
- 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

One Case

The Distance from a Point to a Line Segment (cont.)

Another Case

The Distance from a Point to a Line Segment (cont.)

Distinguishing Between Cases - One Method

The Distance from a Point to a Line Segment (cont.)

Distinguishing Between Cases - Another Method

The Distance from a Point to a Line Segment (cont.)

A Surprising Example - \(p\) Is Outside the Bounds of \(a\) and \(b\)

Some Useful Results

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}||\)