The planar subdivision induced by a set of one-dimensional shapes. More...

#include <arrangement.hpp>

Public Types
using	VertexId = detail::Handle<VertexTag>
	Handle of a vertex of this arrangement specialization.
using	HalfedgeId = detail::Handle<HalfedgeTag>
	Handle of a halfedge of this arrangement specialization.
using	FaceId = detail::Handle<FaceTag>
	Handle of a face of this arrangement specialization.
using	CellId = std::variant<VertexId, HalfedgeId, FaceId>
	Handle of the arrangement cell containing a finite query point.
using	PointType = PointType_
	Vertex type.
using	NumberType = typename PointType::NumberType
	Coordinate type of the vertices.
using	LabelType = TLabel
	Label type carried by edges and faces.
using	SegmentType = Segment<PointType, TLabel>
	Segment alternative returned for a bounded edge.
using	LineType = Line<PointType, TLabel>
	Line alternative returned for an edge.
using	OrientedSegmentType = OrientedSegment<PointType, TLabel>
	Type returned for a halfedge.
using	OrientedLineType = OrientedLine<PointType, TLabel>
	Oriented-line alternative returned for a halfedge.
using	RayType = Ray<PointType, TLabel>
	Ray alternative returned for a halfedge.
using	HalfedgeType = std::variant<OrientedSegmentType, OrientedLineType, RayType>
	Geometry of an oriented halfedge.
using	EdgeType = std::variant<SegmentType, LineType, RayType>
	Geometry of an unoriented edge.
using	IntersectionId = std::variant<HalfedgeId, VertexId>
	Vertex or edge met by a directed intersection query.

Public Member Functions
	Arrangement ()
	Creates the empty arrangement: no cell but the unbounded face.
template<std::ranges::input_range ShapeRange>
	Arrangement (const ShapeRange &shapes)
	Builds the arrangement of a range of shapes.
template<std::ranges::input_range ShapeRange>
	Arrangement (const ShapeRange &shapes, detail::SimpleBoundariesTag)
template<std::ranges::input_range ShapeRange, std::ranges::input_range PointRange>
	Arrangement (const ShapeRange &shapes, const PointRange &points)
	Builds the arrangement of a range of shapes together with a range of points.
std::size_t	vertexCount () const
	Returns the number of finite vertices.
std::size_t	halfedgeCount () const
	Returns the number of halfedges: always even, twins being adjacent.
std::size_t	edgeCount () const
	Returns the number of edges, i.e. half the number of halfedges.
std::size_t	faceCount () const
	Returns the number of faces, including every unbounded face.
const std::vector< PointType > &	vertices () const
	Returns the position of every finite vertex, in VertexId index order.
std::vector< SegmentType >	boundedEdges () const
	Returns the bounded edges, omitting every ray and line.
std::vector< EdgeType >	edges () const
	Returns every edge as a segment, line, or ray.
const PointType &	operator[] (VertexId v) const
	Returns the position of a vertex.
HalfedgeType	operator[] (HalfedgeId h) const
	Returns the geometry of a halfedge, carrying the edge label.
HalfedgeId	twin (HalfedgeId h) const
	Returns the halfedge running along the same edge the other way.
HalfedgeId	next (HalfedgeId h) const
	Returns the next halfedge along the boundary of the face on the left.
VertexId	source (HalfedgeId h) const
	Returns the vertex a halfedge leaves.
VertexId	target (HalfedgeId h) const
	Returns the vertex a halfedge arrives at.
FaceId	face (HalfedgeId h) const
	Returns the face to the left of a halfedge.
HalfedgeId	outgoing (VertexId v) const
	Returns one halfedge leaving a vertex, or the invalid handle when the vertex is isolated.
std::size_t	degree (VertexId v) const
	Returns the number of halfedges leaving a vertex.
std::vector< HalfedgeId >	outgoingHalfedges (VertexId v) const
	Returns every halfedge leaving a vertex, in clockwise order.
Graph< VertexId >	asGraph () const
	Returns the vertex-edge incidence structure as a Graph.
template<class ResultNumber = NumberType>
Point< ResultNumber >	witness (VertexId v) const
	Returns the vertex itself, as the witness of a zero-dimensional cell.
template<class ResultNumber = division_result_t<NumberType>>
Point< ResultNumber >	witness (HalfedgeId h) const
	Returns the midpoint of an edge, which lies in its relative interior.
template<class ResultNumber = division_result_t<NumberType>>
Point< ResultNumber >	witness (FaceId f) const
	Returns a point strictly inside a bounded face.
bool	hasSimpleBoundary (FaceId f) const
	Tells whether a face's boundary is a single simple ring: no hole, and no edge with the face on both sides.
bool	isUnbounded () const
	Tells whether the arrangement contains an unbounded edge.
bool	isUnbounded (HalfedgeId h) const
	Tells whether a halfedge is adjacent to the symbolic vertex at infinity.
bool	isUnbounded (FaceId f) const
	Tells whether a face is unbounded.
