Computational geometry algorithms. More...

#include <sstream>
#include <polygon.H>
#include <htlist.H>
#include <tpl_dynDlist.H>
#include <tpl_dynSetTree.H>
#include <tpl_arrayQueue.H>
#include <tpl_arrayStack.H>
#include <tpl_sort_utils.H>
#include <tpl_2dtree.H>
#include <ah-errors.H>
#include <algorithm>
#include <utility>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <memory>
#include <limits>
#include <cmath>
#include <ah-unique.H>
#include <tpl_dynBinHeap.H>

Include dependency graph for geom_algorithms.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::GeomPolygonUtils
	Shared polygon helpers used across multiple geometry algorithms. More...

class	Aleph::GeomTriangleAdjacencyUtils
	Shared edge-group extraction for triangle meshes. More...

struct	Aleph::GeomTriangleAdjacencyUtils::EdgeRef
	Represents a reference to a triangle edge. More...

class	Aleph::GeomBowyerWatsonUtils
	Shared Bowyer-Watson core parameterized by in-circle predicate. More...

struct	Aleph::GeomBowyerWatsonUtils::WorkTriangle

struct	Aleph::GeomBowyerWatsonUtils::UndirectedEdge

struct	Aleph::GeomBowyerWatsonUtils::CmpUndirectedEdge

class	Aleph::CuttingEarsTriangulation
	Polygon triangulation using the ear-cutting algorithm. More...

class	Aleph::ClosestPairDivideAndConquer
	Closest pair of points via divide and conquer. More...

struct	Aleph::ClosestPairDivideAndConquer::Result

struct	Aleph::ClosestPairDivideAndConquer::LexicographicCmp
	Strict weak order for sorting points lexicographically by (x,y). More...

struct	Aleph::ClosestPairDivideAndConquer::ByYCmp
	Strict weak order for sorting points by (y,x). More...

