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 SlopeIntercept 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\) 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}\)
 Consider a Point \(\bs{p}\) with
\(\bs{h} \cdot \bs{p} + 1 \lt 0\):
 Since \(\bs{h}\cdot\bs{q}+1=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 (cont.)
 A Related Form:
 Letting \(\bs{v} = \bs{p}  \bs{q}\) it follows that
 \(\lambda \bs{p} + (1\lambda) \bs{q} =
\lambda \bs{p} + \bs{q}  \lambda \bs{q} =
\lambda (\bs{p}  \bs{q}) + \bs{q} = \lambda \bs{v} + \bs{q}
\)
 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 (cont.)
 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\)
 \(w_{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:
 \(L(\alpha) = \bs{p} + \alpha \bs{v}\)
 \(M(\beta) = \bs{r} + \beta \bs{w}\)
 Finding The Intersection:
 \(L(\alpha) = M(\beta) \mbox{ iff } \bs{p} + \alpha \bs{v}
= \bs{r} + \beta \bs{w}
\)
 That is, \(L(\alpha) = M(\beta) \mbox{iff } \alpha \bs{v}
= (\bs{r}  \bs{p}) + \beta \bs{w}
\)
 Multiplying Both Sides by \(\bs{w}^{\perp}\):
 \(L(\alpha) = M(\beta) \mbox{iff }
\alpha \bs{v} \cdot \bs{w}^{\perp} = (\bs{r}  \bs{p})
\cdot \bs{w}^{\perp} + 0
\)
 That is, \(L(\alpha) = M(\beta) \mbox{iff }
\alpha \bs{v} \cdot \bs{w}^{\perp} = (\bs{r}  \bs{p})
\cdot \bs{w}^{\perp}
\)
 Multiplying Both Sides by \(\bs{v}^{\perp}\):
 \(L(\alpha) = M(\beta) \mbox{iff }
0 = (\bs{r}  \bs{p}) \cdot \bs{v}^{\perp}
+ \beta \bs{w} \cdot \bs{v}^{\perp}
\)
 That is, \(L(\alpha) = M(\beta) \mbox{iff }
\beta \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:
 \(\alpha = \frac{(\bs{r}\bs{p})\cdot \bs{w}^{\perp}}{\bs{v} \cdot \bs{w}^{\perp}}
\)
 \(\beta = \frac{(\bs{p}\bs{r})\cdot \bs{v}^{\perp}}{\bs{w} \cdot \bs{v}^{\perp}}
\)
Intersection of Lines (cont.)
 A 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 \(\alpha \in [0,1]\) and \(\beta \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\alpha)\bs{p} + \alpha \bs{q}\) or, equivalently,
the point \((1\beta)\bs{r} + \beta \bs{s}\)
 If \(\alpha \not\in [0,1]\) or \(\beta \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.
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 sigment connecting any two points in the polyhedron
is in the polyhedron
Triangles
 A "Loose" Definition:
 The intersection of three (appropriately constrained)
halfspaces
 An Observation:
There's Always More to Learn