bool	isFictitious (VertexId v) const
	Tells whether a vertex is the symbolic point at infinity.
HalfedgeId	outerCycle (FaceId f) const
	Returns a halfedge of the face's outer boundary cycle, which runs counterclockwise, or the invalid handle for an unbounded face.
std::span< const HalfedgeId >	innerCycles (FaceId f) const
	Returns one halfedge of each of the face's inner boundary cycles, each of which runs clockwise.
std::vector< HalfedgeId >	boundaryOf (FaceId f) const
	Returns every halfedge bounding a face, outer cycle first.
std::vector< HalfedgeId >	outerBoundaryOf (FaceId f) const
	Returns the halfedges of a face's counterclockwise outer boundary.
std::vector< std::vector< HalfedgeId > >	innerBoundariesOf (FaceId f) const
	Returns the halfedges of every clockwise inner boundary cycle.
template<class ResultNumber = NumberType>
PolygonWithHoles< Point< ResultNumber > >	polygonWithHoles (FaceId f) const
	Returns the closure of a bounded face as a region.
template<class ResultNumber = NumberType>
HalfplaneIntersection< Point< ResultNumber > >	halfplaneIntersection (FaceId f) const
	Returns the outer boundary constraints of a face as a half-plane intersection, ignoring holes.
const TLabel &	label (HalfedgeId h) const
	Returns the label an edge inherited from the input shape that produced it.
TLabel &	label (HalfedgeId h)
	Returns the mutable label of an edge.
const TLabel &	label (FaceId f) const
	Returns the label of a face.
TLabel &	label (FaceId f)
	Returns the mutable label of a face.
std::span< const std::uint32_t >	originsOf (HalfedgeId h) const
	Returns the positions, in the range the arrangement was built from, of every input shape that produced an edge.
std::vector< std::uint32_t >	originsOf (VertexId v) const
	Returns the positions, in the range the arrangement was built from, of every input shape passing through a vertex.
void	buildPointLocation ()
	Builds the randomized trapezoidal point-location index.
template<class UniformRandomBitGenerator>
void	buildPointLocation (UniformRandomBitGenerator &&generator)
	Builds the point-location index using a caller-provided generator.
void	clearPointLocation () noexcept
	Releases this arrangement's reference to its point-location index.
bool	hasPointLocation () const noexcept
	Tells whether locateFace currently uses the point-location index.
FaceId	locateFace (const PointType &p) const
	Returns the face containing a point.
CellId	locateCell (const PointType &p) const
	Returns the vertex, edge, or face containing a point.
template<class Q, class Fn> requires (OrientedSegmentConcept<Q> \|\| OrientedLineConcept<Q> \|\| RayConcept<Q> \|\| MonotoneChainConcept<Q> \|\| PolylineConcept<Q>)
bool	visitIntersecting (const Q &r, Fn fn) const
	Visits the vertices and edges met by a directed curve, in order.
template<class Q> requires (OrientedSegmentConcept<Q> \|\| OrientedLineConcept<Q> \|\| RayConcept<Q> \|\| MonotoneChainConcept<Q> \|\| PolylineConcept<Q>)
std::vector< IntersectionId >	reportIntersecting (const Q &r) const
	Returns every vertex and edge met by a directed curve, in order.
template<class Q> requires (OrientedSegmentConcept<Q> \|\| OrientedLineConcept<Q> \|\| RayConcept<Q> \|\| MonotoneChainConcept<Q> \|\| PolylineConcept<Q>)
std::optional< IntersectionId >	firstIntersecting (const Q &r) const
	Returns the first vertex or edge met by a directed curve.
template<class Q> requires (OrientedSegmentConcept<Q> \|\| OrientedLineConcept<Q> \|\| RayConcept<Q> \|\| MonotoneChainConcept<Q> \|\| PolylineConcept<Q>)
bool	emptyIntersecting (const Q &r) const
	Returns whether a directed curve meets no vertex or edge.

Detailed Description

template<class PointType_, class TLabel>
class pgl::Arrangement< PointType_, TLabel >

The planar subdivision induced by a set of one-dimensional shapes.

Planar subdivision induced by a set of one-dimensional shapes.

Template Parameters

PointType_	Vertex type, pgl::EPoint by default. It must be able to represent the crossings of the input, so a rational point type unless the input segments meet only at their endpoints.
TLabel	Label carried by an edge (inherited from the input shape that produced it) and by a face (default-constructed, editable).

The cells of the subdivision are its vertices, edges and faces, handled by Arrangement::VertexId, Arrangement::HalfedgeId and Arrangement::FaceId. Each edge is a pair of twin halfedges: twin(h) is h.index() ^ 1, and the face of a halfedge is always the one on its left, so a bounded face is enclosed by a counterclockwise cycle of next and the outer boundary of a connected piece of the input runs clockwise.

Face 0 is an unbounded face. Lines and pairs of rays can produce several unbounded faces; the empty arrangement has just face 0.

