- Forward


Analytic Geometry
An Introduction to Shapes in the Plane


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward

Created by a Line

halfspace
Halfspaces (cont.)
Back SMYC Forward
  • 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:
    • halfspace-test
Halfspaces (cont.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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-segment
Line Segments (cont.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • Definition:
    • The intersection of a finite number of halfspaces
  • Visualization:
    • polyhedron-halfspaces
Polyhedra (cont.)
Back SMYC Forward
  • 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:
    • polyhedron-vertices
Polyhedra (cont.)
Back SMYC Forward
  • Representation of Bounded Polyhedra:
    • Every point in a bounded polyhedron can be represented as a linear combination of the vertices
  • An Example:
    • polyhedron-representation1
Polyhedra (cont.)
Back SMYC Forward
  • Another Example:
    • polyhedron-representation2
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • A "Loose" Definition:
    • The intersection of three (appropriately constrained) halfspaces
  • An Observation:
    • All triangles are convex
There's Always More to Learn
Back -