 |
Pangolin
Header-only C++20 plane computational geometry library
|
|
Pangolin
Header-only C++20 plane computational geometry library
|
Triangulation whose connectivity may change and whose vertex set may grow. More...
#include <triangulation.hpp>
Public Types | |
| using | TriangleType = TriangleType_ |
| using | SegmentType = SegmentType_ |
| using | PointType = typename TriangleType::PointType |
| using | NumberType = typename PointType::NumberType |
| using | SegmentLabel = typename SegmentType::LabelType |
| using | TriangleLabel = detail::optional_label_t<TriangleType> |
| using | VertexId = detail::Handle<VertexTag> |
| Handle of a vertex of this triangulation specialization. | |
| using | TriId = detail::Handle<TriTag> |
| Handle of a triangle of this triangulation specialization. | |
Public Member Functions | |
| Triangulation ()=default | |
| Creates an empty triangulation. | |
| template<class TriangleRange> requires TriangleConcept<typename TriangleRange::value_type> | |
| Triangulation (const TriangleRange &tris) | |
| Builds a triangulation from a set of triangles. | |
| template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const SegmentRange &segs) | |
| Builds a triangulation from its set of edges. | |
| template<class PointRange> requires PointConcept<typename PointRange::value_type> | |
| Triangulation (const PointRange &pts) | |
| Builds the Delaunay triangulation of a set of points. | |
| template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const PointRange &pts, const SegmentRange &segments) | |
| Builds the conforming constrained Delaunay triangulation of a point set with constraint segments. | |
| Triangulation (const Polygon< PointType > &poly) | |
| Builds the constrained Delaunay triangulation of a simple polygon, optionally with extra interior points and constraint segments. | |
| template<class PointRange> requires PointConcept<typename PointRange::value_type> | |
| Triangulation (const Polygon< PointType > &poly, const PointRange &points) | |
Adds the interior points as extra triangulation vertices. | |
| template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const Polygon< PointType > &poly, const SegmentRange &segments) | |
Adds the interior segments as constrained edges and vertices. | |
| template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const Polygon< PointType > &poly, const PointRange &points, const SegmentRange &segments) | |
Adds both interior points and constraint segments. | |
| Triangulation (const PolygonWithHoles< PointType > ®ion) | |
| Builds the constrained Delaunay triangulation of a region with holes, optionally with extra interior points and constraint segments. | |
| template<class PointRange> requires PointConcept<typename PointRange::value_type> | |
| Triangulation (const PolygonWithHoles< PointType > ®ion, const PointRange &points) | |
Adds the interior points as extra triangulation vertices. | |
| template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const PolygonWithHoles< PointType > ®ion, const SegmentRange &segments) | |
Adds the interior segments as constrained edges and vertices. | |
| template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const PolygonWithHoles< PointType > ®ion, const PointRange &points, const SegmentRange &segments) | |
Adds both interior points and constraint segments. | |
| Triangulation (const PolygonSet< PointType > &set) | |
| Builds the constrained Delaunay triangulation of a set of regions, optionally with extra interior points and constraint segments. | |
| template<class PointRange> requires PointConcept<typename PointRange::value_type> | |
| Triangulation (const PolygonSet< PointType > &set, const PointRange &points) | |
Adds the interior points as extra triangulation vertices. | |
| template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const PolygonSet< PointType > &set, const SegmentRange &segments) | |
Adds the interior segments as constrained edges and vertices. | |
| template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type> | |
| Triangulation (const PolygonSet< PointType > &set, const PointRange &points, const SegmentRange &segments) | |
Adds both interior points and constraint segments. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| Arrangement< Point< ResultNumber >, PointType > | voronoiDiagram () const |
| Returns the Voronoi diagram dual to this Delaunay triangulation. | |
| std::size_t | numVertices () const |
| Number of real vertices (excludes the ghost vertex). | |
| std::size_t | numTriangles () const |
| Number of triangles (excludes ghost and out-of-domain fill triangles). | |
| std::size_t | numEdges () const |
| Number of undirected edges incident to the visible triangulation. | |
| bool | empty () const |
| True if the triangulation stores no in-domain triangles. | |
| bool | has (const TriangleType &t) const |
True if t is one of the triangles of this triangulation. | |
| bool | has (const SegmentType &s) const |
True if s is an edge incident to the visible triangulation. | |
| std::optional< TriangleType > | otherTriangle (const TriangleType &t, const SegmentType &shared) const |
The triangle on the other side of shared from t. | |
| std::vector< TriangleType > | edgeAdjacentTriangles (const TriangleType &t) const |
The (up to three) triangles sharing an edge with t. | |
| std::vector< TriangleType > | vertexAdjacentTriangles (const TriangleType &t) const |
The triangles sharing at least one vertex with t (excluding t). | |
| std::vector< TriangleType > | incidentTriangles (const SegmentType &s) const |
The (up to two) triangles incident to edge s. | |
| std::vector< TriangleType > | incidentTriangles (const PointType &p) const |
The triangles incident to vertex p — its full fan. | |
| template<class Fn> | |
| bool | visitTriangles (Fn fn) const |
| Calls fn(Triangle) — or fn(TriId) — on every triangle. | |
| template<class Fn> | |
| bool | visitEdges (Fn fn) const |
| Calls fn(Segment) on every edge, with its stored label. | |
| std::vector< TriangleType > | triangles () const |
| Returns all triangles, sorted. | |
| std::vector< SegmentType > | edges () const |
| Returns all edges, sorted, each with its stored label. | |
| Graph< PointType > | asGraph () const |
| Returns the mesh's vertices and edges as a Graph. | |
| Arrangement< PointType, TriId > | asArrangement () const |
| Returns the visible mesh as an arrangement, labeling each triangle face by its ID. | |
| void | buildPointLocation () |
| Builds the point-location index: a Kirkpatrick hierarchy over this mesh. | |
| void | clearPointLocation () noexcept |
| Releases the point-location index. | |
| bool | hasPointLocation () const noexcept |
| True if locate and locateId currently use the point-location index. | |
| bool | hasCurrentPointLocation () const noexcept |
| True if the index is in place and was drawn against the mesh as it now stands. | |
| std::vector< TriId > | triangleIds () const |
| The handles of every triangle, in storage order. | |
| std::vector< VertexId > | vertexIds () const |
| The handles of every vertex, in storage order. | |
| std::size_t | triangleIndexBound () const |
| One past the largest index a TriId of this triangulation can carry. | |
| std::size_t | vertexIndexBound () const |
| One past the largest index a VertexId of this triangulation can carry. | |
| TriId | locateId (const PointType &p) const |
| Finds the triangle containing the query point, as a handle. | |
| template<PointConcept QueryPoint> | |
| TriId | locateId (const QueryPoint &p) const |
| TriangleType | getShape (TriId t) const |
| The triangle a handle refers to, with its stored label. | |
| const PointType & | getShape (VertexId v) const |
| The position of the vertex a handle refers to. | |
| TriangleType | operator[] (TriId t) const |
| Same as getShape(TriId) const. | |
| const PointType & | operator[] (VertexId v) const |
| Same as getShape(VertexId) const. | |
| TriId | getId (const TriangleType &t) const |
| The handle of a triangle of this triangulation. | |
| VertexId | getId (const PointType &p) const |
| The handle of a vertex of this triangulation. | |
| bool | has (TriId t) const |
True if t is a handle of one of the triangles of this triangulation. | |
| bool | has (VertexId v) const |
True if v is a handle of one of the vertices of this triangulation. | |
| std::array< VertexId, 3 > | vertices (TriId t) const |
| The three vertices of a triangle, counterclockwise. | |
| std::optional< TriId > | otherTriangle (TriId t, int side) const |
The triangle on the other side of side side of t. | |
| bool | isConstrained (TriId t, int side) const |
True if side side of t is a constrained edge. | |
| void | setConstrained (TriId t, int side, bool value=true) |
Constrains (or unconstrains) side side of t. | |
| std::optional< TriId > | otherTriangle (TriId t, VertexId a, VertexId b) const |
The triangle on the other side of edge a b from t. | |
| std::vector< TriId > | edgeAdjacentTriangles (TriId t) const |
The (up to three) triangles sharing an edge with t. | |
| std::vector< TriId > | vertexAdjacentTriangles (TriId t) const |
The triangles sharing at least one vertex with t (excluding t). | |
| std::vector< TriId > | incidentTriangles (VertexId v) const |
The triangles incident to vertex v — its full fan. | |
| template<class L = TriangleLabel> requires (detail::has_label_v<L>) | |
| L & | label (TriId t) |
Returns a reference to the label stored for the triangle t. | |
| template<class L = TriangleLabel> requires (detail::has_label_v<L>) | |
| const L & | label (TriId t) const |
| Graph< PointType > | visibilityGraph () const |
| Returns the visibility graph of the mesh vertices. | |
| Graph< PointType > | clearVisibilityGraph () const |
| Returns the clear visibility graph of the mesh vertices. | |
| Graph< PointType > | reducedVisibilityGraph () const |
| Returns the reduced visibility graph of the mesh vertices. | |
| std::vector< PointType > | visibleVertices (const PointType &query) const |
The mesh vertices visible from query. | |
| std::vector< PointType > | clearlyVisibleVertices (const PointType &query) const |
The mesh vertices clearly visible from query. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| Polygon< Point< ResultNumber > > | regularizedVisiblePolygon (const PointType &query) const |
The region of the domain visible from query, regularized. | |
| std::vector< Convex< PointType > > | convexPartition () const |
| The domain cut into convex pieces with pairwise disjoint interiors. | |
| std::vector< Convex< PointType > > | convexCovering () const |
| Covers the domain with a greedily selected set of convex polygons. | |
| template<detail::DirectedTraversal OS, class Fn> | |
| bool | visitTrianglesIntersecting (const OS &s, Fn f) const |
Visits every triangle met by the directed query s, in order. | |
| template<detail::TriangulationQuery OS> | |
| std::vector< TriangleType > | trianglesIntersecting (const OS &s) const |
Returns the triangles met by s (a segment, (oriented) line, ray, or chain, in order, or a region query shape, in an unspecified order). | |
| template<detail::TriangulationQuery OS, class Fn> | |
| bool | visitTrianglesInteriorIntersecting (const OS &s, Fn f) const |
Visits the triangles whose interior s actually enters. | |
| template<detail::TriangulationQuery OS> | |
| std::vector< TriangleType > | trianglesInteriorIntersecting (const OS &s) const |
Returns the triangles whose interior s enters. | |
| template<detail::TriangulationQuery OS, class Fn> | |
| bool | visitEdgesIntersecting (const OS &s, Fn f) const |
Visits every triangulation edge met by s. | |
| template<detail::TriangulationQuery OS, class Fn> | |
| bool | visitEdgesInteriorIntersecting (const OS &s, Fn f) const |
Visits the triangulation edges whose interior s crosses. | |
| template<detail::TriangulationQuery OS> | |
| std::vector< SegmentType > | edgesIntersecting (const OS &s) const |
Returns the triangulation edges met by s. | |
| template<detail::TriangulationQuery OS> | |
| std::vector< SegmentType > | edgesInteriorIntersecting (const OS &s) const |
Returns the triangulation edges whose interior s crosses. | |
| template<detail::TriangulationRegionQuery Q, class Fn> | |
| bool | visitTrianglesIntersecting (const Q &shape, Fn f) const |
Visits every in-domain triangle that intersects shape. | |
| template<detail::ChainTraversal C, class Fn> | |
| bool | visitTrianglesIntersecting (const C &c, Fn f) const |
Visits every in-domain triangle that intersects the chain c, in the order the chain first meets them. | |
| template<PointConcept QueryPoint> | |
| std::optional< TriangleType > | locate (const QueryPoint &p) const |
| Finds the triangle containing the query point by walking the mesh. | |
| template<PointConcept QueryPoint> | |
| bool | contains (const QueryPoint &shape) const |
True if the triangulated domain contains shape (A ⊇ B). | |
| template<detail::SegmentOrOriented S> | |
| bool | contains (const S &shape) const |
| template<detail::ChainTraversal C> | |
| bool | contains (const C &shape) const |
| template<detail::PolygonalRegion Q> | |
| bool | contains (const Q &shape) const |
| template<PolygonWithHolesConcept Q> | |
| bool | contains (const Q &shape) const |
| template<PolygonSetConcept Q> | |
| bool | contains (const Q &shape) const |
| template<HalfplaneIntersectionConcept Q> | |
| bool | contains (const Q &shape) const |
| template<DiskConcept D> | |
| bool | contains (const D &shape) const |
| template<class U> requires detail::LineOrOriented<U> || RayConcept<U> || HalfplaneConcept<U> | |
| bool | contains (const U &) const |
| template<EmptyShapeConcept E> | |
| bool | contains (const E &) const |
| bool | contains (const Shape< PointType > &shape) const |
| template<detail::TriangulationQuery Q> | |
| bool | intersects (const Q &shape) const |
True if the triangulated domain meets shape (A ∩ B ≠ ∅). | |
| template<PolygonConcept Q> | |
| bool | intersects (const Q &shape) const |
| template<PolygonWithHolesConcept Q> | |
| bool | intersects (const Q &shape) const |
| template<PolygonSetConcept Q> | |
| bool | intersects (const Q &shape) const |
| template<HalfplaneIntersectionConcept Q> | |
| bool | intersects (const Q &shape) const |
| template<EmptyShapeConcept E> | |
| bool | intersects (const E &) const |
| bool | intersects (const Shape< PointType > &shape) const |
| template<detail::TriangulationQuery Q> | |
| bool | interiorContains (const Q &shape) const |
True if the domain's interior contains shape (A∖∂A ⊇ B). | |
| template<PolygonConcept Q> | |
| bool | interiorContains (const Q &shape) const |
| template<PolygonWithHolesConcept Q> | |
| bool | interiorContains (const Q &shape) const |
| template<PolygonSetConcept Q> | |
| bool | interiorContains (const Q &shape) const |
| template<HalfplaneIntersectionConcept Q> | |
| bool | interiorContains (const Q &shape) const |
| template<EmptyShapeConcept E> | |
| bool | interiorContains (const E &) const |
| bool | interiorContains (const Shape< PointType > &shape) const |
| template<PointConcept QueryPoint> | |
| bool | interiorsIntersect (const QueryPoint &shape) const |
True if the domain's interior meets shape's interior (A∖∂A ∩ B∖∂B ≠ ∅). | |
| template<detail::TriangulationQuery Q> requires (!PointConcept<Q>) | |
| bool | interiorsIntersect (const Q &shape) const |
| template<PolygonConcept Q> | |
| bool | interiorsIntersect (const Q &shape) const |
| template<PolygonWithHolesConcept Q> | |
| bool | interiorsIntersect (const Q &shape) const |
| template<PolygonSetConcept Q> | |
| bool | interiorsIntersect (const Q &shape) const |
| template<HalfplaneIntersectionConcept Q> | |
| bool | interiorsIntersect (const Q &shape) const |
| template<EmptyShapeConcept E> | |
| bool | interiorsIntersect (const E &) const |
| bool | interiorsIntersect (const Shape< PointType > &shape) const |
| bool | isConstrained (const SegmentType &s) const |
True if edge s is flagged as constrained. | |
| void | setConstrained (const SegmentType &s, bool value=true) |
Flags (or clears) edge s as constrained on both incident sides. | |
| template<class L = TriangleLabel> requires (detail::has_label_v<L>) | |
| L & | label (const TriangleType &t) |
Returns a reference to the label stored for triangle t. | |
| template<class L = TriangleLabel> requires (detail::has_label_v<L>) | |
| const L & | label (const TriangleType &t) const |
| template<class L = SegmentLabel> requires (detail::has_label_v<L>) | |
| L & | label (const SegmentType &s) |
Returns a reference to the label stored for edge s. | |
| template<class L = SegmentLabel> requires (detail::has_label_v<L>) | |
| const L & | label (const SegmentType &s) const |
| bool | flippable (const SegmentType &s) const |
True if edge s can be flipped (unconstrained, interior, convex quad). | |
| std::optional< SegmentType > | flip (const SegmentType &s) |
Flips edge s, replacing it by the opposite diagonal. | |
| template<class EdgeRange> requires SegmentConcept<typename EdgeRange::value_type> | |
| bool | flippable (const EdgeRange &edges) const |
True if every edge in edges can be flipped simultaneously. | |
| template<class EdgeRange> requires SegmentConcept<typename EdgeRange::value_type> | |
| std::optional< std::vector< SegmentType > > | flip (const EdgeRange &edges) |
Flips every edge in edges at once, if the whole set allows it. | |
| bool | insert (const PointType &p) |
Inserts p as a new vertex. | |
| bool | insertDelaunay (const PointType &p) |
Inserts p as a new vertex and restores the constrained Delaunay property around it. | |
| bool | checkInvariants () const |
| Checks the structural invariants (orientation + neighbor symmetry). Intended for debug assertions. | |
| template<class ResultNumber> | |
| Arrangement< Point< ResultNumber >, typename Triangulation< TriangleType, SegmentType >::PointType > | voronoiDiagram () const |
Friends | |
| Canvas & | operator<< (Canvas &canvas, const Triangulation &triangulation) |
| Draws every triangle to a canvas. | |
Triangulation whose connectivity may change and whose vertex set may grow.
| TriangleType_ | The triangle type stored, e.g. pgl::Triangle<Point>. The point type — and hence any vertex labels — is taken from it. |
| SegmentType_ | The edge type stored, defaulting to the triangle's own edge-segment type. When built from a container of labeled segments it is deduced as that labeled type, so segment labels are kept. |
Any label carried by the input triangles (TriangleType::LabelType) and segments (SegmentType::LabelType) is stored and surfaced again by the accessors, and can be read or edited in place through label. A flip resets the labels of the edges and triangles it touches to default-constructed values. Labels are stored via [[no_unique_address]], so they cost nothing when absent (NoLabel).
| using pgl::Triangulation< TriangleType_, SegmentType_ >::NumberType = typename PointType::NumberType |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::PointType = typename TriangleType::PointType |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::SegmentLabel = typename SegmentType::LabelType |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::SegmentType = SegmentType_ |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::TriangleLabel = detail::optional_label_t<TriangleType> |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::TriangleType = TriangleType_ |
| using pgl::Triangulation< TriangleType_, SegmentType_ >::TriId = detail::Handle<TriTag> |
Handle of a triangle of this triangulation specialization.
| using pgl::Triangulation< TriangleType_, SegmentType_ >::VertexId = detail::Handle<VertexTag> |
Handle of a vertex of this triangulation specialization.
|
default |
Creates an empty triangulation.
|
inlineexplicit |
Builds a triangulation from a set of triangles.
The vertex set is the union of the triangles' vertices (extendable later via insert). Adjacencies, the ghost triangles over the boundary, and the segment-to-edge map are all computed automatically.
| TriangleRange | Range whose elements are TriangleType. |
| tris | Triangles forming the triangulation. |
|
inlineexplicit |
Builds a triangulation from its set of edges.
The triangular faces are recovered from the edge set by sorting each vertex's incident edges counterclockwise and tracing the bounded faces (an exact rotation-system / DCEL face walk). The vertex set is the union of the segments' endpoints (extendable later via insert).
| SegmentRange | Range whose elements are pgl::Segment. |
| segs | Edges of the triangulation. |
|
inlineexplicit |
Builds the Delaunay triangulation of a set of points.
The vertex set is the points (deduplicated; extendable later via insert) and the connectivity is their Delaunay triangulation, computed exactly. Points that are collinear with all others, or duplicated, simply carry no incident triangle.
| PointRange | Range whose elements are pgl::Point. |
| pts | Points to triangulate. |
|
inline |
Builds the conforming constrained Delaunay triangulation of a point set with constraint segments.
The vertex set is the union of the points and the segments' endpoints (deduplicated; extendable later via insert) and every input segment is present as a constrained edge — never flipped, kept by insertDelaunay, fencing hull growth like a polygon boundary when it lies on the hull. Unlike the polygon constructors nothing is carved away: the domain is the whole convex hull. Segment labels are kept on the constrained edges.
| PointRange | Range whose elements are pgl::Point. |
| SegmentRange | Range whose elements are segments. |
| pts | Points to triangulate. |
| segments | Constraint segments. |
|
inlineexplicit |
Builds the constrained Delaunay triangulation of a simple polygon, optionally with extra interior points and constraint segments.
The convex hull of all input vertices is Delaunay-triangulated, the polygon's boundary edges and every constraint segment are inserted as constraints, and the triangles lying outside the polygon (between it and its convex hull) are marked out-of-domain. The public view — triangles, numTriangles, locate, ... — then sees exactly the polygon's interior; locate therefore works for non-convex polygons.
The vertex set is the union of the polygon's vertices, the points in points, and the endpoints of the segments in segments; each segment additionally becomes a constrained edge. Either points or segments (or both) may be omitted.
| poly | Simple polygon (convex or not) to triangulate. |
poly is simple (non-self-intersecting) and non-degenerate, and any extra points and segments lie inside it (the latter is not checked).
|
inline |
Adds the interior points as extra triangulation vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie inside poly. |
|
inline |
Adds the interior segments as constrained edges and vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| segments | Constraint edges (and their endpoint vertices); assumed to lie inside poly. |
|
inline |
Adds both interior points and constraint segments.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie inside poly. |
| segments | Constraint edges (and their endpoint vertices); assumed to lie inside poly. |
|
inlineexplicit |
Builds the constrained Delaunay triangulation of a region with holes, optionally with extra interior points and constraint segments.
Every ring — the outer boundary and each hole — goes in as constrained edges, and the out-of-domain flood is seeded both from outside the convex hull and from inside each hole. The domain is then exactly the part of the region that has area: triangles, numTriangles and locate see the material between the rings and nothing else.
A region may hold pieces with no area at all — a hole sharing an edge with another ring leaves a slit, and the region contains it without any neighbourhood of it being in the region. Slits carry no triangle, so the triangulated domain is the closure of the region's interior rather than the region itself. Areas are unaffected, a slit having none.
| region | Region to triangulate. |
region satisfies PolygonWithHoles::isValid, and any extra points and segments lie in it (neither is checked).
|
inline |
Adds the interior points as extra triangulation vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie in region. |
|
inline |
Adds the interior segments as constrained edges and vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| segments | Constraint edges (and their endpoint vertices); assumed to lie in region. |
|
inline |
Adds both interior points and constraint segments.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie in region. |
| segments | Constraint edges (and their endpoint vertices); assumed to lie in region. |
|
inlineexplicit |
Builds the constrained Delaunay triangulation of a set of regions, optionally with extra interior points and constraint segments.
Every ring of every component goes in as constrained edges, and the out-of-domain flood is seeded both from outside the convex hull and from inside each component's holes. The domain is then exactly the part of the set that has area — the gap between two components is reached by the same flood that carves away the exterior, and a component stranded inside another's hole is fenced out of that hole's flood by its own outer ring.
As with a single region, a slit carries no triangle, so the triangulated domain is closure(A°) rather than A itself.
| set | Set of regions to triangulate. |
set satisfies PolygonSet::isValid, and any extra points and segments lie in it (neither is checked).
|
inline |
Adds the interior points as extra triangulation vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie in set. |
|
inline |
Adds the interior segments as constrained edges and vertices.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| segments | Constraint edges (and their endpoint vertices); assumed to lie in set. |
|
inline |
Adds both interior points and constraint segments.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| points | Extra vertices to insert; assumed to lie in set. |
| segments | Constraint edges (and their endpoint vertices); assumed to lie in set. |
|
nodiscard |
Returns the visible mesh as an arrangement, labeling each triangle face by its ID.
The arrangement contains exactly the geometric edges returned by edges. Its bounded faces that are triangles of this triangulation are labeled with their TriId; every other face, including the exterior and holes in a constrained domain, has an invalid label. Arrangement edge labels are likewise invalid: the arrangement's label type is reserved for face IDs.
|
inlinenodiscard |
Returns the mesh's vertices and edges as a Graph.
The graph is the 1-skeleton of the triangulation: its vertices are the numVertices stored points and its edges are the numEdges edges of the visible mesh, so a vertex left without any incident in-domain edge — one duplicated or collinear with every other point, which carries no triangle — comes back as an isolated graph vertex rather than not at all. The ghost vertex closing the mesh at infinity is internal and is not one of them.
The points are the graph's vertices, since a point identifies a vertex of a triangulation, unlike Arrangement::asGraph where the vertex at infinity forces the use of handles. Edge labels have no place in a graph and are dropped; label recovers the label of an edge from its endpoints.
Complexity: O(V + E).
| void pgl::Triangulation< TriangleType, SegmentType >::buildPointLocation | ( | ) |
Builds the point-location index: a Kirkpatrick hierarchy over this mesh.
The mesh is enclosed in a box and the ring between the box and the convex hull is triangulated, so that every vertex but the four box corners is interior. An independent set of low-degree vertices is then removed and the hole each star leaves is retriangulated, and again over the result, until only the box is left: some thirty levels for a mesh of 100,000 vertices, each holding about seven tenths of the triangles below it. Every triangle records the ones it covers, so a query placed in the box descends one triangle per level and arrives at the mesh triangle holding it.
Until it is called, locate and locateId walk the mesh from the last query's answer, which is fast for queries that follow one another and linear for queries that do not. Afterwards a query whose coordinates convert losslessly to this triangulation's PointType descends the hierarchy instead. What a query may return does not change: a point strictly inside a triangle gets that triangle indexed or not, and one on an edge or a vertex gets an incident triangle, which of them being as unspecified as it is for the bare walk.
The index outlives every edit. A hierarchy built before an insert or a flip stays usable across it: what it lands on is a triangle of this mesh whatever has happened to the mesh since, and the walk resumes from there rather than answering outright. What an edit costs is that resumption — the hierarchy does not know the vertices added since it was drawn, so the walk out of its answer lengthens as the mesh grows away from it. Rebuilding is therefore the owner's call and never the triangulation's — call this again to redraw the hierarchy against the mesh as it now stands (it does nothing if nothing has changed since), or clearPointLocation to give it up and go back to walking from the previous query's answer.
@complexity Expected O(V) time and space, both a small multiple of what the mesh itself takes; O(log V) per query.
|
inlinenodiscard |
Checks the structural invariants (orientation + neighbor symmetry). Intended for debug assertions.
|
nodiscard |
The mesh vertices clearly visible from query.
The strict counterpart of visibleVertices, matching clearVisibilityGraph: the open segment query–v must lie in the interior of the domain, cross no wall, and hold no other vertex. Neither grazing nor passing through a vertex counts, and a vertex reached only along the boundary — including the far end of a boundary edge query sits on — is left out. Always a subset of visibleVertices.
| query | Point to look from; outside the domain nothing is visible. |
|
inlinenoexcept |
|
nodiscard |
Returns the clear visibility graph of the mesh vertices.
Two vertices are adjacent exactly when the open segment joining them lies in the interior of the domain, crosses no wall, and contains no other vertex. This is the strict reading of visibility: a segment that grazes the boundary, runs along a wall or passes through a third vertex is excluded, and so is every boundary edge of the domain itself, whose relative interior lies on the boundary rather than inside it. The clear visibility graph of a simple polygon is therefore exactly its set of legal triangulation diagonals, and it is always a subgraph of visibilityGraph.
Computed by the same triangular expansion as visibilityGraph, with the cone kept open, and without the collinear closure.
Complexity: O(V·T + E), as for visibilityGraph.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
True if the triangulated domain contains shape (A ⊇ B).
The domain is the closed region the triangulation covers — the polygon for the polygon constructors, the convex hull otherwise — so this, and its companions interiorContains, intersects and interiorsIntersect, answer exactly what the shape predicates of the same name would answer for that region as a Polygon, boundary and all: a shape running along a polygon edge, or ending on one, is contained. The work is done on the mesh, though, so the cost is proportional to the triangles shape meets rather than to the size of the domain's boundary.
Every shape type is accepted. An unbounded one — a line, oriented line, ray, or half-plane — is never contained in the bounded domain; the empty shape always is.
| shape | Query shape; it may use a different point type. |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
|
inlinenodiscard |
Covers the domain with a greedily selected set of convex polygons.
A convex candidate is grown independently from every in-domain triangle, always against the original triangulation. Growth crosses an unconstrained boundary edge when adjoining its triangle keeps the candidate convex; a failed edge is reconsidered if a later merge changes either endpoint angle. Each candidate is stored together with the exact set of triangles fused to make it.
Those triangle sets form a set-cover instance whose universe is the in-domain triangles. The greedy phase repeatedly takes the candidate that covers the most triangles not covered yet. A final reverse pass removes a selected candidate whenever all its triangles are still covered by the other selected candidates. Thus the result is irredundant, though neither the greedy cover nor the independently grown candidates are guaranteed minimum. Unlike convexPartition, returned polygons may overlap.
Constrained edges are never crossed. The pieces are unlabeled for the same reason as those returned by convexPartition: one piece may contain several triangles with different labels.
Complexity: O(n^2) time and space for n real triangles. There are at most n candidates, each grown and stored in O(n) time and space; the incidence-based greedy cover and redundancy pass are quadratic as well.
|
inlinenodiscard |
The domain cut into convex pieces with pairwise disjoint interiors.
Hertel–Mehlhorn: start from the triangles and delete every diagonal whose deletion leaves a convex piece, in one pass. Deleting a diagonal can only change the interior angle at its two endpoints — everywhere else the merged boundary is a stretch of one of the two pieces, unchanged — so each merge is decided by two orientation tests and nothing has to be re-examined. The classical guarantee is that the result has at most four times the minimum number of convex pieces, whatever order the diagonals are visited in, which is why no search is worth doing here. On a random simple polygon it halves the piece count against the triangulation.
What it partitions is the domain: closure(interior), exactly the part the triangles cover. A region's holes are where there is no piece, and a slit — a stretch of boundary two rings cover between them — has no area and so appears in no piece. Callers that need to sweep a slit have to add it themselves; pgl::detail::minkowskiConvexPieces is the one that does.
A constrained edge is never deleted. It is in the triangulation because something asked for it, and a partition that cuts along it is the one the caller described; for a polygon or a region built without extra constraints only the rings are constrained, so nothing is given up.
The pieces come back unlabeled: a piece is a merge of several triangles and there is no one triangle's label to carry.
Complexity: O(n^2) worst-case time and O(n) auxiliary space for n real triangles. The merge tests and ring construction are linear apart from the shared-edge guard below: it walks the boundary of a current piece, and repeated walks over a growing piece can take quadratic time altogether. Reading the surviving rings is linear; putting the p result pieces in canonical order additionally takes O(p log p) polygon comparisons.
|
inlinenodiscard |
The (up to three) triangles sharing an edge with t.
|
inlinenodiscard |
The (up to three) triangles sharing an edge with t.
|
inlinenodiscard |
Returns all edges, sorted, each with its stored label.
|
inlinenodiscard |
Returns the triangulation edges whose interior s crosses.
A materialized form of visitEdgesInteriorIntersecting: the in-domain edges e with s.interiorsIntersect(e), each with its stored label — in the order they are encountered along a segment or chain s, or an unspecified order for a region query shape.
| s | A directed query — segment, oriented segment, line, oriented line, or ray — or a chain (polyline, monotone chain), both traced in order; or a region query shape (reported in an unspecified order). It may use a different point type. |
|
inlinenodiscard |
Returns the triangulation edges met by s.
A materialized form of visitEdgesIntersecting: the in-domain edges e with s.intersects(e), each with its stored label — in the order they are encountered along a segment or chain s, or an unspecified order for a region query shape.
| s | A directed query — segment, oriented segment, line, oriented line, or ray — or a chain (polyline, monotone chain), both traced in order; or a region query shape (reported in an unspecified order). It may use a different point type. |
|
inlinenodiscard |
True if the triangulation stores no in-domain triangles.
|
inline |
Flips every edge in edges at once, if the whole set allows it.
All-or-nothing: if flippable(edges) holds, each edge is replaced by the opposite diagonal and the new diagonals are returned in the order of edges; otherwise the triangulation is left unchanged and std::nullopt is returned. Because the quadrilaterals are disjoint, the individual flips are independent — one never disturbs another's quad — so order does not matter.
| edges | A range of edge segments (edges.value_type is a segment). |
edges is not flippable as a set.
|
inline |
Flips edge s, replacing it by the opposite diagonal.
The two triangles sharing s are retriangulated across the other diagonal; the segment-to-edge map is updated accordingly.
| s | Edge to flip. |
s is not flippable.
|
inlinenodiscard |
True if every edge in edges can be flipped simultaneously.
A parallel flip is valid only when each edge is individually flippable (unconstrained, interior, convex quad) and the quadrilaterals are pairwise disjoint — i.e. no triangle is shared by two of the edges' quads. A shared triangle would be rewritten by the first flip, invalidating the other, so such a set is rejected (a repeated edge fails for the same reason). An empty range is trivially flippable.
| edges | A range of edge segments (edges.value_type is a segment). |
|
inlinenodiscard |
True if edge s can be flipped (unconstrained, interior, convex quad).
|
inlinenodiscard |
The handle of a vertex of this triangulation.
Found by a point-location walk, so no hash lookup is involved.
| p | A point. |
p is not a vertex of the triangulation (or lies outside the triangulated region).
|
inlinenodiscard |
The handle of a triangle of this triangulation.
This is the bridge from the value world into the handle world: it is the one query that pays for a hash lookup, after which the handle-taking navigation methods walk the connectivity without touching a hash table.
| t | A triangle. |
t is not one of the triangulation's triangles.
|
inlinenodiscard |
The triangle a handle refers to, with its stored label.
| t | Handle of a triangle of this triangulation. |
|
inlinenodiscard |
The position of the vertex a handle refers to.
| v | Handle of a vertex of this triangulation. |
|
inlinenodiscard |
True if s is an edge incident to the visible triangulation.
|
inlinenodiscard |
True if t is one of the triangles of this triangulation.
|
inlinenodiscard |
True if t is a handle of one of the triangles of this triangulation.
|
inlinenodiscard |
True if v is a handle of one of the vertices of this triangulation.
|
inlinenodiscardnoexcept |
True if the index is in place and was drawn against the mesh as it now stands.
False once an edit has moved the mesh on from the index, which costs a query the index's answer — the walk resumes from it instead — and nothing else. See buildPointLocation, which this is the test of whether calling would do any work.
|
inlinenodiscardnoexcept |
|
inlinenodiscard |
The triangles incident to vertex p — its full fan.
| p | A vertex of the triangulation. |
p as one of its vertices, in rotational order around p. Empty if p is not a vertex of the triangulation (or lies outside the triangulated region).
|
inlinenodiscard |
The (up to two) triangles incident to edge s.
|
inlinenodiscard |
The triangles incident to vertex v — its full fan.
| v | Handle of a vertex of the triangulation. |
v as one of its vertices, in rotational order around v. Empty when v carries no triangle (a vertex duplicated or collinear with every other one) or when the handle is not a vertex of the triangulation.
|
inline |
Inserts p as a new vertex.
If p lies strictly inside a triangle, that triangle is replaced by the three-triangle fan from its edges to p. If p lies in the interior of an edge, the edge splits into two collinear halves — which inherit its constrained flag and its label — and each incident triangle (two for an interior edge, one on the convex-hull boundary) splits in two. If p lies strictly outside the convex hull, the hull grows: p is joined to every hull edge it strictly sees, one new triangle per edge (the only triangulation of the pocket between the hull and the point); a constrained hull edge stays constrained and simply becomes interior. All other edges keep their labels; the replacement triangles get default-constructed labels, as with flip.
The change is purely local — no other connectivity changes — so a Delaunay triangulation does not generally stay Delaunay; use insertDelaunay for that.
| p | The vertex to insert. |
p lies in the closed polygon. Inserting a point outside it — in the carved-away region between polygon and hull, or beyond the hull — is undefined behavior, like the polygon constructors' extra points (not checked). p is already a vertex or the triangulation is empty.
|
inline |
Inserts p as a new vertex and restores the constrained Delaunay property around it.
Performs insert, then legalizes outward from p by Lawson flips, never flipping a constrained edge: if the triangulation satisfied the constrained Delaunay property before the call (as built by the point-set and polygon constructors), it satisfies it after. Edges and triangles touched by the legalizing flips have their labels reset, as with flip; the halves of a split edge inherit its constrained flag and label, as with insert.
| p | The vertex to insert. |
p lies in the closed polygon (not checked).
|
inlinenodiscard |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
True if the domain's interior contains shape (A∖∂A ⊇ B).
The domain minus its boundary: shape must lie inside it without touching the polygon's edges (or, for a hull domain, the hull's). So it is contains plus "meets no boundary edge of the domain" — an edge with a ghost or a hull-fill triangle on its far side. A shape lying along a polygon edge is contained but not interior-contained.
| shape | Query shape; it may use a different point type. |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
True if the domain's interior meets shape's interior (A∖∂A ∩ B∖∂B ≠ ∅).
Contact along the boundary of either does not count: a segment lying on a polygon edge, or a triangle of the mesh sharing only an edge with shape, do not interior-intersect the domain.
| shape | Query shape; it may use a different point type. |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
True if the triangulated domain meets shape (A ∩ B ≠ ∅).
Closed intersection, as for contains: a shape touching the domain only along its boundary meets it. This is precisely "some triangle of the mesh meets @p shape", which is what the traversals report, so it is the cheapest of the four predicates — the walk stops at the first triangle found.
| shape | Query shape; it may use a different point type. |
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenodiscard |
True if edge s is flagged as constrained.
|
inlinenodiscard |
True if side side of t is a constrained edge.
Handle counterpart of isConstrained(const SegmentType&) const, with the edge named by the triangle it belongs to and its index there (see otherTriangle(TriId, int) const for the side convention). Constraints are what the polygon and region constructors mark their boundary with, so this is also how a walk recognizes the boundary of the shape it came from without keeping a set of its edges.
| t | Handle of a triangle of the triangulation. |
| side | Which of its three edges to test, in [0, 3). |
|
inlinenodiscard |
Returns a reference to the label stored for edge s.
The reference is into the triangulation's own storage, so assigning through it (tri.label(s) = ...) changes the label every later accessor reports for that edge. Only available when the segment type carries a label.
| s | An edge of this triangulation. |
s is one of the triangulation's edges.
|
inlinenodiscard |
|
inlinenodiscard |
Returns a reference to the label stored for triangle t.
The reference is into the triangulation's own storage, so assigning through it (tri.label(t) = ...) changes the label every later accessor reports for that triangle. Only available when the triangle type carries a label.
| t | A triangle of this triangulation. |
t is one of the triangulation's triangles.
|
inlinenodiscard |
|
inlinenodiscard |
Returns a reference to the label stored for the triangle t.
Handle counterpart of label(const TriangleType&), reaching the same storage without the hash lookup that resolving a triangle value needs.
| t | Handle of a triangle of this triangulation. |
|
inlinenodiscard |
|
inlinenodiscard |
Finds the triangle containing the query point by walking the mesh.
Uses a stochastic (randomized) visibility walk, which terminates with probability one on any valid triangulation, not just Delaunay ones; a generous step cap remains only as a defensive bound. After buildPointLocation a query descends the point-location hierarchy instead, for the same answer in logarithmic time.
| p | Query point; may use a different point type than the triangulation. |
p lies outside the triangulated region (or the triangulation is empty).
|
inlinenodiscard |
Finds the triangle containing the query point, as a handle.
Handle counterpart of locate: the same stochastic visibility walk, answering with the triangle's handle instead of its value. This is the hash-free way into the handle world for a point that is not a vertex — getId(*locate(p)) would locate the triangle and then look it up again.
buildPointLocation replaces the walk by a descent of the point-location hierarchy, which is what a query pays for; it does not change what a query may return.
| p | Query point; may use a different point type than the triangulation. |
p lies outside the triangulated region (or the triangulation is empty).
|
inlinenodiscard |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. Queries with matching coordinate types take their walk's start from the index whenever their points can be converted too. Other coordinate types walk from the usual hint, avoiding a potentially lossy conversion into the index's own point type.
|
inlinenodiscard |
Number of undirected edges incident to the visible triangulation.
|
inlinenodiscard |
Number of triangles (excludes ghost and out-of-domain fill triangles).
|
inlinenodiscard |
Number of real vertices (excludes the ghost vertex).
|
inlinenodiscard |
Same as getShape(TriId) const.
|
inlinenodiscard |
Same as getShape(VertexId) const.
|
inlinenodiscard |
The triangle on the other side of shared from t.
| t | A triangle of the triangulation. |
| shared | An edge of t. |
shared, or std::nullopt if that edge is on the boundary or the arguments are not part of the mesh.
|
inlinenodiscard |
The triangle on the other side of side side of t.
Side i of a triangle is the edge from vertices(t)[i] to vertices(t)[(i + 1) % 3], which is getShape(t).edges()[i]. Crossing it is one array read, so a walk over the mesh never has to name an edge by its segment.
| t | Handle of a triangle of the triangulation. |
| side | Which of its three edges to cross, in [0, 3). |
|
inlinenodiscard |
The triangle on the other side of edge a b from t.
Handle counterpart of otherTriangle(const TriangleType&, const SegmentType&) const, with the shared edge given by its two endpoints instead of as a segment.
| t | Handle of a triangle of the triangulation. |
| a | One endpoint of an edge of t. |
| b | The other endpoint of that edge. |
t.
|
nodiscard |
Returns the reduced visibility graph of the mesh vertices.
The subgraph of visibilityGraph holding the edges a shortest path can bend along: those tangent to the obstacles at both ends. An edge uv is tangent at u when the walls incident to u all lie in one closed half-plane of the line uv, which is what lets a taut path bend there. A vertex with no incident wall — a free point inside the domain — bends no path and comes back isolated.
The surviving edges are the walls themselves and the bitangents between reflex corners, so this is much sparser than visibilityGraph.
This graph alone does not answer shortest-path queries. What it guarantees is the interior of a geodesic: an edge lying strictly inside some shortest path has that path bending at both its ends, is therefore tangent at both, and survives. A path does not bend at its own endpoints, though — it merely starts and ends there — so its first and last hop need no tangency and may well have been pruned. To route between two points, vertices or not, add each of them joined to everything it sees:
Using it unaided returns a path that exists but is too long: a convex corner keeps only its two boundary edges, so a route starting there is forced along the wall.
Complexity: visibilityGraph plus O(E·w) for w walls per vertex, which is two along a polygon boundary.
|
nodiscard |
The region of the domain visible from query, regularized.
The visibility polygon: every point reachable from query by a segment that stays in the domain and crosses no wall. Being star-shaped about query it is simply connected, so the result is one Polygon however many holes or walls the domain has.
Regularized means the closure of the interior, which drops the lower-dimensional slivers grazing sight would otherwise add: a sightline running along a wall, or straight through a vertex into a region beyond that has no area, contributes a one-dimensional spike to the visible set and none to this. What comes back always bounds area.
Its vertices are the domain's own vertices together with the window ends where a sightline past a reflex corner lands on a farther edge. Those are ray-edge intersections and need division, so the result type is requested explicitly, as everywhere in the library.
query on the boundary is a vertex of the result. Should the domain pinch so that the visible region reaches query along more than one lobe, the ring passes through query once per lobe and is then only weakly simple.
| ResultNumber | Coordinate type of the result (default: division_result_t of the mesh's own). |
| query | Point to look from. |
query lies outside the domain.
|
inline |
Flags (or clears) edge s as constrained on both incident sides.
|
inline |
Constrains (or unconstrains) side side of t.
Handle counterpart of setConstrained(const SegmentType&, bool). The flag belongs to the edge, so it is set on both incident triangles and a later isConstrained sees it from either side.
| t | Handle of a triangle of the triangulation. |
| side | Which of its three edges to mark, in [0, 3). |
| value | true to constrain the edge, false to release it. |
|
inlinenodiscard |
The handles of every triangle, in storage order.
The order is the triangulation's own, which is neither the sorted order of triangles nor a stable one across edits, but is the order that reads the connectivity arrays front to back.
|
inlinenodiscard |
One past the largest index a TriId of this triangulation can carry.
id.index() is therefore a slot of a side table of this size — a plain std::vector rather than a map — for every handle the triangulation hands out. The indices are dense over [0, triangleIndexBound()), but the range also covers the triangles a polygon or region domain carved away, which has rejects and no query returns: it is a bound on the storage, not a triangle count, and exceeds numTriangles by exactly those.
|
inlinenodiscard |
Returns all triangles, sorted.
|
inlinenodiscard |
Returns the triangles whose interior s enters.
A materialized form of visitTrianglesInteriorIntersecting: the in-domain triangles t with t.interiorsIntersect(s) — in the order they are encountered along a segment or chain s, or an unspecified order for a region query shape.
| s | A directed query — segment, oriented segment, line, oriented line, or ray — or a chain (polyline, monotone chain), both traced in order; or a region query shape (reported in an unspecified order). It may use a different point type. |
|
inlinenodiscard |
Returns the triangles met by s (a segment, (oriented) line, ray, or chain, in order, or a region query shape, in an unspecified order).
A materialized form of visitTrianglesIntersecting: the in-domain triangles t with s.intersects(t), in the order they are encountered along s. The order is preserved (not sorted), since it is the point of the traversal.
| s | A directed query — segment, oriented segment, line, oriented line, or ray — or a chain (polyline, monotone chain), both traced in order; or a region query shape (reported in an unspecified order). It may use a different point type. |
|
inlinenodiscard |
The triangles sharing at least one vertex with t (excluding t).
The union of the vertex fans of t's three vertices: every triangle touching t at a vertex or across an edge, each listed once. A superset of edgeAdjacentTriangles.
| t | A triangle of the triangulation. |
t; empty if t is not part of the mesh.
|
inlinenodiscard |
The triangles sharing at least one vertex with t (excluding t).
Handle counterpart of vertexAdjacentTriangles(const TriangleType&) const.
|
inlinenodiscard |
The handles of every vertex, in storage order.
Every stored vertex is listed, including one that carries no triangle (duplicated, or collinear with every other point), exactly as numVertices counts them. The internal ghost vertex is not one of them.
|
inlinenodiscard |
One past the largest index a VertexId of this triangulation can carry.
As with triangleIndexBound, id.index() is a slot of a side table of this size. Vertex indices are dense over [1, vertexIndexBound()): slot 0 belongs to the internal ghost vertex that closes the mesh at infinity and is never handed out, so a table indexed by id.index() - 1 is the tight one of numVertices entries.
|
inlinenodiscard |
The three vertices of a triangle, counterclockwise.
Handle counterpart of getShape(t).vertices(): the order is the same one TriangleType normalizes to, the lexicographically smallest vertex first, so vertices(t)[i] is the vertex at getShape(t)[i].
| t | Handle of a triangle of this triangulation. |
|
nodiscard |
Returns the visibility graph of the mesh vertices.
Sight is stopped by the boundary of the domain and by every constrained edge, which therefore act as opaque walls: poly.triangulation(walls) answers visibility inside poly among the obstacles walls. An unconstrained interior edge is transparent, so the visibility graph of a plain point-set triangulation is the complete graph over its convex hull.
Two vertices are adjacent exactly when the closed segment joining them stays in the closed domain and never crosses a wall. Grazing counts: a segment that runs along a wall, touches a boundary vertex, or passes straight through another vertex without leaving the domain is a visibility edge. See clearVisibilityGraph for the convention that forbids it.
The mesh's own edges are always present, and a vertex with no in-domain triangle comes back isolated rather than absent.
Computed by triangular expansion: one cone-clipped traversal of the mesh per vertex, whose cost is proportional to the part of the domain that vertex actually sees, followed by a walk along each collinear chain. Every test is an orientation predicate on stored vertices, so an exact coordinate type stays exact and nothing is ever constructed.
Complexity: O(V·T + E) for V vertices, E visibility edges and T triangles seen per vertex; T is O(1) in a corridor-like domain and O(V) at worst.
|
nodiscard |
The mesh vertices visible from query.
Same convention as visibilityGraph, for a point that need not be a vertex: a vertex v is reported when the closed segment query–v stays in the closed domain and crosses no wall, grazing included. Together with reducedVisibilityGraph this is what routes a shortest path between arbitrary points — that graph alone holds only the edges a path can bend along, so each endpoint needs joining to everything it sees:
Costs one cone-clipped traversal of the mesh, proportional to the part of the domain query actually sees — never the whole visibility graph.
| query | Point to look from; outside the domain nothing is visible. |
query starting from the lexicographically smallest, as sortAround orders them. Empty when query lies outside the domain.
|
inline |
Calls fn(Segment) on every edge, with its stored label.
If fn returns a value convertible to bool, the visit stops early as soon as it returns true; a void-returning fn visits every edge.
|
inline |
Visits the triangulation edges whose interior s crosses.
Like visitEdgesIntersecting but reports only the edges e with s.interiorsIntersect(e) — dropping those merely touched at a shared endpoint (e.g. where a segment s passes through a mesh vertex, or an endpoint of s lands on an edge). s may be a directed query, a chain, or a region query shape.
f follows the visitor convention (return true to stop early, void to visit all); returns whether the walk stopped early. s may use a different point type than the triangulation.
|
inline |
Visits every triangulation edge met by s.
Reports each in-domain edge e with s.intersects(e) exactly once, with its stored label (for a segment or chain s, roughly in the order it meets them, ties broken arbitrarily; for a region query shape, in an unspecified order). Built on visitTrianglesIntersecting: as each met triangle is visited, its edges that s meets are reported (deduplicated across the two triangles sharing an edge). Edges of ghost or out-of-domain triangles are never reported, matching edges.
f follows the visitor convention (return true to stop early, void to visit all); returns whether the walk stopped early. s may use a different point type than the triangulation.
|
inline |
Calls fn(Triangle) — or fn(TriId) — on every triangle.
A fn that accepts a TriangleType is given triangle values; one that accepts only a TriId is given handles instead, so a global pass can work in the handle world without materializing a triangle per step. A generic callable ([](auto t)) accepts both and is given values.
If fn returns a value convertible to bool, the visit stops early as soon as it returns true; a void-returning fn visits every triangle.
|
inline |
Visits the triangles whose interior s actually enters.
Like visitTrianglesIntersecting but reports only the triangles t with t.interiorsIntersect(s) — dropping those merely touched along an edge or at a vertex. The traversal still passes through every met triangle for navigation; the filtered ones simply are not reported. s may be a directed query or a chain (reported in order) or a region query shape (unspecified order).
f follows the visitor convention (return true to stop early, void to visit all); returns whether the walk stopped early. s may use a different point type than the triangulation.
|
inline |
Visits every in-domain triangle that intersects the chain c, in the order the chain first meets them.
Generalizes visitTrianglesIntersecting(const OS&, Fn) const from a single segment to a polygonal chain — a Polyline or a MonotoneChain. The chain is traced edge by edge with the directed segment walk, from vertex c[0] towards c[c.size() - 1], and each triangle is reported the first time it is met: the set passed to f is exactly { t : t.intersects(c) } over the in-domain triangles, so a triangle met again by a later edge (a chain that turns back into it, or self-intersects) is not reported twice. A chain that leaves the triangulated region and comes back is handled — unlike the region flood fill, the per-edge walks re-enter it — and a chain with a single vertex is the point query.
The cost is that of the individual segment walks: proportional to the triangles met, plus one point location per edge.
f follows the visitor convention: returning true stops the walk early, a void return visits every such triangle. Returns whether it stopped early. c may use a different point type.
|
inline |
Visits every triangle met by the directed query s, in order.
s may be a segment, oriented segment, line, oriented line, or ray. For a segment, it locates s.source(), visits the triangles touching it (if any), then traces s to s.target(). A line or oriented line has no finite endpoints: it enters the hull at the ghost where the directed line s[0]->s[1] crosses in (found by a directional descent of the ghost ring) and traces forward until it leaves the hull again. A ray keeps s.source() (located, or entered at that directional ghost when the source is outside the hull) but, like a line, runs forward until it leaves the hull rather than stopping at a target. Either way each triangle crossed is visited — including the fan where s passes through a vertex — and the set passed to f is exactly { t : s.intersects(t) } over the in-domain triangles, in the order they are met along s[0]->s[1] (a plain line's order follows its arbitrary defining-point direction). Ghost triangles and (for a polygon) out-of-domain hull-fill triangles are traversed for navigation but never reported, so a query leaving and re-entering the polygon through a reflex pocket simply shows a gap.
f follows the visitor convention: returning true stops the walk early, a void return visits all. Returns whether it stopped early. As in visitTriangles, an f that accepts only a TriId is given handles instead of triangle values. s may use a different point type than the triangulation.
|
inline |
Visits every in-domain triangle that intersects shape.
Generalizes visitTrianglesIntersecting(const OS&, Fn) const from a segment to a connected convex query shape — a point, triangle, rectangle, convex polygon, or an unbounded line, oriented line, ray, or half-plane. The set of triangles t passed to f is exactly { t : t.intersects(shape) } over the in-domain triangles, in an unspecified order.
The work is local. A seed triangle meeting shape is found by navigation — tracing shape's boundary edges with the segment walk (for a bounded shape), or scanning the convex-hull boundary for an edge it crosses (for an unbounded one) — and the reported set is then grown by a flood fill through edge/vertex adjacency that never strays past the triangles meeting shape and their immediate neighbours. The cost is therefore proportional to the number of triangles met, not to the size of the triangulation; the lone exception is the unbounded-shape seed search, which scans the hull and is O(hull).
f follows the visitor convention: returning true stops the walk early, a void return visits every such triangle. Returns whether it stopped early. shape may use a different point type.
| Arrangement< Point< ResultNumber >, typename Triangulation< TriangleType, SegmentType >::PointType > pgl::Triangulation< TriangleType_, SegmentType_ >::voronoiDiagram | ( | ) | const |
|
nodiscard |
Returns the Voronoi diagram dual to this Delaunay triangulation.
The result is an unbounded Arrangement whose faces are labeled by their generating vertices: after locating a query in a face f, diagram.label(f) is the nearest vertex. On a Voronoi edge or vertex, Arrangement::locateFace applies its usual infinitesimal perturbation and therefore selects one of the tied sites; use Arrangement::locateCell and inspect the incident faces to recover every tied site.
The dual is built from the current triangle connectivity. An interior Delaunay edge becomes a segment between the two incident circumcenters, and a convex-hull edge becomes an outward ray. Cocircular triangles may have the same circumcenter; their zero-length dual edge is omitted.
The arrangement's edge labels are default-constructed and have no meaning; its face labels are the stored PointType values.
| ResultNumber | Coordinate type of the arrangement vertices. The default is exact and overflow-free for integral input. |
|
friend |
Draws every triangle to a canvas.
| canvas | Destination canvas. |
| triangulation | Triangulation whose triangles are drawn. |
1.17.0