Construction is exact and takes any range of points, segment-bounded shapes, lines, oriented lines and rays. A Point becomes an isolated vertex. Half-planes, disks and other two-dimensional input are rejected.

Declared here, well before its definition in algorithm/arrangement.hpp, so that an implementation header included ahead of it — the cut predicates pgl::Polygon::separates and pgl::Polygon::crosses run on the arrangement of both operands' boundaries — may name the class inside a template whose instantiation happens later.

The vertex type defaults to pgl::EPoint — spelled out here, where that alias does not exist yet — because an arrangement's vertices are crossings, and only an exact rational point type is guaranteed to hold them.

Member Typedef Documentation

◆ CellId

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::CellId = std::variant<VertexId, HalfedgeId, FaceId>

Handle of the arrangement cell containing a finite query point.

◆ EdgeType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::EdgeType = std::variant<SegmentType, LineType, RayType>

Geometry of an unoriented edge.

◆ FaceId

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::FaceId = detail::Handle<FaceTag>

Handle of a face of this arrangement specialization.

◆ HalfedgeId

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::HalfedgeId = detail::Handle<HalfedgeTag>

Handle of a halfedge of this arrangement specialization.

◆ HalfedgeType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::HalfedgeType = std::variant<OrientedSegmentType, OrientedLineType, RayType>

Geometry of an oriented halfedge.

◆ IntersectionId

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::IntersectionId = std::variant<HalfedgeId, VertexId>

Vertex or edge met by a directed intersection query.

◆ LabelType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::LabelType = TLabel

Label type carried by edges and faces.

◆ LineType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::LineType = Line<PointType, TLabel>

Line alternative returned for an edge.

◆ NumberType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::NumberType = typename PointType::NumberType

Coordinate type of the vertices.

◆ OrientedLineType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::OrientedLineType = OrientedLine<PointType, TLabel>

Oriented-line alternative returned for a halfedge.

◆ OrientedSegmentType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::OrientedSegmentType = OrientedSegment<PointType, TLabel>

Type returned for a halfedge.

◆ PointType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::PointType = PointType_

Vertex type.

◆ RayType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::RayType = Ray<PointType, TLabel>

Ray alternative returned for a halfedge.

◆ SegmentType

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::SegmentType = Segment<PointType, TLabel>

Segment alternative returned for a bounded edge.

◆ VertexId

template<class PointType_, class TLabel>

using pgl::Arrangement< PointType_, TLabel >::VertexId = detail::Handle<VertexTag>

Handle of a vertex of this arrangement specialization.

Constructor & Destructor Documentation

◆ Arrangement() [1/4]

template<class PointType_, class TLabel>

pgl::Arrangement< PointType_, TLabel >::Arrangement ( )

inline

Creates the empty arrangement: no cell but the unbounded face.

◆ Arrangement() [2/4]

template<class PointType_, class TLabel>

template<std::ranges::input_range ShapeRange>

pgl::Arrangement< PointType_, TLabel >::Arrangement ( const ShapeRange & shapes )

inlineexplicit

Builds the arrangement of a range of shapes.

Accepted shapes are a Point (an isolated vertex), a Segment or OrientedSegment, a Polyline or MonotoneChain, a Polygon, Triangle, Rectangle, Convex or PolygonWithHoles (their boundaries), a Line, OrientedLine or Ray, and a Shape variant holding any of those. Half-planes, disks and other two-dimensional input are rejected.

The input may be as degenerate as it likes: segments may cross, overlap collinearly, repeat, share endpoints, dangle with a free end, or run vertically. Overlapping and duplicated stretches are merged into a single edge, which then remembers every input shape it came from (originsOf).

Complexity: O(E log E) in the size of the arrangement — interning the vertices, sorting each rotational fan, tracing the cycles, and nesting each boundary cycle in the face holding it — plus the splitting step, which is the one term that is not output-sensitive: it is quadratic in the number of distinct input segments in the worst case, although a sweep over the segments' x-projections keeps the pairs actually tested to those whose bounding boxes overlap. Replacing the split by a sweep that reports the crossings per segment is what the rest of the construction is arranged around; it is what stands between this and a construction whose whole cost follows the size of what it produces.

The nesting is the one step with two implementations rather than one, so the bound deserves a word: halfedgesLeftOf answers the batch of Q questions either by a sweep, in O((E + Q) log E), or by a scan over the edges per question, in O(Q E), and it takes the scan only when Q E comes out below the sweep's own bound. The scan is therefore capped by the inequality that admits it and not a fallback out of the bound; and Q is at most 2E, a question being one boundary cycle and the cycles being halfedge-disjoint, so O((E + Q) log E) is O(E log E) either way. Input containing a ray or line uses the general carrier overlay, which tests every pair of distinct supporting lines and is quadratic in their number before the same O(E log E) topology construction.

Template Parameters

ShapeRange Range of shapes.

Parameters

shapes Shapes whose subdivision of the plane to compute.

