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 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 \(\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.
Intersection of Lines (cont.)
 Recall:
 We were tring 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
\(\alpha\) and \(\beta\):
 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 \(\alpha\) and \(\beta\)
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 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