3 - Computational Geometry#
33.1 - Line-Segment Properties#
Vector Rotation Problem#
Given two vectors
The cross product
This results in the following cases:
If
, then is clockwise from with respect to the origin.If
, then is counterclockwise from with respect to the origin.If
, then and are colinear, meaning that they point in either the same or opposite directions.
Left/Right Turn Problem#
Given two consecutive line segments
This can be solved using the cross product, as shown in the previous example. In this case, we merely examine the vectors
If
is counterclockwise from , then it is a left turn.If
is clockwise from , then it is a right turn.
Line Segment Intersection Problem#
Do line segments
This can be solved using algebra, but it requires using division, which is costly and imprecise when done computationally. This can cause issues especially when the segments are nearly parallel.
Consider the walks from
If the line segments overlap, then we consider the segments to intersect. This must be handled separately.
SEGMENTS-INTERSECT(p1, p2, p3, p4)
d1 = DIRECTION(p3, p4, p1)
d2 = DIRECTION(p3, p4, p2)
d3 = DIRECTION(p1, p2, p3)
d4 = DIRECTION(p1, p2, p4)
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and
((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0))
return TRUE
elseif d1 == 0 and ON-SEGMENT(p3, p4, p1)
return True
elseif d2 == 0 and ON-SEGMENT(p3, p4, p2)
return True
elseif d3 == 0 and ON-SEGMENT(p1, p2, p3)
return True
elseif d4 == 0 and ON-SEGMENT(p1, p2, p4)
return True
else
return FALSE
DIRECTION(pi, pj, pk)
return (pk - pi) * (pj - pi)
ON-SEGMENT(pi, pj, pk)
if min(xi, xj) <= xk <= max(xi, xj) and
min(yi, yj) <= yk <= max(yi, yj)
return TRUE
else
return FALSE
33.2 - Determining Whether Any Pair of Segments Intersect#
Consider the problem above, but we have a collection of line segments rather than just one pair.
To solve this, we utilize a vertical sweep line.
This algorithm runs in
time, where is the number of line segments.This algorithm does not find all the intersections, it only finds whether one exists in the set.
The algorithm assumes that the set contains no vertical line segments, and that no intersection contains three line segments.
Imagine that this sweep line moves left to right through the space with the line segments.
Whenever we hit an endpoint of a line segment, we find the vertical order of the line segments going through that point (or rather, we add/delete the new/old point and check whether the order of the pairs have changed).
Sweeping algorithms typically manage two sets of data:
The sweep-line status gives the relationships among the objects that the sweep line intersects.
The event-point schedule is a sequence of points, called event points, which we order from left to right according to their
-coordinates. Whenever the sweep line reaches an event point, the sweep halts to process the event point, and then it resumes.
The sweep-line algorithm:
Sort the endpoints of all line segments by
-coordinate.If two endpoints are covertical (they have the same
-coordinate) we break the tie by putting all the covertical left endpoints before all the covertical right endpoints.If there is still a tie, we sort by increasing
-coordinates.
Whenever an event point is encountered, we perform a sweep.
When we encounter a left endpoint in a sweep, we insert the segment into the sweep-line status.
When we encounter a right endpoint in a sweep, we delete the segment from the sweep-line status.
When two segments first become consecutive in the total preorder, we check whether they intersect.
The sweep-line status is a total preorder
insert segment into . delete segment from . return the segment immediately above segment in . return the segment immediately below segment in .
If the input contains
Pseudocode#
The following algorithm takes as input a set
ANY-SEGMENTS-INTERSECT(S)
T = {}
sort the endpoints of the segments in S from left to right,
breaking ties by putting left endpoints before right endpoints
and breaking further ties by putting points with lower
y-coordinates first
for each point p in the sorted list of endpoints
if p is the left endpoint of a segment x
INSERT(T, s)
if (ABOVE(T, s) exists and intersects s)
or (BELOW(T, s) exists and intersects s)
return TRUE
if p is the right endpoint of a segment s
if both ABOVE(T, s) and BELOW(T, s) exist
and ABOVE(T, s) intersects BELOW(T, s)
return TRUE
DELETE(T, s)
return FALSE
33.3 - Finding the Convex Hull#
The convex hull of a set
This section covers Graham’s scan and Jarvis’s march as methods for computing the complex hull, which utilize a rotational sweep. Other methods include:
In the incremental method, we first sort the points from left to right, yielding a sequence
. At the th stage, we update the convex hull of the leftmost point, , according to the th point from the left, thus forming . This can be done in time.In the divide-and-conquer method, we divide the set of
points in time into two subsets, one containing the leftmost points and one containing the rightmost points, recursively compute the convex hulls of the subsets, and then, by means of a clever method, combine the hulls in time. The running time is described by the familiar recurrence , and so the divide-and-conquer method runs in time.The prune-and-search method is similar to the worst case linear-time median algorithm in Section 9.3. With this method, we find the upper portion (or upper chain) of the convex hull by repeatedly throwing out a constant fraction of the remaining points until only the upper chain of the convex hull remains. We then do the same for the lower chain. This method is asymptotically the fastest: if the convex hull contains
vertices, it runs in only time.
Graham’s Scan#
Graham’s scan solves the convex hull problem by maintaining a stack
GRAHAM-SCAN(Q)
let p0 be the point in Q with the minimum y-coordinate,
or the leftmost such point in case of a tie
let <p1, p2, ..., pm> be the remaining points in Q,
sorted by polar angle in counterclockwise order around p0
(if more than one point has the same angle, remove all but
the one that is farthest from p0)
let S be an empty stack
PUSH(p0, S)
PUSH(p1, S)
PUSH(p2, S)
for i = 3 to m
while the angle formed by points NEXT-TO-TOP(S), TOP(S),
and pi makes a nonleft turn
POP(S)
PUSH(pi, S)
return S
Graham’s scan runs in
Jarvis’s March#
Jarvis’s march computes the convex hull of a set of
Intuitively, Jarvis’s march simulates wrapping a taut piece of paper around the set
At each vertex visited in Jarvis’s march, we compute the point which has the most rightward angle with respect to the current vertex. In doing so, we build the right chain until we find the uppermost vertex. From here, we do the same on the way down to find the left chain. Once this is completed, the convex hull is found.
33.4 - Finding the Closest Pair of Points#
A brute force approach to finding the closest pair of points in a set
In this section, we use a divide-and-conquer algorithm, whose runtime is given by the recurrence
The Divide-and-Conquer Algorithm#
Each recursive iteration takes as input a subset
A given recursive invocation with inputs
Divide: Find a vertical line
that bisects the point set into two sets and such that all points in are on or to the right of . Divide the array into and , which contain the points of and respectively, sorted by monotonically increasing -coordinate. Similarly, divide the array into arrays and , which contain the points of and respectively, sorted by monotonically increasing -coordinate.Conquer: Having divided
into and , make two recursive calls, one to find the closest pair of points in and the other to find the closest pair of points in . The inputs to the first call are the subset and arrays and ; the second call receives the inputs , , and . Let the closest-pair distances returned for and be and , respectively, and let .Combine: The closest pair is either the pair with distance
found by one of the recursive calls, or it is the pair of points with one point in and the other in . The algorithm determines whether there is a pair with one point in and the other point in and whose distance is less than . Observe that if a pair of points has distance less than , both points of the pair must reside within units of line . To find such a pair, if it exists, we do the following:Create an array
, which is the array with all points not in the -wide vertical strip removed. The array is sorted by -coordinate, just as is .For each point
in the array , try to find points in that are within units of . Only the 7 points in that follow need to be considered. Compute the distance from to each of these 7 points, and keep track of the closest-pair distance found over all pairs in .If
, then the vertical strip does indeed contain a closer pair than the recursive calls found. Return this pair and its distance . Otherwise, return the closest pair and its distance found by the recursive calls.
When implemented correctly, the divide-and-conquer approach achieves