(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.
- Is a segment clockwise or counterclockwise from another that shares an endpoint?
- Which way do we turn when traversing two adjoining line segments?
- 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.
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.
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
- A technique used in an O(n log n)-time algorithm for determining whether a set of n line segments contains any intersections.
- 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.