Geometry

Planar and three-dimensional primitives, polygons, and circles.

Headers

Header	Summary
circle_geometry.hpp	Circle intersections, line intersections, tangent points, common tangents, and circumcircles.
circle_polygon_area.hpp	Area of intersection of two closed disks with nonnegative radii. Uses long double; inputs and intermediate squared lengths/areas must be finite.
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.
convex_polygon.hpp	Preprocess a convex boundary for logarithmic point location. The input is in clockwise or counter-clockwise boundary order. Consecutive duplicates, a repeated closing point, and redundant collinear vertices are removed in O(n). Collinear input becomes its two extreme points. For integral coordinates, all determinant products/differences must fit in signed 128 bits; floating coordinates use exact long-double comparisons.
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_3d.hpp	Three-dimensional point/vector with lexicographic order. Vector arithmetic and products use T; choose T wide enough for intermediate products. Metric operations convert coordinates before subtracting them.
geometry_base.hpp	Planar point primitives, orientation tests, and convex hull construction.
geometry_distance.hpp	Project p onto the infinite line through a and b. A zero-length defining pair returns nullopt. Coordinates are converted before arithmetic; results use long double and are subject to floating-point precision.
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.