Chapter 17: Computational Geometry. 25 sections.
25 items
You need a mathematical representation for locations, directions, distances, and geometric relationships.
Many geometric algorithms must determine whether three points form a left turn, a right turn, or lie on the same line.
Given two lines or two line segments, determine whether they intersect and, if they do, compute the intersection point.
Given a polygon described by its vertices, compute its area efficiently and accurately.
Given a polygon and a query point, determine whether the point lies: ```text inside the polygon outside the polygon
Given a set of points, compute the smallest convex polygon that contains all of them.
After constructing a convex hull, many geometric questions remain: * What is the maximum distance between any two points?
Given a set of points in the plane, find the pair with the smallest Euclidean distance.
Many geometric problems involve detecting interactions among large collections of geometric objects.
You need to solve geometric problems that can be reduced to one-dimensional intervals.
Given a set of axis-aligned rectangles, compute the total area covered by their union.
Given a collection of half-planes, compute their common intersection.
Given a set of points, partition the plane into regions so that every location belongs to the region of its nearest point.
Given a set of points in the plane, construct a triangulation that avoids thin, poorly shaped triangles as much as possible.
Geometric algorithms often look exact on paper but fail in code because numeric computations are approximate.
Many computational geometry problems use coordinates that are naturally integers: ```text grid maps pixels
Some geometric problems cannot stay entirely in integer arithmetic.
You need a fast way to group or search geometric objects by location.
You need to search large collections of geometric objects efficiently.
Most real-world geometry software is not built from a single algorithm.
After studying individual geometric algorithms, it is tempting to view them as unrelated techniques.
Geometric algorithms are easy to test visually and surprisingly easy to get wrong.
Geometry code fails in ways that ordinary examples rarely expose.
Many geometric algorithms are already asymptotically optimal.
Individual geometry algorithms are useful, but real systems usually require several of them working together.