• i. Points, Vectors and Orientation: the point/vector struct, cross and dot products, orientation, angular sorting, and the integer-vs-floating-point rules everything else depends on.
• ii. Lines and Segments: line and segment intersection (exact and constructed), the implicit form, and robust point-in-polygon ray casting.
• iii. Triangles: centroid, incenter, circumcenter, orthocenter, the Euler line, Euler’s $O{I}^2=R(R-2r)$, Heron’s formula, and medians.
• iv. Polygons: shoelace area and centroid, Pick’s theorem, floor sums, and point/segment-in-polygon tests.
• v. Convex Hull: Andrew’s monotone chain, Graham scan, Melkman’s online hull, convex layers, and the Chan / Kirkpatrick-Seidel output-sensitive algorithms.
• vi. Dynamic Convex Hull: maintaining the hull of a growing point set with upper/lower chains in a balanced map, $O(\log n)$ amortised per insert.
• vii. Rotating Calipers: diameter, minimum bounding rectangle, and the distance between two convex polygons via the Minkowski difference.
• viii. Convex Polygon Queries and Tangents: $O(\log n)$ extreme vertex, tangents from a point, and line-hull intersection via cyclic binary search; circle and polygon tangent lines.
• ix. Half-Plane Intersection: the angular-sweep deque algorithm, its duality with convex hulls, and when to fall back to incremental clipping.
• x. Minkowski Sum: merging edges by angle, collision detection via the Minkowski difference, and max-plus convolution of concave sequences.
• xi. Polygon Clipping and Union: Sutherland-Hodgman clipping, ear-clipping triangulation, affine transforms, and the area of a union of overlapping polygons.
• xii. Circles and Inversion: circle-line and circle-circle intersection, the radical axis, lens area, and circle inversion.
• xiii. Circle Union and Angular Sweep: the area of a union of circles via Green’s theorem, the maximum-points-in-a-circle sweep, and exact angle arithmetic with a turn counter.
• xiv. Minimum Enclosing Circle: Welzl’s randomised incremental algorithm and the LP-type framework it exemplifies.
• xv. Sweep Line and Segment Intersections: the rectangle-union segment tree template, Shamos-Hoey, and a full Bentley-Ottmann implementation.
• xvi. Closest Pair: the sweep-with-a-set method, the randomised grid algorithm, and Bentley-Shamos divide and conquer with the seven-point lemma.
• xvii. Manhattan Geometry: the 45-degree rotation trick to Chebyshev distance, sums of pairwise distances, and the Manhattan MST.
• xviii. Point Location and Point Counting: the segment-below-a-query sweep, counting points inside a triangle with an angular-sweep Fenwick tree, and maximum collinear points.
• xix. 3D Geometry and 3D Hull: 3D primitives, planes, distances, volumes, and an incremental 3D convex hull with area and volume.
• xx. Delaunay and Voronoi: why Delaunay is the optimal triangulation, the paraboloid lifting trick, Bowyer-Watson and Fortune’s algorithm, and the Voronoi duality.
• xxi. Planar Graphs and Faces: listing the faces of a planar straight-line embedding by walking each directed edge to the next in angular order.