◆ Arrangement() [3/4]

template<class PointType_, class TLabel>

template<std::ranges::input_range ShapeRange>

pgl::Arrangement< PointType_, TLabel >::Arrangement	(	const ShapeRange &	shapes,
		detail::SimpleBoundariesTag	)

inline

◆ Arrangement() [4/4]

template<class PointType_, class TLabel>

template<std::ranges::input_range ShapeRange, std::ranges::input_range PointRange>

pgl::Arrangement< PointType_, TLabel >::Arrangement	(	const ShapeRange &	shapes,
		const PointRange &	points )

inline

Builds the arrangement of a range of shapes together with a range of points.

The points are vertices of the arrangement wherever they fall: a point on a shape splits it there, and a point on nothing becomes a vertex of its own, incident to no edge and lying in the interior of the face that holds it. Passing them separately is a convenience — a Point in the shape range does the same thing — for the callers whose points and shapes come from different places, such as the cell decomposition behind pgl::Polygon::separates.

Template Parameters

ShapeRange	Range of shapes; see the single-range constructor for what is accepted.
PointRange	Range of points.

Parameters

shapes	Shapes whose subdivision of the plane to compute.
points	Points to add as vertices.

Member Function Documentation

◆ asGraph()

template<class PointType_, class TLabel>

Graph< VertexId > pgl::Arrangement< PointType_, TLabel >::asGraph ( ) const

inlinenodiscard

Returns the vertex-edge incidence structure as a Graph.

Every vertex of the arrangement is a graph vertex, isolated ones included, and every edge becomes the graph edge joining the handles of its two endpoints. When the arrangement has a symbolic vertex at infinity (isUnbounded), that vertex is one of them, so a ray reaches it just as it does in the halfedge structure.

The vertices are VertexId handles rather than points because a point does not name a vertex on its own: the vertex at infinity has none. operator[] turns a finite handle back into its position, and isFictitious recognizes the infinite one.

A Graph is simple, so the two things the arrangement can hold and it cannot are dropped. A line's two ends are the same infinity vertex, so it contributes a self-loop and hence no graph edge; and two edges sharing both endpoints — two rays leaving the same vertex, which meet again at infinity — are coalesced into one. Both are exactly the cases where the graph would have to distinguish edges that its adjacency sets cannot.

Complexity: O(V + E).

◆ boundaryOf()

template<class PointType_, class TLabel>

std::vector< HalfedgeId > pgl::Arrangement< PointType_, TLabel >::boundaryOf ( FaceId f ) const

inlinenodiscard

Returns every halfedge bounding a face, outer cycle first.

The returned halfedges follow each boundary cycle under next. For a bounded face, its counterclockwise outer cycle comes first, followed by each clockwise inner cycle. An unbounded face has no outer cycle, so its result consists only of its inner cycles. Consequently, the boundary of the empty arrangement is empty.

Parameters

f	Face handle.

◆ boundedEdges()

template<class PointType_, class TLabel>

std::vector< SegmentType > pgl::Arrangement< PointType_, TLabel >::boundedEdges ( ) const

inlinenodiscard

Returns the bounded edges, omitting every ray and line.

◆ buildPointLocation() [1/2]

template<class PointType, class TLabel>

void pgl::Arrangement< PointType, TLabel >::buildPointLocation ( )

Builds the randomized trapezoidal point-location index.

The operation is idempotent. Until it is called, locateFace and locateCell use their linear-scan implementations; afterwards they use the immutable index. Copies of an indexed arrangement share the index because arrangement topology cannot change through the public API. The randomized insertion order is generated from a fixed seed, making the resulting index deterministic across runs. Use the generator-taking overload to select a different order.

@complexity Expected O(E log E) time and O(E) space.

◆ buildPointLocation() [2/2]

template<class PointType, class TLabel>

template<class UniformRandomBitGenerator>

void pgl::Arrangement< PointType, TLabel >::buildPointLocation ( UniformRandomBitGenerator && generator )

Builds the point-location index using a caller-provided generator.

This overload makes the randomized incremental order reproducible in tests and applications that require it.

◆ clearPointLocation()

template<class PointType_, class TLabel>

void pgl::Arrangement< PointType_, TLabel >::clearPointLocation ( )

inlinenoexcept

Releases this arrangement's reference to its point-location index.

◆ degree()

template<class PointType_, class TLabel>

std::size_t pgl::Arrangement< PointType_, TLabel >::degree ( VertexId v ) const

inlinenodiscard

Returns the number of halfedges leaving a vertex.

This is the size outgoingHalfedges would return, obtained by walking the rotational fan without building the vector. An isolated vertex has degree zero, and every other vertex has one halfedge per incident edge end, so a vertex where k lines cross has degree 2k.

Parameters

v	Vertex handle.

◆ edgeCount()

template<class PointType_, class TLabel>

std::size_t pgl::Arrangement< PointType_, TLabel >::edgeCount ( ) const

inlinenodiscard

