Analytic Geometry

Analytic Geometry
An Introduction to Shapes in the Plane

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

Geometry:
- The mathematics of shapes
Analytic Geometry:
- Branch of geometry in which points are represented with respect to a coordinate system
- Introduced by Descartes in the 1600s

Points

Definition:
- A point in \(\mathbb{R}^{2}\) is an ordered pair of numbers (called coordinates)
Working with Points:
- We have (almost) everything we need from our study of vectors

Lines: Explicit Form

Explicit Form (aka Slope-Intercept Form):
- Given \(m \in \mathbb{R}\) and \(b \in \mathbb{R}\) the set of ordered pairs \((x,y)\) that satisfy \(y = mx + b\) are said to be a line in \(\mathbb{R}^{2}\)
Interpretation:
- \(m\) is the slope of the line
- \(b\) is the vertical intercept

Lines: Implicit Form

A Shortcoming of the Explicit Form:
- There is no way to represent vertical lines
One Small Adjustment:
- Move everything to one side: \(mx - y + b = 0\)
Generalizing:
- Add a parameter: \(mx + wy + b = 0\)
The Advantage:
- Vertical lines can be represented by setting \(w=0\)

Lines: Implicit Form (cont.)

Changing Notation:
- Use \((p_{1}, p_{2})\) instead of \((x, y)\)
- Use \((n_{1}, n_{2})\) instead of \((m, w)\)
The Result:
- \(n_{1}p_{1} + n_{2}p_{2} + b = 0\)
- In vector notation: \(\bs{n} \cdot \bs{p} + b = 0\)

Lines: Homogeneous Form

An Observation - We Can Divide by \(b\):
- \(\frac{n_{1}}{b}p_{1} + \frac{n_{2}}{b}p_{2} + 1 = 0\)
Substitute:
- \(h_{i}\) for \(\frac{n_{i}}{b}\)
The Result - Homogeneous Form:
- \(h_{1}p_{1} + h_{2}p_{2} + 1 = 0\)
- In vector notation: \(\bs{h} \cdot \bs{p} + 1 = 0\)

Lines: Homogeneous Form (cont.)

Given a Line Defined by \(\bs{h}\) and a Particular Point \(\bs{q}\) on that Line:
- \(\bs{h} \cdot \bs{q} = -1\)
It Follows That:
- \(\bs{h} \cdot \bs{q} = \bs{h} \cdot \bs{p}\) for all other points \(\bs{p}\) on that line
Subtracting:
- \(\bs{h} \cdot (\bs{p} - \bs{q}) = 0\) for all points \(\bs{p}\) on that line
- \(\bs{h} \cdot (\bs{p} - \bs{q}) \neq 0\) for all points \(\bs{p}\) NOT on that line

Halfspaces

Created by a Line

Halfspaces (cont.)

Given:
- A point \(\bs{q}\) on a line \(L\) defined by \(\bs{h}\)
Consider a Point \(\bs{p}\) with \(\bs{h} \cdot \bs{p} + 1 \gt 0\):
- Since \(\bs{h}\cdot\bs{q}+1=0\) and \(\bs{h}\cdot\bs{h} \gt 0\), it follows that \(\bs{h}\cdot(\bs{q}+\bs{h})+1\gt0\) and hence that \(\bs{p}\) must be in the same halfspace as \(\bs{q}+\bs{h}\) (which is not on the line)
Consider a Point \(\bs{p}\) with \(\bs{h} \cdot \bs{p} + 1 \lt 0\):
- Since \(\bs{h}\cdot\bs{q}+1=0\) and \(-\bs{h}\cdot\bs{h} \lt 0\), it follows that \(\bs{h}\cdot(\bs{q}-\bs{h})+1 \lt 0\) and hence that \(\bs{p}\) must be in the same halfspace as \(\bs{q}-\bs{h}\)
A Visualization:

Halfspaces (cont.)

Performing the Calculations:
- Using the implicit form eliminates some divisions (and all of the problems they can cause)
The Two Cases in Implicit Form:
- \(\bs{n} \cdot \bs{p} + b \gt 0\)
- \(\bs{n} \cdot \bs{p} + b \lt 0\)

Line Segments

Definition:
- The line segment formed by the two points \(\bs{p}, \bs{q} \in \mathbb{R}^{2}\) is the set of points \(\lambda \bs{p} + (1-\lambda) \bs{q}\) for all \(\lambda \in [0, 1]\)
Visualization:

