Computational Geometry in C++

What you will be able to do

• Write geometric predicates that stay correct on degenerate and nearly degenerate input
• Implement convex hulls, polygon triangulation and Delaunay triangulation from scratch, and explain their complexity
• Detect segment intersections with a sweep line and clip polygons
• Answer range and nearest-neighbor queries with k-d trees and quadtrees
• Represent meshes with the half-edge structure and edit them safely
• Read the design of CGAL (kernels, exact predicates) and know when to reach for it

Who it is for

• CAD, GIS and mesh-processing developers who need geometry code they can trust
• Game, physics and robotics programmers working with collision and spatial queries
• Competitive programmers who are tired of skipping the geometry problem
• Graduate students who want to run the textbook algorithms, not only read them

Before you start

• Templates & Generic Programming
• STL & Algorithms
• Memory & Resources

The course project

Across the course you build a small 2D geometry toolkit: exact predicates, convex hull, polygon operations, triangulation and a k-d tree. Each lesson's programs are self-contained and draw their results as pictures in the output panel. The last lesson assembles the pieces into one program with a test harness, so you finish with code you can paste into your own project.

Lessons

1. 1Points, Vectors and the Orientation PredicateFree sampleThe one question almost every geometry algorithm asks, "which side of the line is this point on?", answered with a sign instead of an angle.30 min
2. 2Floating-Point Robustness: Epsilons, Exact Predicates and FiltersWhy the orientation test gives wrong signs in double, why an epsilon does not fix it, and how a filtered predicate with an exact fallback does.40 min
3. 3Segment Intersection and the Sweep LineDecide exactly whether two segments meet, in every degenerate case, then find whether any of n segments intersect in O(n log n) with the Shamos-Hoey sweep.35 min
4. 4Convex Hulls: Graham Scan, Monotone Chain and QuickHullBuild the convex hull with Andrew's monotone chain, compare it with Graham scan, Jarvis march and QuickHull by counting their work, and test every degenerate case.40 min
5. 5Polygons: Area, Winding and Point-in-PolygonExact polygon area with the shoelace formula, a convexity test that rejects stars, and point-in-polygon that stays right when the ray hits a vertex.45 min
6. 6Triangulating a Polygon: Ear ClippingCut any simple polygon into n - 2 triangles with exact ear clipping, check the result without trusting it, and place art gallery guards by 3-coloring.40 min
7. 7Delaunay Triangulation and Voronoi DiagramsBuild the Delaunay triangulation of a point set with Bowyer-Watson on an exact in-circle predicate, verify it by brute force, and read the Voronoi diagram off its dual.40 min
8. 8Spatial Indexes: k-d Trees and QuadtreesAnswer range and nearest-neighbor queries over many points without scanning them all, with k-d trees, point-region quadtrees and packed R-trees, and know when each one fails.40 min
9. 9Closest Pair and Nearest-Neighbor QueriesFind the two closest points among a million in O(n log n) by divide and conquer or a sweep, or in expected O(n) with a randomized grid, and answer nearest-neighbor queries with a grid.40 min
10. 10Polygon Clipping: Sutherland-Hodgman and Boolean OperationsClip segments and polygons against windows with Liang-Barsky and Sutherland-Hodgman, intersect half-planes, and see why rounded intersection points and touching edges make general Boolean operations hard.40 min
11. 11Meshes and the Half-Edge Data StructureStore a triangle mesh so that "what is across this edge?" and "what surrounds this vertex?" take constant time, check it with Euler's formula, and flip edges until the mesh is Delaunay.45 min
12. 12Project: A Small, Robust 2D Geometry ToolkitAssemble the course's algorithms into one tested C++ program with a single coordinate contract, check every part against an independent reference, and learn when to reach for CGAL or Boost.Geometry instead.25 min