Computational Geometry

Geometry in code starts with two objects: a point, which is a position, and a vector, which is the difference between two points. Almost everything after that reduces to one of two products. The dot product is positive when two vectors point the same general way, zero when they are perpendicular, negative when they oppose. The 2D cross product of (b - a) and (c - a) is twice the signed area of triangle abc, and its sign says whether the turn at b goes left, right or straight on.

That sign is the orientation test, and it carries the whole category. Two segments cross when each straddles the other's line, which is four orientation tests and no division. A polygon's area is half the absolute value of the summed cross products of consecutive vertices. A convex hull is built by sorting the points once and then walking them with a stack, popping any vertex where the turn goes the wrong way: monotone chain sorts by x and builds a lower and an upper chain, Graham scan sorts by angle around the lowest point, and both cost O(n log n) with the sort as the dominant term.

Two patterns cover the rest. Divide and conquer splits the points by x, solves each half, and then compares only the points inside a narrow strip around the divider, which brings closest pair down to O(n log n) from the n^2 of all pairs. A sweep line moves across the plane, keeps an active set of whatever it currently crosses, and does work only at event points, which finds k segment intersections in O((n + k) log n) instead of testing every pair.

After this you can

• Compute a dot product and a cross product and say what each sign means
• Decide whether two segments intersect using orientation tests alone
• Build a convex hull by sorting the points and popping the wrong turns
• Compare squared distances so that no square root enters the comparison
• Recognise when a sweep line replaces a comparison of every pair