Line Segments (cont.)

An Observation:
- The line segment is the set of convex combinations of \(\bs{p}\) and \(\bs{q}\)
Lines Revisited:
- If we allow \(\lambda\) to be outside of \([0,1]\) (i.e., we consider the barycentric combinations) then we have defined a line

Line Segments: Parametric Form

An Important Direction:
- \(\bs{v} = \bs{q} - \bs{p}\) is the direction from \(\bs{p}\) to \(\bs{q}\)
Deriving the Parametric Form Form:
- \((1 - \lambda) \bs{p} + \lambda \bs{q} = \bs{p} + \lambda \bs{p} + \lambda \bs{q} = \lambda (\bs{q} - \bs{p}) + \bs{p} = \lambda \bs{v} + \bs{p} \)
Some Intuition:
- We start at \(\bs{p}\) (when \(\lambda = 0\)) and move towards \(\bs{q}\) (when \(\lambda = 1\))
Lines Revisited Yet Again:
- If we allow \(\lambda\) to be outside of \([0,1]\) then we have the parametric form of a line

Line Segments: Implicit Form

Given:
- Two points on a line, \(\bs{p}\) and \(\bs{q}\)
To Implicit Form:
- \(\bs{n} = (\bs{p}-\bs{q})^{\perp}\) [i.e., \(n_{1} = -(p_{2} - q_{2})\) and \(n_{2} = (p_{1} - q_{1})\)]
- \(b = -(\bs{n} \cdot \bs{p})\)

Intersection of Lines

Given Two Lines in Implicit Form:
- \(m_{1} x + w_{1} y + b_{1} = 0\)
- \(m_{2} x + w_{2} y + b_{2} = 0\)
Given Two Lines Homogeneous Form:
- \(g_{1} x + h_{1} y + 1 = 0\)
- \(g_{2} x + h_{2} y + 1 = 0\)
Finding The Intersection:
- Solution of two equations in two unknowns (\(x\) and \(y\))
- Can be solved using the matrix inverse

Intersection of Lines (cont.)

Two Lines:
- \(a_{11} x_1 + a_{12} x_2 = b_1\)
- \(a_{21} x_1 + a_{22} x_2 = b_2\)
Two Lines in Matrix Notation:
- \(A x = b\)
Solving for \(x\):
- \(x = A^{-1} b\)

Intersection of Lines (cont.)

The Inverse of an \(n \times n\) Matrix:
- \(A^{-1} = \frac{1}{|A|} \text{adj}(A)\)
The Inverse for a 2x2 Matrix:
- When \(A = \left[ \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{matrix} \right]\)
- It follows that \(A^{-1} = \frac{1}{a_{11}a_{22} - a_{21}a_{12}} \left[ \begin{matrix}a_{22} & -a_{12} \\ -a_{21} & a_{11}\end{matrix} \right]\)
- So
  \(x_1 = \frac{1}{a_{11}a_{22} - a_{21}a_{12}} (a_{22}b_1 - a_{12}b_2)\)
  and
  \(x_2 = \frac{1}{a_{11}a_{22} - a_{21}a_{12}} (-a_{21} b_1 + a_{11} b_2)\)

Intersection of Lines (cont.)

One Difficulty:
- Division can be both "expensive" and sensitive
Another Difficulty:
- We often want to find the intersection of line segments (not lines)

Intersection of Lines (cont.)

Given Two Lines in Parametric Form:
- \(\mathcal{L}(\lambda) = \bs{p} + \lambda \bs{v}\)
- \(\mathcal{M}(\mu) = \bs{r} + \mu \bs{w}\)
Finding The Intersection:
- \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{ iff } \bs{p} + \lambda \bs{v} = \bs{r} + \mu \bs{w} \)
- That is, \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{iff } \lambda \bs{v} = (\bs{r} - \bs{p}) + \mu \bs{w} \)
Multiplying Both Sides by \(\bs{w}^{\perp}\):
- \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{ iff } \lambda \bs{v} \cdot \bs{w}^{\perp} = (\bs{r} - \bs{p}) \cdot \bs{w}^{\perp} + 0 \)
- That is, \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{ iff } \lambda \bs{v} \cdot \bs{w}^{\perp} = (\bs{r} - \bs{p}) \cdot \bs{w}^{\perp} \)
Multiplying Both Sides by \(\bs{v}^{\perp}\):
- \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{ iff } 0 = (\bs{r} - \bs{p}) \cdot \bs{v}^{\perp} + \mu \bs{w} \cdot \bs{v}^{\perp} \)
- That is, \(\mathcal{L}(\lambda) = \mathcal{M}(\mu) \mbox{ iff } \mu \bs{w} \cdot \bs{v}^{\perp} = (\bs{p} - \bs{r}) \cdot \bs{v}^{\perp} \)