Returns the number of edges, i.e. half the number of halfedges.

◆ edges()

template<class PointType_, class TLabel>

std::vector< EdgeType > pgl::Arrangement< PointType_, TLabel >::edges ( ) const

inlinenodiscard

Returns every edge as a segment, line, or ray.

The edge at index i is the one represented by halfedges 2i and 2i + 1. Lines are unoriented; a ray keeps its unique finite source.

◆ emptyIntersecting()

template<class PointType_, class TLabel>

template<class Q>
requires (OrientedSegmentConcept<Q> || OrientedLineConcept<Q> || RayConcept<Q> || MonotoneChainConcept<Q> || PolylineConcept<Q>)

bool pgl::Arrangement< PointType_, TLabel >::emptyIntersecting ( const Q & r ) const

inlinenodiscard

Returns whether a directed curve meets no vertex or edge.

◆ face()

template<class PointType_, class TLabel>

FaceId pgl::Arrangement< PointType_, TLabel >::face ( HalfedgeId h ) const

inlinenodiscard

Returns the face to the left of a halfedge.

Parameters

h	Halfedge handle.

◆ faceCount()

template<class PointType_, class TLabel>

std::size_t pgl::Arrangement< PointType_, TLabel >::faceCount ( ) const

inlinenodiscard

Returns the number of faces, including every unbounded face.

◆ firstIntersecting()

template<class PointType_, class TLabel>

template<class Q>
requires (OrientedSegmentConcept<Q> || OrientedLineConcept<Q> || RayConcept<Q> || MonotoneChainConcept<Q> || PolylineConcept<Q>)

std::optional< IntersectionId > pgl::Arrangement< PointType_, TLabel >::firstIntersecting ( const Q & r ) const

inlinenodiscard

Returns the first vertex or edge met by a directed curve.

◆ halfedgeCount()

template<class PointType_, class TLabel>

std::size_t pgl::Arrangement< PointType_, TLabel >::halfedgeCount ( ) const

inlinenodiscard

Returns the number of halfedges: always even, twins being adjacent.

◆ halfplaneIntersection()

template<class PointType_, class TLabel>

template<class ResultNumber = NumberType>

HalfplaneIntersection< Point< ResultNumber > > pgl::Arrangement< PointType_, TLabel >::halfplaneIntersection ( FaceId f ) const

inlinenodiscard

Returns the outer boundary constraints of a face as a half-plane intersection, ignoring holes.

For a bounded face, the constraints come from its outer cycle. For an unbounded face, they come from the boundary cycles that visit the symbolic vertex at infinity; bounded inner cycles are holes and are ignored. An edge with the face on both sides is a slit or dangling edge, not part of the regularized outer boundary, and is ignored as well. Consequently, the empty arrangement and the unbounded face outside an isolated bounded component produce the whole plane.

Each constraint uses the defining coordinates already stored for the arrangement edge. As for any HalfplaneIntersection, the result is the intersection of the supporting half-planes; it equals the face with its holes filled when that outer boundary is convex.

Template Parameters

ResultNumber Coordinate type of the half-planes' defining points.

Parameters

f	Face handle.

Exceptions

std::logic_error if f is invalid.

◆ hasPointLocation()

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::hasPointLocation ( ) const

inlinenodiscardnoexcept

Tells whether locateFace currently uses the point-location index.

◆ hasSimpleBoundary()

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::hasSimpleBoundary ( FaceId f ) const

inlinenodiscard

Tells whether a face's boundary is a single simple ring: no hole, and no edge with the face on both sides.

Those are exactly the faces whose closure is the interior of their outer cycle, so a witness for the ring is a witness for the face. A face never pinches shut at a vertex — two lobes meeting at a point are not connected as open sets, so they are two faces — which is why a dangling edge is the only thing left to rule out.

Parameters

f	Face handle.

◆ innerBoundariesOf()

template<class PointType_, class TLabel>

std::vector< std::vector< HalfedgeId > > pgl::Arrangement< PointType_, TLabel >::innerBoundariesOf ( FaceId f ) const

inlinenodiscard

Returns the halfedges of every clockwise inner boundary cycle.

Each vector follows one cycle under next, and the vectors have the same order as innerCycles. The result is empty when the face has no inner boundaries.

Parameters

f	Face handle.

◆ innerCycles()

template<class PointType_, class TLabel>

std::span< const HalfedgeId > pgl::Arrangement< PointType_, TLabel >::innerCycles ( FaceId f ) const

inlinenodiscard

Returns one halfedge of each of the face's inner boundary cycles, each of which runs clockwise.

An inner cycle is what encloses a hole of the face — either material of the input stranded inside it, or a boundary walk through infinity for an unbounded face.

Parameters

f	Face handle.

◆ isFictitious()

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::isFictitious ( VertexId v ) const

inlinenodiscard

Tells whether a vertex is the symbolic point at infinity.

◆ isUnbounded() [1/3]

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::isUnbounded ( ) const

inlinenodiscard

