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:
- Solving for \(x\):
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:
