Computational geometry designs algorithms for geometric objects: points, segments, polygons, circles and higher-dimensional shapes. It answers questions such as which points lie inside a region, what is the nearest neighbour, or how to mesh a surface. Maps, graphics, robotics, CAD and games all depend on it.
Key concepts
- Orientation test: the sign of a cross product says whether three points turn left or right; most algorithms are built on it.
- Convex hull: the smallest convex shape containing a set of points, found in O(n log n) by Graham scan or similar.
- Sweep line: move an imaginary line across the plane and keep only the objects it touches; it finds segment intersections.
- Triangulation and Voronoi diagrams: Delaunay triangulation and its dual divide space by proximity.
- Spatial indexes: k-d trees, quadtrees and R-trees speed up range and nearest-neighbour queries.
Vocabulary
- Degeneracy: a special case, such as three collinear points, that breaks naive code.
- Robust predicates: tests that give the right answer even with rounding error, using exact or adaptive arithmetic.
- Polygon: a closed chain of segments; simple means it does not cross itself.
- Duality: a transformation that turns points into lines and back, making some problems easier.
What to study, in order
- Vectors, dot and cross products, and the orientation test.
- Implement the convex hull of random points and plot it.
- Test whether a point lies inside a polygon and whether two segments intersect.
- Learn the sweep line and build a Delaunay triangulation, then draw its Voronoi dual.
- Add a k-d tree for nearest-neighbour search and check it against brute force.
Related tags
#algorithms #computer-graphics #data-structures #spatial-data #linear-algebra