Tells whether the arrangement contains an unbounded edge.

This tests for the symbolic infinity vertex, not for an unbounded face: every arrangement has an unbounded face, including the empty arrangement and arrangements made entirely of segments.

◆ isUnbounded() [2/3]

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::isUnbounded ( FaceId f ) const

inlinenodiscard

Tells whether a face is unbounded.

Parameters

f	Face handle.

◆ isUnbounded() [3/3]

template<class PointType_, class TLabel>

bool pgl::Arrangement< PointType_, TLabel >::isUnbounded ( HalfedgeId h ) const

inlinenodiscard

Tells whether a halfedge is adjacent to the symbolic vertex at infinity.

Both twins of a ray or line edge are unbounded. A segment halfedge is bounded, including one obtained by splitting an unbounded input curve between two finite vertices.

Parameters

h	Halfedge handle.

◆ label() [1/4]

template<class PointType_, class TLabel>

TLabel & pgl::Arrangement< PointType_, TLabel >::label ( FaceId f )

inlinenodiscard

Returns the mutable label of a face.

◆ label() [2/4]

template<class PointType_, class TLabel>

const TLabel & pgl::Arrangement< PointType_, TLabel >::label ( FaceId f ) const

inlinenodiscard

Returns the label of a face.

Faces have no label of their own to inherit — nothing in the input is a face — so a face's label starts default-constructed and is there for the caller to fill in, typically with whatever classification it ran per cell.

Parameters

f	Face handle.

◆ label() [3/4]

template<class PointType_, class TLabel>

TLabel & pgl::Arrangement< PointType_, TLabel >::label ( HalfedgeId h )

inlinenodiscard

Returns the mutable label of an edge.

◆ label() [4/4]

template<class PointType_, class TLabel>

const TLabel & pgl::Arrangement< PointType_, TLabel >::label ( HalfedgeId h ) const

inlinenodiscard

Returns the label an edge inherited from the input shape that produced it.

An edge produced by several input shapes at once — overlapping or duplicated input — carries the label of the first of them, and originsOf lists them all.

Parameters

h	Halfedge handle.

◆ locateCell()

template<class PointType, class TLabel>

Arrangement< PointType, TLabel >::CellId pgl::Arrangement< PointType, TLabel >::locateCell ( const PointType & p ) const

nodiscard

Returns the vertex, edge, or face containing a point.

An edge is represented by its even-numbered halfedge, independently of orientation. Unlike locateFace, this operation does not perturb a query on the boundary into an incident face.

◆ locateFace()

template<class PointType, class TLabel>

Arrangement< PointType, TLabel >::FaceId pgl::Arrangement< PointType, TLabel >::locateFace ( const PointType & p ) const

nodiscard

Returns the face containing a point.

A point on an edge or on a vertex belongs to no face; the answer is then the face that an infinitesimal displacement of the query point towards -x (and, if that is not enough to leave the boundary, towards +y) lands in.

Without a point-location index the search is a linear scan over the edges. After buildPointLocation it uses a randomized trapezoidal search DAG and takes expected logarithmic time.

Parameters

p	Query point.

◆ next()

template<class PointType_, class TLabel>

HalfedgeId pgl::Arrangement< PointType_, TLabel >::next ( HalfedgeId h ) const

inlinenodiscard

Returns the next halfedge along the boundary of the face on the left.

Parameters

h	Halfedge handle.

◆ operator[]() [1/2]

template<class PointType_, class TLabel>

HalfedgeType pgl::Arrangement< PointType_, TLabel >::operator[] ( HalfedgeId h ) const

inlinenodiscard

Returns the geometry of a halfedge, carrying the edge label.

The result is an OrientedSegment, OrientedLine or Ray. Segment and line twins reverse orientation. A ray has only one finite source and therefore returns the same ray for both twins.

Parameters

h	Halfedge handle.

◆ operator[]() [2/2]

template<class PointType_, class TLabel>

const PointType & pgl::Arrangement< PointType_, TLabel >::operator[] ( VertexId v ) const

inlinenodiscard

Returns the position of a vertex.

Parameters

v	Vertex handle.

Exceptions

std::logic_error if v is invalid or is the infinity vertex.

◆ originsOf() [1/2]

template<class PointType_, class TLabel>

std::span< const std::uint32_t > pgl::Arrangement< PointType_, TLabel >::originsOf ( HalfedgeId h ) const

inlinenodiscard

Returns the positions, in the range the arrangement was built from, of every input shape that produced an edge.

There is more than one exactly when input shapes overlap along the edge. The positions come out sorted and without repetition.

Parameters

h	Halfedge handle.

◆ originsOf() [2/2]

template<class PointType_, class TLabel>

std::vector< std::uint32_t > pgl::Arrangement< PointType_, TLabel >::originsOf ( VertexId v ) const

inlinenodiscard

Returns the positions, in the range the arrangement was built from, of every input shape passing through a vertex.

