Computational Geometry

(Abridged notes from Introduction to Algorithms)

Branch of CS that studies algorithms for solving geometric problems. Input is typically a set of points, a set of line segments, or the vertices of a polygon in counterclockwise order. Output is often a response to a query about the objects, such as whether any lines intersect, or finding a new geometric object (e.g. convex hull) of the set of points.

We look at computational-geometry algorithms in two dimensions (2D), i.e. in the plane. Each object is represented by a set of points {P1, P2, P3, ...}, where each Pi = (Xi, Yi). For example, an n-vertex polygon P = <P0, P1, P2, ..., Pn-1>.

Computational geometry can also apply to higher dimensions, but such problems and their solutions can be very difficult to visualize.

Line-segment properties

1. Is a segment clockwise or counterclockwise from another that shares an endpoint?
2. Which way do we turn when traversing two adjoining line segments?
3. Do two line segments intersect?

Cross product lies at the heart of our line-segment methods. The cross product is the determinant of a matrix.

P1 x P2 = det

X_1	X_2
Y_1	Y_2

= X1 Y2 - X2 Y1

= -P2 x P1

If P1 x P2 is positive, then P1 is clockwise from P2 w.r.t. the origin (0,0), otherwise counterclockwise.

If P1 x P2 is 0, the vectors are colinear, pointing in the same or opposite directions.

Determining whether consecutive segments turn left or right

Do two consecutive line segments P0P1 and P1P2 turn left or right at P1? Or, which way angle L P0P1P2 turns.

Use the cross product, don't even need to compute the angle. Compute the cross product (P2 - P0) x (P1 - P0). If the sign is negative, P0P2 is counterclockwise w.r.t P0P1, thus a left turn at P1. If positive, clockwise orientation and a right turn. If 0, P0, P1, P2 are colinear.

Determining whether two line segments intersect

Straightforward method: compute the line equation of the form y = mx + b for each segment (m is the slope and b is the y-intercept). Find the point of intersection on the lines. Check whether this point is on both segments (uses division to find POI). NOTE: can be inaccurate when segments are nearly parallel, due to precision of division on computers.

TODO

"Sweeping"

• A technique used in an O(n log n)-time algorithm for determining whether a set of n line segments contains any intersections.

Finding the convex hull ("Rotational-sweep")

• Algorithms for computing the convex hull (smallest enclosing convex polygon) of a set of n points.
• Graham's scan: O(n log n) time.
• Jarvis's march: O(n h) time, where h is the number of vertices of the convex hull.

Finding the closest pair of points