class	Aleph::MinimumEnclosingCircle
	Smallest circle enclosing a point set (Welzl's algorithm). More...

struct	Aleph::MinimumEnclosingCircle::Circle
	Result type: a circle defined by center and squared radius. More...

class	Aleph::RotatingCalipersConvexPolygon
	Rotating calipers metrics for convex polygons. More...

struct	Aleph::RotatingCalipersConvexPolygon::DiameterResult

struct	Aleph::RotatingCalipersConvexPolygon::WidthResult

class	Aleph::PointInPolygonWinding
	Exact point-in-polygon classification via winding number. More...

class	Aleph::ConvexPolygonIntersectionBasic
	Basic exact intersection for closed convex polygons. More...

class	Aleph::HalfPlaneIntersection
	Exact bounded intersection of half-planes. More...

struct	Aleph::HalfPlaneIntersection::HalfPlane

class	Aleph::DelaunayTriangulationBowyerWatson
	Exact Delaunay triangulation using the Bowyer-Watson incremental algorithm. More...

struct	Aleph::DelaunayTriangulationBowyerWatson::IndexedTriangle
	Represents a triangle by the indices of its three vertices. More...

struct	Aleph::DelaunayTriangulationBowyerWatson::Result
	The result of a Delaunay triangulation. More...

class	Aleph::RegularTriangulationBowyerWatson
	Exact regular triangulation (weighted Delaunay) via Bowyer-Watson. More...

struct	Aleph::RegularTriangulationBowyerWatson::WeightedSite
	A 2-D site with an associated weight (squared radius). More...

struct	Aleph::RegularTriangulationBowyerWatson::Result

class	Aleph::DelaunayTriangulationRandomizedIncremental
	O(n log n) expected-time Delaunay's triangulation. More...

struct	Aleph::DelaunayTriangulationRandomizedIncremental::Tri

struct	Aleph::DelaunayTriangulationRandomizedIncremental::DagNode

class	Aleph::ConstrainedDelaunayTriangulation
	Constrained Delaunay Triangulation via Sloan's flip-based method. More...

struct	Aleph::ConstrainedDelaunayTriangulation::IndexedEdge

struct	Aleph::ConstrainedDelaunayTriangulation::Result

struct	Aleph::ConstrainedDelaunayTriangulation::Tri

struct	Aleph::ConstrainedDelaunayTriangulation::CrossingEdge
	Collect edges that cross segment (u,v) by scanning all mesh edges. More...

class	Aleph::VoronoiDiagramFromDelaunay
	Voronoi diagram derived as the dual of a Delaunay triangulation. More...

struct	Aleph::VoronoiDiagramFromDelaunay::Edge
	Represents an edge in the Voronoi diagram. More...

struct	Aleph::VoronoiDiagramFromDelaunay::Cell
	Represents a Voronoi cell. More...

struct	Aleph::VoronoiDiagramFromDelaunay::ClippedCell
	Represents a Voronoi cell clipped by a bounding polygon. More...

struct	Aleph::VoronoiDiagramFromDelaunay::Result
	The complete result of a Voronoi diagram computation. More...

class	Aleph::VoronoiDiagram
	O(n log n) Voronoi diagram construction. More...

class	Aleph::VoronoiDiagramFortune
	Fortune sweep-line Voronoi construction. More...

struct	Aleph::VoronoiDiagramFortune::Event
	Forward declaration of beach-line arc. More...

struct	Aleph::VoronoiDiagramFortune::Arc
	Arc in the beach-line state structure. More...

struct	Aleph::VoronoiDiagramFortune::EventCmp
	Comparator for prioritizing events in the sweep-line. More...

struct	Aleph::VoronoiDiagramFortune::TriKey
	Key for identifying a triangle by its vertex indices. More...

class	Aleph::AndrewMonotonicChainConvexHull
	Andrew's monotonic chain convex hull algorithm. More...

struct	Aleph::AndrewMonotonicChainConvexHull::LexicographicCmp
	Lexicographical comparison for points (x primary, y secondary). More...

class	Aleph::GrahamScanConvexHull
	Graham scan convex hull algorithm. More...

struct	Aleph::GrahamScanConvexHull::LexicographicCmp
	Lexicographical comparison for points. More...

class	Aleph::BruteForceConvexHull
	Brute force convex hull algorithm. More...

struct	Aleph::BruteForceConvexHull::CmpSegment
	Comparator for segments to ensure strict weak ordering in sets. More...

class	Aleph::GiftWrappingConvexHull
	Gift wrapping (Jarvis march) convex hull algorithm. More...

class	Aleph::QuickHull
	QuickHull convex hull algorithm. More...

class	Aleph::SegmentSegmentIntersection
	Dedicated exact intersection for a single pair of segments. More...

struct	Aleph::SegmentSegmentIntersection::Result
	Detailed result of a segment-segment intersection test. More...

class	Aleph::LineSweepFramework< Event, CmpEvent >
	Reusable event-driven sweep line framework. More...

struct	Aleph::LineSweepFramework< Event, CmpEvent >::SeqEvent
	Internal event wrapper that adds a sequence number for tie-breaking. More...

struct	Aleph::LineSweepFramework< Event, CmpEvent >::CmpSeqEvent
	Comparator for SeqEvent, ensuring a strict weak ordering. More...

class	Aleph::SweepLineSegmentIntersection
	Report all pairwise intersection points among a set of segments. More...

struct	Aleph::SweepLineSegmentIntersection::Intersection
	A single intersection record. More...

struct	Aleph::SweepLineSegmentIntersection::Event
	Represents an event in the sweep-line algorithm. More...

struct	Aleph::SweepLineSegmentIntersection::EventLess
	Functor wrapper for event_less (used by LineSweepFramework). More...

class	Aleph::SweepLineSegmentIntersection::StatusTree
	Sweep-line status as a balanced tree with O(log n) updates. More...

struct	Aleph::SweepLineSegmentIntersection::StatusTree::Node

class	Aleph::MonotonePolygonTriangulation
	O(n log n) triangulation of simple polygons via y-monotone partition + linear-time monotone triangulation. More...

class	Aleph::MonotonePolygonTriangulation::EdgeStatusTree

struct	Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node

class	Aleph::MinkowskiSumConvex
	Exact Minkowski sum of two closed convex polygons. More...

class	Aleph::ConvexPolygonDistanceGJK
	Distance between two closed convex polygons using GJK. More...

struct	Aleph::ConvexPolygonDistanceGJK::Result
	Holds the results of the distance computation. More...

struct	Aleph::ConvexPolygonDistanceGJK::SupportPoint
	A point in the Minkowski difference and its source components. More...

struct	Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult

class	Aleph::KDTreePointSearch
	Spatial point index for O(log n) nearest-neighbor queries. More...

struct	Aleph::KDTreePointSearch::DebugPartition
	Represents a spatial partition or leaf in the KD-tree. More...

struct	Aleph::KDTreePointSearch::DebugSnapshot
	A complete snapshot of the tree for debugging. More...

class	Aleph::ConvexPolygonDecomposition
	Decompose a simple polygon into convex parts using Hertel-Mehlhorn. More...

class	Aleph::RangeTree2D
	Static 2D range tree for orthogonal range queries. More...

struct	Aleph::RangeTree2D::DebugNode
	Represents a node in the range tree for debugging. More...

struct	Aleph::RangeTree2D::DebugSnapshot
	A complete snapshot of the range tree for debugging. More...

struct	Aleph::RangeTree2D::Node
	Internal node structure containing the y-sorted secondary array. More...

class	Aleph::ConvexPolygonOffset
	Inward (erosion) and outward (dilation) offset of convex polygons. More...

class	Aleph::PolygonOffset
	Offset (inflate/deflate) an arbitrary simple polygon. More...

struct	Aleph::PolygonOffset::Result
	The result of an offset operation, which may produce multiple polygons. More...

struct	Aleph::PolygonOffset::Intersection
	Intersection found between edge i and edge j of the raw polygon. More...

struct	Aleph::PolygonOffset::AugVertex
	Augmented vertex in the cleaned polygon. More...

class	Aleph::VisibilityPolygon
	Compute the visibility polygon from a point inside a simple polygon. More...

class	Aleph::VisibilityPolygon::EdgeStatusTree
	BST-based sweep status for active edges, ordered by ray-intersection distance. More...

struct	Aleph::VisibilityPolygon::EdgeStatusTree::EdgeKey

struct	Aleph::VisibilityPolygon::EdgeStatusTree::EdgeKeyCmp

class	Aleph::ShortestPathInPolygon
	Compute the shortest Euclidean path between two points inside a simple polygon. More...

struct	Aleph::ShortestPathInPolygon::ITri

class	Aleph::SegmentArrangement
	Compute the full planar subdivision induced by a set of segments. More...

struct	Aleph::SegmentArrangement::ArrEdge
	Represents an edge in the planar subdivision. More...

struct	Aleph::SegmentArrangement::ArrFace
	Represents a face (region) in the planar subdivision. More...

struct	Aleph::SegmentArrangement::Result
	The complete result of the segment arrangement computation. More...

struct	Aleph::SegmentArrangement::HalfEdge
	Internal half-edge structure used for face traversal. More...

class	Aleph::AlphaShape
	Alpha shape of a point set. More...

struct	Aleph::AlphaShape::Result
	Result of an alpha-shape computation. More...

class	Aleph::PowerDiagram
	Power diagram (weighted Voronoi diagram). More...

struct	Aleph::PowerDiagram::WeightedSite
	A site with an associated weight (squared radius). More...

struct	Aleph::PowerDiagram::PowerEdge
	Represents an edge in the power diagram. More...

struct	Aleph::PowerDiagram::PowerCell
	Represents a cell in the power diagram. More...

struct	Aleph::PowerDiagram::Result
	Complete result of a power diagram computation. More...

class	Aleph::BezierCurve
	Quadratic and cubic Bézier curves with exact rational arithmetic. More...

struct	Aleph::BezierCurve::SplitResult
	De Casteljau subdivision: split a cubic Bézier at parameter t into two cubic Béziers (left and right). More...

class	Aleph::BooleanPolygonOperations
	Boolean operations on simple polygons (union, intersection, difference) using the Greiner-Hormann algorithm. More...

struct	Aleph::BooleanPolygonOperations::GHNode

struct	Aleph::BooleanPolygonOperations::IsectPair
	Intersection pair found between edge i of A and edge j of B. More...

class	Aleph::GeomSerializer
	Serialization utilities for geometry objects. More...

class	Aleph::AABBTree
	Axis-aligned bounding box tree for spatial queries. More...

struct	Aleph::AABBTree::Entry
	An entry in the tree, consisting of a bounding box and a user-defined index. More...

struct	Aleph::AABBTree::DebugNode
	Structure used for debugging and visualizing the tree structure. More...

struct	Aleph::AABBTree::DebugSnapshot
	A snapshot of the entire tree for debugging. More...

struct	Aleph::AABBTree::Node
	Internal tree node structure. More...

class	Aleph::DouglasPeuckerSimplification
	Douglas-Peucker polyline simplification. More...

class	Aleph::VisvalingamWhyattSimplification
	Visvalingam-Whyatt polyline simplification. More...

struct	Aleph::VisvalingamWhyattSimplification::VWEntry
	Entry in the priority queue for vertex removal. More...

class	Aleph::ChaikinSmoothing
	Chaikin corner-cutting subdivision for polygon smoothing. More...

class	Aleph::TrapezoidalMapPointLocation
	O(log n) point location via trapezoidal map with DAG search. More...

struct	Aleph::TrapezoidalMapPointLocation::Trapezoid
	A trapezoid in the decomposition. More...

struct	Aleph::TrapezoidalMapPointLocation::DagNode
	A node in the search Directed Acyclic Graph (DAG). More...

struct	Aleph::TrapezoidalMapPointLocation::LocationResult
	Result of a point location query. More...

struct	Aleph::TrapezoidalMapPointLocation::Result
	The trapezoidal map and DAG search structure. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
SegmentSegmentIntersection::Result	Aleph::segment_segment_intersection (const Segment &s1, const Segment &s2)
	Convenience free-function wrapper for SegmentSegmentIntersection.

Detailed Description

Computational geometry algorithms.

This file provides fundamental algorithms for computational geometry:

Triangulation

CuttingEarsTriangulation: Triangulate a simple polygon using the ear-cutting algorithm. Complexity: O(n²)

Convex Hull

Convex hull algorithms to compute the hull of a point set:

Algorithm	Complexity	Best For
AndrewMonotonicChainConvexHull	O(n log n)	General use, deterministic
GrahamScanConvexHull	O(n log n)	General use, angle-based
BruteForceConvexHull	O(n³)	Small sets, educational
GiftWrappingConvexHull	O(nh)	Few hull points (h small)
QuickHull	O(n log n) avg, O(n²) worst	General use

where n = number of points, h = number of hull points.

Closest Pair

ClosestPairDivideAndConquer: Computes the closest pair of points in O(n log n) time using divide & conquer.

Minimum Enclosing Circle

MinimumEnclosingCircle: Smallest circle containing all input points, computed in expected O(n) time via Welzl's algorithm.

Rotating Calipers (Convex Polygons)

RotatingCalipersConvexPolygon: Computes diameter in O(n) and minimum width in O(n) for convex polygons.

Point-in-Polygon

PointInPolygonWinding: Exact point location in simple polygons (inside/boundary/outside) using winding number.

Polygon Intersection (Basic)

ConvexPolygonIntersectionBasic: Exact convex-convex polygon intersection via Sutherland-Hodgman clipping.

Half-Plane Intersection

HalfPlaneIntersection: Exact bounded half-plane intersection using angle-sorted deque (O(n log n)).

Segment-Segment Intersection

SegmentSegmentIntersection: Dedicated O(1) exact intersection for a single segment pair (none / point / overlap).

Delaunay / Voronoi

DelaunayTriangulationBowyerWatson: Incremental Delaunay triangulation using Bowyer-Watson.
VoronoiDiagramFromDelaunay: Voronoi diagram derived as the dual of a Delaunay triangulation (bounded edges + unbounded rays).

Serialization

GeomSerializer: Convert basic geometry types to WKT and GeoJSON strings.

Spatial Indexing

AABBTree: Axis-aligned bounding box tree for accelerating rectangle range queries and point queries.

Polyline / Polygon Simplification

DouglasPeuckerSimplification: Recursive split by maximum perpendicular distance. O(n log n) average, O(n²) worst.
VisvalingamWhyattSimplification: Iteratively removes the vertex forming the smallest effective area triangle. O(n log n) with a heap.

Polygon Offset

ConvexPolygonOffset: Inward/outward offset of convex polygons.
PolygonOffset: Inward/outward offset of arbitrary simple polygons, with self-intersection cleanup. O(n²).

Trapezoidal Map Point Location

TrapezoidalMapPointLocation: O(log n) point location via trapezoidal decomposition with DAG search. O(n log n) expected construction, O(log n) expected query.

C++20 Support

GeomNumberType: Concept describing numeric types usable by geometry routines.

Dependencies

Requires polygon.H for geometric primitives:

Point: 2D point with x, y coordinates
Segment: Line segment between two points
Polygon: Sequence of connected vertices
Triangle: Three-point polygon
Vertex: Point with connectivity information

Usage Example

#include <geom_algorithms.H>
 
// Create a point set
DynList<Point> points;
points.append(Point(0, 0));
points.append(Point(4, 0));
points.append(Point(4, 4));
points.append(Point(0, 4));
points.append(Point(2, 2));  // Interior point
 
// Compute convex hull
QuickHull qh;
Polygon hull = qh(points);  // Returns square (excludes interior point)
 
// Triangulate a polygon
Polygon square;
square.add_vertex(Point(0, 0));
square.add_vertex(Point(4, 0));
square.add_vertex(Point(4, 4));
square.add_vertex(Point(0, 4));
square.close();
 
CuttingEarsTriangulation triangulator;
DynList<Triangle> triangles = triangulator(square);

See also: polygon.H Geometric primitives; Point, Segment, Polygon, Triangle; GeomSerializer; AABBTree

Example programs:

Examples/geom_example.C (core + advanced demo selector)
Examples/delaunay_voronoi_example.cc
Examples/point_in_polygon_example.cc
Examples/halfplane_intersection_example.cc
Examples/convex_hull_comparison_example.cc
Examples/closest_pair_example.cc
Examples/rotating_calipers_example.cc

Author: Leandro Rabindranath León; Alejandro J. Mujica

Definition in file geom_algorithms.H.

Classes

Namespaces

Functions