Computational Geometry

Computational Geometry
An Introduction (in 2D)

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}||$

There's Always More to Learn