This is the union of originsOf(HalfedgeId) over the edges incident to the vertex, sorted and without repetition. An isolated vertex is incident to no edge and has no origins, even when an input point put it there.

Parameters

v	Vertex handle.

◆ outerBoundaryOf()

template<class PointType_, class TLabel>

std::vector< HalfedgeId > pgl::Arrangement< PointType_, TLabel >::outerBoundaryOf ( FaceId f ) const

inlinenodiscard

Returns the halfedges of a face's counterclockwise outer boundary.

The halfedges follow one another under next. An unbounded face has no outer boundary, so its result is empty.

Parameters

f	Face handle.

◆ outerCycle()

template<class PointType_, class TLabel>

HalfedgeId pgl::Arrangement< PointType_, TLabel >::outerCycle ( FaceId f ) const

inlinenodiscard

Returns a halfedge of the face's outer boundary cycle, which runs counterclockwise, or the invalid handle for an unbounded face.

Parameters

f	Face handle.

◆ outgoing()

template<class PointType_, class TLabel>

HalfedgeId pgl::Arrangement< PointType_, TLabel >::outgoing ( VertexId v ) const

inlinenodiscard

Returns one halfedge leaving a vertex, or the invalid handle when the vertex is isolated.

This is the entry point of the rotational fan around the vertex: next(twin(h)) is the next halfedge leaving it clockwise, and iterating that until the start comes back visits every incident edge exactly once.

Parameters

v	Vertex handle.

◆ outgoingHalfedges()

template<class PointType_, class TLabel>

std::vector< HalfedgeId > pgl::Arrangement< PointType_, TLabel >::outgoingHalfedges ( VertexId v ) const

inlinenodiscard

Returns every halfedge leaving a vertex, in clockwise order.

The first entry is outgoing(v), and each following entry is next(twin(h)) of the previous one. An isolated vertex has no outgoing halfedges and returns an empty vector.

Parameters

v	Vertex handle.

◆ polygonWithHoles()

template<class PointType_, class TLabel>

template<class ResultNumber = NumberType>

PolygonWithHoles< Point< ResultNumber > > pgl::Arrangement< PointType_, TLabel >::polygonWithHoles ( FaceId f ) const

inlinenodiscard

Returns the closure of a bounded face as a region.

The result is the regularized face: a dangling edge sticking into the face, which the face's boundary cycle walks down and back, has no place in a polygon and is dropped, and a boundary cycle that pinches shut at a vertex is cut there into one ring per side, as PolygonWithHoles requires. The vertices are kept as they are otherwise, so a vertex lying in the middle of a straight stretch of boundary stays in the ring.

Template Parameters

ResultNumber Coordinate type of the result.

Parameters

f	Face handle.

Exceptions

std::logic_error if f is invalid or names an unbounded face.

◆ reportIntersecting()

template<class PointType_, class TLabel>

template<class Q>
requires (OrientedSegmentConcept<Q> || OrientedLineConcept<Q> || RayConcept<Q> || MonotoneChainConcept<Q> || PolylineConcept<Q>)

std::vector< IntersectionId > pgl::Arrangement< PointType_, TLabel >::reportIntersecting ( const Q & r ) const

inlinenodiscard

Returns every vertex and edge met by a directed curve, in order.

◆ source()

template<class PointType_, class TLabel>

VertexId pgl::Arrangement< PointType_, TLabel >::source ( HalfedgeId h ) const

inlinenodiscard

Returns the vertex a halfedge leaves.

Parameters

h	Halfedge handle.

◆ target()

template<class PointType_, class TLabel>

VertexId pgl::Arrangement< PointType_, TLabel >::target ( HalfedgeId h ) const

inlinenodiscard

Returns the vertex a halfedge arrives at.

Parameters

h	Halfedge handle.

◆ twin()

template<class PointType_, class TLabel>

HalfedgeId pgl::Arrangement< PointType_, TLabel >::twin ( HalfedgeId h ) const

inlinenodiscard

Returns the halfedge running along the same edge the other way.

Parameters

h	Halfedge handle, which must be valid: the invalid handle has no twin, and flipping its index would only produce a second, less canonical invalid value.

◆ vertexCount()

template<class PointType_, class TLabel>

std::size_t pgl::Arrangement< PointType_, TLabel >::vertexCount ( ) const

inlinenodiscard

Returns the number of finite vertices.

◆ vertices()

template<class PointType_, class TLabel>

const std::vector< PointType > & pgl::Arrangement< PointType_, TLabel >::vertices ( ) const

inlinenodiscard

Returns the position of every finite vertex, in VertexId index order.

The symbolic infinity vertex, when present, has handle index vertexCount() and no position, so it is absent from both this vector and the count.

◆ visitIntersecting()

template<class PointType, class TLabel>
requires (OrientedSegmentConcept<Q> || OrientedLineConcept<Q> || RayConcept<Q> || MonotoneChainConcept<Q> || PolylineConcept<Q>)

