Geometry

Geometric primitives and operations for planar algorithms.

Headers

Header	Summary
circle_geometry.hpp	Circle intersections, line intersections, tangent points, common tangents, and circumcircles.
closest_pair.hpp	Return indices of a closest pair in O(n log n).
convex_layers.hpp	Return the one-based onion layer of every distinct point. Two decremental hull structures maintain the left and right boundary chains; deleting the current boundary from both structures exposes the next layer.
euclidean_mst.hpp	Return a Euclidean minimum spanning tree on integral planar points. Divide-and-conquer Delaunay triangulation keeps only O(n) candidate edges: the empty-circumcircle property guarantees that every Euclidean MST edge is present. Kruskal on squared lengths then selects the tree; duplicate points are connected by explicit zero-length edges.
furthest_pair.hpp	Return indices of a furthest pair in O(n log n).
geometry_base.hpp	Planar point primitives, orientation tests, and convex hull construction.
half_plane_intersection.hpp	Directed boundary whose feasible half-plane is on its left side.
minimum_enclosing_circle.hpp	Return the minimum circle and one boundary support set. Randomly ordering the points makes the expected number of constraint rebuilds linear: an outside point must belong to the new boundary, reducing the remaining problem successively to circles through one, two, then three fixed points.
minkowski_sum.hpp	Minkowski sum of two point sets as a strict counter-clockwise convex polygon in O((n+m) log(n+m)), including degenerate point and segment cases.
rectangle_union_area.hpp	Exact union area of half-open axis-aligned integer rectangles by a sweep line and covered-length segment tree in O(n log n).
triangle_point_counter.hpp	Count points strictly inside triangles whose vertices come from a fixed set. For every upward-directed vertex pair, preprocessing counts points at intermediate heights strictly left of its supporting line and on that line. Horizontal-ray counts are stored at each vertex as well. Sorting a query's three vertices by (y, x) decomposes its open interior into a signed combination of at most three such half-open strips and one horizontal ray, with line and vertex equality counts removing every boundary point.