25_Computational_Geometry.pdf
Lecture 25
Computational Geometry
EECS 281: Data Structures & Algorithms
Data Structures & Algorithms
Computational Geometry Overview
Raster (Bitmap) Graphics
Images on screen are represented by pixel arrays
Same idea works for storing images in files
• RGB: 3 colors per pixel, 1 byte per color
• An 1920×1080 image would require ~6.22MB
• Much larger files for high-res camera images
3
Vector Graphics Scale Better
4
Image Compression
• Lossy vs. lossless compression
• Flat background and sparse line graphics
compress well without losses
• Vector graphics compress even better
5
Basic Geometry Objects
Points, segments and lines in 2D and 3D
2D point: (x,y)
2D segment: two distinct points: {(x0, y0), (x1, y1)}
2D line: slope + intercept: (k, c) in y = k x + c
A segment defines a line
• Given two unequal points, solve for k, c
• Different segments may define the same line
• Must use floats or doubles, not ints
6
! = ($! − $”)/((! − (“)
) = $! − !(!
$! = !(! + )
$” = !(” + )
Geometry Transforms
Idea: modify all points & segments the same way
• Shifting/displacing point (x, y) by a vector (dx, dy)
(x, y) → (x + dx, y + dy)
• Scaling/stretching in the x dimension by C > 0
(x, y) → (C x, y)
• Mirroring in the x dimension
(x, y) → (-x, y)
• Rotation by angle θ
(x, y) → cos . − sin .sin . cos .
(
$ =
( cos . − $ sin .
( sin . + $ cos .
7
“Rotation Matrix”
Basic Geometry Questions
• Given two lines
– If they intersect, find their intersection point
• Given three points
– Do they lie on the same line? Find their triangle area?
– Are they ordered clockwise or counter-clockwise?
• Given point P and line L
– Does P lie on L? Find the point on L closest to P
• Given N points (1D, 2D, 3D)
– Find the smallest rectilinear bounding box of N points
– Find a closest pair of points
– Find a closest point among N to a given point A
8
Basic Geometry Questions
Two very different kinds of question
1. Deal with several points, lines, segments at
a time w/o considering algorithmic complexity
– Often solved by simple formulas or simple logic
2. Deal with collections of N points, lines,
segments;
need efficient algorithms in terms of N
– Often use simple formulas many times
9
Floating-Point Comparisons ==
General Rule 1: When comparing floating-
point values for equality, use approximate
comparisons.
Instead of using
if (a == b)
use
if (fabs(a – b) < epsilon)
for a suitable epsilon, for example
constexpr float epsilon = 0.0001;
10
Floating-Point Comparisons <,>
General Rule 2: When comparing floating-
point values for inequality, use approximate
comparisons.
Instead of using
if (a < b)
use
if (a < b + epsilon)
if (a < b - epsilon)
11
Data Structures & Algorithms
Computational Geometry Overview
Composite Geometry Objects
Pointsets and polygons
13
Composite Geometry Objects
2D and 3D meshes
Stored in files: points and segments
14
Application: Solid Modeling CAD
15
Data Structures & Algorithms
Points and Lines
Intersection of Two Lines (1)
Two lines given by their slope-intercept equations
y = ax + b and y = cx + d
• Check if the slopes are equal (a == c)
case: b == d (same line)
case: b != d (parallel lines, no intersection)
• If slopes are unequal (a != c), find the single
intersection point (x0, y0)
• y0 = ax0 + b = cx0 + d
• x0 = (d – b) / (c – a)
• y0 = ax0 + b
17
Intersection of Two Lines (2)
Two lines given by pairs of points
Same idea as before,
but more involved math
From Wikipedia:
Zero denominators → parallel lines
18
Segment Intersection Test (1)
Do two segments intersect?
19
Segment Intersection Test (2)
1. Find two lines formed by the segments
2. If the lines are parallel (same slope)
– But distinct (intercepts are ≠), return false
– And coincide (equal intercepts), check if
the segments’ X and Y projections overlap
3. Else, find the intersection point
– Check if it lies inside both segments
(by checking this for X and Y coordinates)
20
Collinear Points
Q: Do points P1, P2, P3 lie on the same line?
A: Check if the lines formed by segments
a = [P1, P2] and b = [P2, P3] are the same
1. Find slope-intercept {ka, ca} values from
the line segment [P1, P2]
2. Find slope-intercept {kb, cb} values from
the line segment [P2, P3]
3. Collinear if ka == kb and ca == cb
21
Distance from Point to a Line
• Given a point (x0, y0), find the shortest
distance to a line ax + by + c = 0
• Find the coordinates of the point on the
line closest to (x0, y0)
22*Source: Wikipedia
Min Bounding Box of a Pointset
23
Min Bounding Box of a Pointset
• Finding the minimum size BB is easy, IF
you stay parallel to x/y axes
– For each coordinate, find min and max, O(N)
• Usually a smaller BB exists without edges
parallel to x/y axes
Possible in O(N) time, but non-trivial algorithm
24
Data Structures & Algorithms
Points and Lines
Closest Pair of Points (1)
• Given N points, find two with min distance
– Direct O(N2)-time algorithm
• In 1D, O(N log N) time via sorting
• In 2D, use
Divide & Conquer:
– Left side
– Right side
– Middle strip
(alternate directions)
26
Closest Pair of Points (2)
Partitioning can be done using X-median
1. Recurse on the left half, find min dist
2. Recurse on the right half, find min dist
3. Additionally form
a middle strip
of width min-dist
4. Sort the strip by Y
5. Compare each pt
to 7 points after it
27
Closest Pair of Points (3)
Recursion is similar to that in Quick sort,
but with two linear terms – for partition and
for processing the middle strip
O(N log N) time
If sorting is used
to partition, we get
O(N log2 N) time
28
Finding Closest Point from N
• Given N points, we’d like to serve
the following type of queries
– For point P, find a closest point among N pts
(“the closest” would be misleading in general)
– To go beyond the obvious O(N2)-time
solution, build a data structure (a search
index)
• This problem has many applications
in databases, geospatial mapping, Internet
systems, computer-aided design etc
29
Data Structures & Algorithms
Polygons
Clockwise Test & Triangle Area
• Given three non-colinear points a, b, c
– Determine if they turn counterclockwise (left)
or clockwise (right)
– Find the area of the triangle they form
• Two problems solved by the same formula
“signed triangle area” is < 0 for “clockwise”
31
Area of a Polygon
• a polygon is given by n points (xi, yi)
• no segments are allowed to intersect
32
Area of a Polygon
A polygon with 5 points
33
Area of a Polygon
Break the polygon into
pieces, by drawing
vertical lines from
each point down to the
x-axis.
We’re left with nearly-
trapezoidal regions.
34
Area of a Trapezoid
Area of a trapezoid
with right angles:
35
! = # ℎ! + ℎ"2
Area of a Trapezoid
Area of a trapezoid
with right angles:
36
1 =
(" − (! $# + $"
2
Area of a Polygon
Remove the red shape from the green shape
to get the yellow shape
• Each trapezoid has a top edge in the polygon
• Each edge is the top of a trapezoid (red or green)
37
– =
=0
+1 -0 =1
-1
Area of a Polygon
• Unsigned Area
– Green trapezoids have xi < xi+1
! =
#! + #!"# %!"# − %!
2
– Red trapezoids have xi > xi+1
! =
#! + #!”# %! − %!”#
2
• Signed Area
– Green trapezoid have A > 0
– Red trapezoids have A < 0
! =
#! + #!"# %!"# − %!
2
38
– =
• For non-convex shapes, the
positive/negative regions can overlap.
• Some regions are double-counted (+ or -)
• It still works!
Area of a Polygon
39
– =
+2 -2 =0
+1 -0 =1-1
Area of a Polygon
• From Wikipedia: the Shoelace formula
The points are (x0, y0), (x1, y1), (x2, y2), …, (xn-1, yn-1), with (xn, yn) = (x0, y0) for convenience
* will be negative if the points are listed in counterclockwise order
• Punchline: computing AreaOf(polygon)
in linear time (in the number of points)
40
! =
1
2 %
!"#
$%&
&!'!'& −%
!"#
$%&
&!'&'!
The Shoelace Formula
41
Point Inside a Polygon (1)
Given a polygon (defined by N points) and a
point P, determine if P is inside the polygon.
42
Point Inside a Polygon (2)
Given a polygon (defined by N points) and a
point P, determine if P is inside the polygon.
43
Point Inside Polygon (3)
Project a horizontal line through the point
– Crosses an even number of segments: outside
– Crosses an odd number of segments: inside
44*Reminder: all comparisons use epsilon!
Point Inside Polygon (4)
The special cases when lines cross polygon’s
vertices can be handled by “wiggling” the points
up/down by epsilon.
45*Reminder: all comparisons use epsilon!
Data Structures & Algorithms
Polygons
Data Structures & Algorithms
Additional Topics
Computing Min & Max at Once
• Computing min of N values takes N - 1
comparisons
• Computing max of N values takes N - 1
comparisons
• However, both values can be computed
using 1 + ceil (3 * (N – 2) / 2) comparisons
– For each pair of input values, compare
the larger of the two with running max
and the smaller of the two with running min
48
k-d (k-dimensional) trees (1)
• A binary tree to represent coordinate data
• The data structure works in k dimensions,
but we will use k=2 for illustration
• Construction
– Pick one coordinate and partition all points
using the chosen value (linear time)
– Then recurse to each partition, but use a
different coordinate next
– Build a tree
49
k-d trees (2)
• Each tree node represents
a vertical or horizontal cut
– One point recorded @node
• Construction process takes
O(N log N) time
• Search takes O(log N) time
– Similar to binary search,
but alternates dimensions
50
Optional: Convex Hull
• Find the smallest polygon
enclosing the given pointset
• Intuition: if points are nails stuck in a
board, then a rubber band stretched
around the nails assumes the shape
of the convex hull, in O(1) time!
• Several algorithms find convex hull
of N points in 2D in O(N log N) time
– Can be accomplished with a sweeping line
51
Optional: Polygonal Operations
• Boolean ops on polygonal shapes:
– Union, intersection, set difference
• Polygonal shapes can represent
mechanical parts in software for
solid-modelling CAD
– These techniques can be extended
to 3D and also to smooth shapes
52
Data Structures & Algorithms
Additional Topics
Summary
• Geometric objects
– Basic: points, segments, lines
– Compound: pointsets, polygons, meshes
• Transforms: shifts, scaling, mirroring, rotation
• Geometric tests for points, segments, lines
• Efficient geometric algorithms
– Closest pair of points, closest-point queries
– Area of polygons, point-in-polygon test, etc
• Floating-point comparisons must use
epsilon 54
Interview Question
• Given n points, find a line through two of
the given points that divides the remaining
points into two halves, in O(n log n) time
• Assumptions to make it slightly easier:
– There are an even number of points
– No three points are collinear
• Hint: draw it out!
55