- 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 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 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 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 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 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 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 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 Forward

Created by a Line

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