template<class Q, class Fn>
requires (OrientedSegmentConcept<Q> || OrientedLineConcept<Q> || RayConcept<Q> || MonotoneChainConcept<Q> || PolylineConcept<Q>)

bool pgl::Arrangement< PointType, TLabel >::visitIntersecting	(	const Q &	r,
		Fn	fn ) const

Visits the vertices and edges met by a directed curve, in order.

The query may be a Ray, OrientedLine, OrientedSegment, MonotoneChain, or Polyline. Where the query meets an edge only at one of its endpoints, the vertex there stands for the contact and the edge is not reported for it; a straight piece meeting that same edge away from its endpoints still reports the edge. An edge is represented by only one of its twin halfedges, and a chain that meets the same cell more than once reports it at its first encounter.

If fn returns bool, true stops the traversal. A void visitor never stops it. When the point-location index is present its vertex and curve indexes supply the candidates; otherwise the arrangement arrays do.

Returns: true if the visitor requested an early stop.

◆ witness() [1/3]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>>

Point< ResultNumber > pgl::Arrangement< PointType_, TLabel >::witness ( FaceId f ) const

inlinenodiscard

Returns a point strictly inside a bounded face.

A face whose boundary is a single simple ring — no hole to fall into and no dangling edge to land on — gets the same witness a polygon does: the midpoint of a diagonal from its leftmost vertex, or the interior point of an ear. That divides the coordinates by two or four and no more, which matters far beyond the cost of computing it: the witness exists to be fed to containment predicates, and an exact predicate costs what the size of its operands says it costs.

Any other face — one with holes, or with a slit running into it — is settled by leaving the midpoint of a boundary halfedge along the inward normal and stopping halfway to the first point where that ray meets the face's own boundary, which is the whole of what can stop it since the ray starts inside the face. That answer is a ratio of products of coordinates, so it is the expensive one, and it is used only where it is needed.

Either way the cost is linear in the face's boundary, hence linear in the arrangement over all faces together.

Template Parameters

ResultNumber Coordinate type of the result.

Parameters

f	Face handle.

Precondition: The face is bounded (isUnbounded is false).

Warning: The witness is a genuine interior point in exact arithmetic; an integral ResultNumber may round it onto the boundary, exactly as Triangle::pointInside may.

◆ witness() [2/3]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>>

Point< ResultNumber > pgl::Arrangement< PointType_, TLabel >::witness ( HalfedgeId h ) const

inlinenodiscard

Returns the midpoint of an edge, which lies in its relative interior.

Template Parameters

ResultNumber Coordinate type of the result.

Parameters

h	Halfedge handle.

Warning: Halves coordinates, so an integral ResultNumber may round the midpoint onto an endpoint.

◆ witness() [3/3]

template<class PointType_, class TLabel>

template<class ResultNumber = NumberType>

Point< ResultNumber > pgl::Arrangement< PointType_, TLabel >::witness ( VertexId v ) const

inlinenodiscard

Returns the vertex itself, as the witness of a zero-dimensional cell.

Template Parameters

ResultNumber Coordinate type of the result.

Parameters

v	Vertex handle.

Exceptions

std::logic_error if v is the infinity vertex.

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ CellId

◆ EdgeType

◆ FaceId

◆ HalfedgeId

◆ HalfedgeType

◆ IntersectionId

◆ LabelType

◆ LineType

◆ NumberType

◆ OrientedLineType

◆ OrientedSegmentType

◆ PointType

◆ RayType

◆ SegmentType

◆ VertexId

Constructor & Destructor Documentation

◆ Arrangement() [1/4]

◆ Arrangement() [2/4]

◆ Arrangement() [3/4]

◆ Arrangement() [4/4]

Member Function Documentation

◆ asGraph()

◆ boundaryOf()

◆ boundedEdges()

◆ buildPointLocation() [1/2]

◆ buildPointLocation() [2/2]

◆ clearPointLocation()

◆ degree()

◆ edgeCount()

◆ edges()

◆ emptyIntersecting()

◆ face()

◆ faceCount()

◆ firstIntersecting()

◆ halfedgeCount()

◆ halfplaneIntersection()

◆ hasPointLocation()

◆ hasSimpleBoundary()

◆ innerBoundariesOf()

◆ innerCycles()

◆ isFictitious()

◆ isUnbounded() [1/3]

◆ isUnbounded() [2/3]

◆ isUnbounded() [3/3]

◆ label() [1/4]

◆ label() [2/4]

◆ label() [3/4]

◆ label() [4/4]

◆ locateCell()

◆ locateFace()

◆ next()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ originsOf() [1/2]

◆ originsOf() [2/2]

◆ outerBoundaryOf()

◆ outerCycle()

◆ outgoing()

◆ outgoingHalfedges()

◆ polygonWithHoles()

◆ reportIntersecting()

◆ source()

◆ target()

◆ twin()

◆ vertexCount()

◆ vertices()

◆ visitIntersecting()

◆ witness() [1/3]

◆ witness() [2/3]

◆ witness() [3/3]