triangulation.hpp File Reference

Mutable triangulation of a point set or simple polygon. More...

#include "algorithm/bitmatrix.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <limits>
#include <map>
#include <memory>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <variant>
#include <vector>

Go to the source code of this file.

Classes
struct	pgl::Triangulation< TriangleType_, SegmentType_ >
	Triangulation whose connectivity may change and whose vertex set may grow. More...
struct	pgl::Triangulation< TriangleType_, SegmentType_ >::Kirkpatrick::Cell

Namespaces
namespace	pgl

Functions
template<class TriangleRange> requires TriangleConcept<typename TriangleRange::value_type>
	pgl::Triangulation (const TriangleRange &) -> Triangulation< typename TriangleRange::value_type >
template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const SegmentRange &) -> Triangulation< Triangle< typename SegmentRange::value_type::PointType >, typename SegmentRange::value_type >
template<class PointRange> requires PointConcept<typename PointRange::value_type>
	pgl::Triangulation (const PointRange &) -> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > > >
template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const PointRange &, const SegmentRange &) -> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > >, Segment< Point< typename PointRange::value_type::NumberType >, typename SegmentRange::value_type::LabelType > >
template<class PointType>
	pgl::Triangulation (const Polygon< PointType > &) -> Triangulation< Triangle< PointType > >
template<class PolyPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	pgl::Triangulation (const Polygon< PolyPoint > &, const PointRange &) -> Triangulation< Triangle< PolyPoint > >
template<class PolyPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const Polygon< PolyPoint > &, const SegmentRange &) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >
template<class PolyPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const Polygon< PolyPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >
template<class RegionPoint>
	pgl::Triangulation (const PolygonWithHoles< RegionPoint > &) -> Triangulation< Triangle< RegionPoint > >
template<class RegionPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	pgl::Triangulation (const PolygonWithHoles< RegionPoint > &, const PointRange &) -> Triangulation< Triangle< RegionPoint > >
template<class RegionPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const PolygonWithHoles< RegionPoint > &, const SegmentRange &) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >
template<class RegionPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const PolygonWithHoles< RegionPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >
template<class SetPoint>
	pgl::Triangulation (const PolygonSet< SetPoint > &) -> Triangulation< Triangle< SetPoint > >
template<class SetPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	pgl::Triangulation (const PolygonSet< SetPoint > &, const PointRange &) -> Triangulation< Triangle< SetPoint > >
template<class SetPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const PolygonSet< SetPoint > &, const SegmentRange &) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >
template<class SetPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	pgl::Triangulation (const PolygonSet< SetPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >

Detailed Description

Mutable triangulation of a point set or simple polygon.

Vertex coordinates never move once added, but the vertex set can grow — Triangulation::insert and Triangulation::insertDelaunay add a new point by subdividing the triangle or edge containing it, or by growing the hull when it is outside — and the connectivity (the set of triangles and their adjacencies) changes via Triangulation::flip.

The main interface speaks in value types — pgl::Triangle, pgl::Segment, and pgl::Point. Internally the connectivity uses the triangle-with-neighbors layout (each triangle stores three CCW vertex indices and three neighbor-triangle indices, with neighbor i across the edge opposite vertex i), closed by a single ghost vertex so every edge has two incident triangles. Those internal records (Tri, Edge) and the raw indices are private and never exposed.

A single unordered_map<Segment, Edge> bridges the two worlds: it converts an outside-world edge (a Segment) into the internal Edge handle. A public Triangle is resolved by taking one of its edges, looking up that handle, and selecting the incident side whose apex matches the triangle — so no triangle-keyed map is needed.

Beside that, a low-level interface speaks in handles — Triangulation::TriId and Triangulation::VertexId — which are opaque strong types over those internal indices. Triangulation::getId (paying for one lookup) and Triangulation::locateId (paying for none) cross into it, and Triangulation::getShape or Triangulation::operator[] crosses back, so a traversal that would otherwise hash a Segment per step walks the connectivity arrays directly. Handles are positions in that storage: they stay valid while the triangulation is only read, and any mutation (Triangulation::insert, Triangulation::flip) may reuse them for other cells.