Intersection of Lines (cont.)

Parallel Lines:
- \(\bs{v} \cdot \bs{w}^{\perp} = \bs{w} \cdot \bs{v}^{\perp} = 0\)
Otherwise:
- \(\lambda = \frac{(\bs{r}-\bs{p})\cdot \bs{w}^{\perp}}{\bs{v} \cdot \bs{w}^{\perp}} \)
- \(\mu = \frac{(\bs{p}-\bs{r})\cdot \bs{v}^{\perp}}{\bs{w} \cdot \bs{v}^{\perp}} \)

Intersection of Lines (cont.)

A Common Special Case:
- \(\bs{v} = \bs{q} - \bs{p}\) (i.e., the line segment with endpoints \(\bs{p}\) and \(\bs{q}\))
- \(\bs{w} = \bs{s} - \bs{r}\) (i.e., the line segment with endpoints \(\bs{r}\) and \(\bs{s}\))
Intepreting the Results:
- If \(\lambda \in [0,1]\) and \(\mu \in [0,1]\) then the line segments defined by \(p,q\) and \(r,s\) intersect. In this case, the two line segments intersect at the point \((1-\lambda)\bs{p} + \lambda \bs{q}\) or, equivalently, the point \((1-\mu)\bs{r} + \mu \bs{s}\)
- If \(\lambda \not\in [0,1]\) or \(\mu \not\in [0,1]\) then the line segments defined by \(p,q\) and \(r,s\) do not intersect but the line and line segment (or vice versa) do intersect.

Intersection of Lines (cont.)

Recall:
- We were trying to avoid division!
An Observation:
- If we don't need to find the point of intersection (just determine if they intersect or not) we needn't divide
Reinterpreting the Results for \(\lambda\) and \(\mu\):
- If (the numerator is 0) or ((the numerator and denominator have the same sign) and (the numerator is less than or equal to the denominator))) for both \(\lambda\) and \(\mu\) then the line segments intersect

Polyhedra

Definition:
- The intersection of a finite number of halfspaces
Visualization:

Polyhedra (cont.)

Bounded Polyhedron:
- There exists a \(k\) such that \(||\bs{p}|| \lt k\) for every point \(\bs{p}\) in the polyhedron.
Vertices (i.e., Extreme Points) of Bounded Polyhedra:

Polyhedra (cont.)

Representation of Bounded Polyhedra:
- Every point in a bounded polyhedron can be represented as a linear combination of the vertices
An Example:

Polyhedra (cont.)

Another Example:
Obviously:
- \(\bs{h} = \mu_{1} \bs{s} + \mu_{2} \bs{t}\) where \(\mu_{1}, \mu_{2} \in [0,1]\)
- \(\bs{p} = \lambda_{1} \bs{q} + \lambda_{2} \bs{h}\) where \(\lambda_{1}, \lambda_{2} \in [0,1]\)
Combining:
- \(\bs{h} = \mu_{1} \bs{s} + \mu_{2} \bs{t}\) where \(\mu_{1}, \mu_{2} \in [0,1]\)
- \(\bs{p} = \lambda_{1} \bs{q} + \lambda_{2} (\mu_{1} \bs{s} + \mu_{2} \bs{t}) = \lambda_{1} \bs{q} + \lambda_{2}\mu_{1} \bs{s} + \lambda_{2}\mu_{2} \bs{t} \) where \(\lambda_{1}, \lambda_{2}\mu_{1}, \lambda_{2}\mu_{2} \in [0,1]\)

Convex Polyhedra

Definition:
- A polyhedron is said to be convex if, for any two points in the polyhedron, all of the convex combinations of those two points are also in the polyhedron.
Visualization:
- The line segment connecting any two points in the polyhedron is in the polyhedron

Triangles

A "Loose" Definition:
- The intersection of three (appropriately constrained) halfspaces
An Observation:
- All triangles are convex

There's Always More to Learn