pgl::Polygon< PointType_, TLabel > Struct Template Reference

Closed simple polygon stored by its vertices. More...

#include <polygon.hpp>

Inheritance diagram for pgl::Polygon< PointType_, TLabel >:

Classes
class	BoundaryIterator
	Forward iterator over the (optionally oriented) boundary edges. More...

Public Types
using	PointType = PointType_
using	NumberType = PointType::NumberType
using	LabelType = TLabel
template<bool Oriented>
using	BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>>
using	EdgeIterator = BoundaryIterator<false>
using	OrientedEdgeIterator = BoundaryIterator<true>

Public Member Functions
constexpr	Polygon ()=default
	Creates a polygon with no vertex.
template<std::ranges::input_range Range = std::initializer_list<PointType>> requires std::ranges::common_range<Range> && std::convertible_to<std::ranges::range_value_t<Range>, PointType>
constexpr	Polygon (Range &&points, bool trusted=false)
	Creates a polygon from a range of points.
constexpr	Polygon (std::initializer_list< NumberType > coords, bool trusted=false)
	Creates a polygon from a flat list of coordinates.
template<PointConcept OtherPointType, class OtherLabelType> requires (std::constructible_from<PointType, const OtherPointType&>)
constexpr	Polygon (const Polygon< OtherPointType, OtherLabelType > &other)
	Converts a polygon with compatible vertex type.
template<class A = LabelType> requires (detail::has_label_v<A>)
constexpr A &	label () const
	Returns the polygon label.
constexpr const PointType	operator[] (std::size_t index) const
	Accesses a vertex by index.
constexpr PointType	get (std::ptrdiff_t index) const
	Cyclic access: same as operator[] but index is taken modulo size(); negative indices wrap from the end. Useful for iterating polygon edges where the last edge wraps around.
constexpr std::ptrdiff_t	index (const PointType &point) const
	Returns the smallest index i with (*this)[i] == point, or -1 if point is not a vertex.
constexpr auto	begin () const
	Returns a constant iterator to the first vertex.
constexpr auto	cbegin () const
	Returns a constant iterator to the first vertex.
constexpr auto	end () const
	Returns a constant iterator past the last vertex.
constexpr auto	cend () const
	Returns a constant iterator past the last vertex.
constexpr auto	operator<=> (const Polygon &other) const
	Compares two polygons by their canonical vertex sequences.
constexpr bool	operator== (const Polygon &other) const
	Checks equality of two polygons.
template<AnyShapeConcept OtherShape>
constexpr bool	samePointSet (const OtherShape &other) const
	Tests whether another shape defines exactly the same point set.
constexpr std::size_t	size () const
	Returns the number of vertices in the polygon.
template<class ResultNumber = NumberType>
constexpr ResultNumber	twiceArea () const
	Computes twice the (unsigned) area of the polygon via the shoelace formula.
template<class ResultNumber = division_result_t<NumberType>>
constexpr auto	area () const
	Computes the area of the polygon.
constexpr bool	empty () const
	Returns whether the polygon is the empty set of points.
constexpr bool	isDegenerate () const
	Checks if the polygon is degenerate (has zero area).
constexpr bool	isPoint () const
	Checks whether the polygon covers exactly one point.
constexpr std::optional< PointType >	getIfPoint () const
	Returns the point the polygon collapses to, if it does.
constexpr bool	isSegment () const
	Checks whether the polygon covers exactly one segment of positive length.
constexpr std::optional< BoundaryType< false > >	getIfSegment () const
	Returns the segment the polygon collapses to, if it does.
constexpr bool	isUndefined () const
	Checks whether the polygon is degenerate without covering a point or a segment.
template<class Rational = pgl::Rational<pgl::BigInt>>
bool	isSimple () const
	Tests whether the polygon is simple (its boundary does not touch or cross itself).
constexpr bool	isConvex () const
	Tests whether the polygon is convex.
constexpr std::size_t	chainCount () const
	Counts the maximal lexicographically monotone chains the boundary decomposes into, without building any of them.
constexpr std::optional< HalfplaneIntersection< PointType > >	getStarShapedKernel () const
	Returns the kernel: the set of points that see the whole polygon.
constexpr bool	isStarShaped () const
	Tests whether the polygon is star-shaped.
constexpr Segment< PointType >	diameter () const
	Returns a segment realizing the diameter (the farthest vertex pair).
constexpr Convex< PointType >	convexHull () const
	Returns the convex hull of the polygon's vertices.
constexpr const Rectangle< PointType > &	bbox () const
	Computes the bounding box of the polygon.
template<class ResultNumber = grid_number_t<typename PointType_::NumberType>> requires (detail::extended_integral<ResultNumber> || std::same_as<ResultNumber, BigInt>)
std::vector< Point< ResultNumber, typename PointType::LabelType > >	latticePoints () const
	Returns the integer points the polygon contains.
template<std::floating_point ResultNumber = double>
constexpr Rectangle< Point< ResultNumber > >	fbox () const
	Computes the floating-point bounding box of the polygon.
constexpr std::vector< PointType >	vertices () const
	Returns the vertices of the polygon (translation applied).
constexpr std::vector< Segment< PointType > >	edges () const
	Returns the edges of the polygon.
constexpr std::vector< OrientedSegment< PointType > >	orientedEdges () const
	Returns the oriented edges of the polygon.
Graph< PointType >	visibilityGraph () const
	Returns the visibility graph of the polygon vertices.
Graph< PointType >	clearVisibilityGraph () const
	Returns the clear visibility graph of the polygon vertices.
Graph< PointType >	reducedVisibilityGraph () const
	Returns the reduced visibility graph of the polygon vertices.
std::vector< PointType >	visibleVertices (const PointType &query) const
	The polygon vertices visible from query.
std::vector< PointType >	clearlyVisibleVertices (const PointType &query) const
	The polygon vertices clearly visible from query.
template<class ResultNumber = division_result_t<NumberType>>
Polygon< Point< ResultNumber > >	regularizedVisiblePolygon (const PointType &query) const
	The part of the polygon visible from query, regularized.
constexpr auto	verticesView () const
	Returns a lazy view over the vertices, translating each on the fly instead of allocating a vector.
constexpr auto	edgesView () const
	Returns a lazy view over the edges, materializing each Segment on the fly instead of allocating a vector.
constexpr auto	orientedEdgesView () const
	Lazy view counterpart of orientedEdges(); see edgesView().
constexpr EdgeIterator	edgesBegin () const
	Returns an iterator to the first unoriented edge.
constexpr EdgeIterator	edgesEnd () const
	Returns an iterator past the last unoriented edge.
constexpr OrientedEdgeIterator	orientedEdgesBegin () const
	Returns an iterator to the first oriented edge.
constexpr OrientedEdgeIterator	orientedEdgesEnd () const
	Returns an iterator past the last oriented edge.
constexpr PolygonWithHoles< PointType >	asPolygonWithHoles () const
	Returns the polygon as a hole-free region.
constexpr PolygonSet< PointType >	asPolygonSet () const
	Returns the polygon as a one-component set of regions.
template<class ResultNumber = division_result_t<NumberType>>
constexpr Point< ResultNumber >	centroid () const
	Computes the area-weighted centroid of the polygon.
template<class ResultNumber = division_result_t<NumberType>>
constexpr Point< ResultNumber >	verticesCentroid () const
	Computes the centroid of the vertex set (the average of the vertices).
template<class ResultNumber = division_result_t<NumberType>>
constexpr Point< ResultNumber >	pointInside () const
	Returns a point strictly inside the (simple) polygon.
template<class OtherShape>
constexpr bool	pointInsideInteriorContainedIn (const OtherShape &shape) const
	Tests whether some point in this shape's relative interior lies in the strict interior of shape.
auto	triangulation () const
	Builds the constrained Delaunay triangulation of this polygon.
template<class SegmentRange>
auto	triangulation (const SegmentRange &segments) const
	Builds the constrained Delaunay triangulation of this polygon with the given interior constraint segments.
std::vector< Convex< PointType > >	convexPartition () const
	Cuts this polygon into convex pieces with disjoint interiors.
std::vector< Convex< PointType > >	convexCovering () const
	Covers this polygon with convex hulls derived from triangle cliques.
template<class ResultNumber = grid_number_t<typename PointType_::NumberType>> requires (std::signed_integral<ResultNumber>)
auto	asBitMatrix () const
	Rasterizes this polygon into a BitMatrix, one bit per covered cell.
template<class PointRange, class SegmentRange>
auto	triangulation (const PointRange &points, const SegmentRange &segments) const
	Builds the constrained Delaunay triangulation of this polygon with the given interior vertices and constraint segments.
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherPolygon &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherConvex &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherTriangle &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherRectangle &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherRegion &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherSet &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherIntersection &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	difference (const OtherHalfplane &other) const
	Returns the regularized set difference of the two shapes (A ∖ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	regularizedUnion (const OtherPolygon &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	regularizedUnion (const OtherConvex &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	regularizedUnion (const OtherTriangle &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	regularizedUnion (const OtherRectangle &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	regularizedUnion (const OtherRegion &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
auto	regularizedUnion (const OtherSet &other) const
	Returns the regularized union of the two shapes (A ∪ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	symmetricDifference (const OtherPolygon &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	symmetricDifference (const OtherConvex &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	symmetricDifference (const OtherTriangle &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	symmetricDifference (const OtherRectangle &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	symmetricDifference (const OtherRegion &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
auto	symmetricDifference (const OtherSet &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherPolygon &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherConvex &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherTriangle &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherRectangle &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherRegion &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherPolyline &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherChain &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherSegment &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherSegment>
PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherSegment &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
PolygonSet< Point< ResultNumber, typename PointType::LabelType > >	minkowskiSum (const OtherSet &other) const
	Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions.
template<PointConcept OtherPoint>
constexpr bool	contains (const OtherPoint &point) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<SegmentConcept OtherSegment>
constexpr bool	contains (const OtherSegment &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	contains (const OtherOrientedSegment &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<LineConcept OtherLine>
constexpr bool	contains (const OtherLine &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	contains (const OtherOrientedLine &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<RayConcept OtherRay>
constexpr bool	contains (const OtherRay &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	contains (const OtherHalfplane &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<RectangleConcept OtherRectangle>
constexpr bool	contains (const OtherRectangle &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<TriangleConcept OtherTriangle>
constexpr bool	contains (const OtherTriangle &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<ConvexConcept OtherConvex>
constexpr bool	contains (const OtherConvex &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<PolygonConcept OtherPolygon>
constexpr bool	contains (const OtherPolygon &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<PolygonConcept OtherPolygon>
constexpr bool	containsChainBased (const OtherPolygon &other) const
	Same contract as contains(const OtherPolygon&) const, by the chain-pair strategy alone.
template<DiskConcept OtherDisk>
constexpr bool	contains (const OtherDisk &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
constexpr bool	contains (const Shape< PointType > &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<class EmptyPoint>
constexpr bool	contains (const EmptyShape< EmptyPoint > &) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<class EmptyPoint>
constexpr bool	boundaryContains (const EmptyShape< EmptyPoint > &) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<class EmptyPoint>
constexpr bool	interiorContains (const EmptyShape< EmptyPoint > &) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PointConcept OtherPoint>
constexpr bool	interiorContains (const OtherPoint &point) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<SegmentConcept OtherSegment>
constexpr bool	interiorContains (const OtherSegment &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<SegmentConcept OtherSegment>
constexpr bool	interiorContainsInterior (const OtherSegment &other) const
	Tests whether this shape's interior contains the segment's interior.
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	interiorContains (const OtherOrientedSegment &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<LineConcept OtherLine>
constexpr bool	interiorContains (const OtherLine &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	interiorContains (const OtherOrientedLine &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<RayConcept OtherRay>
constexpr bool	interiorContains (const OtherRay &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	interiorContains (const OtherHalfplane &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<RectangleConcept OtherRectangle>
constexpr bool	interiorContains (const OtherRectangle &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<TriangleConcept OtherTriangle>
constexpr bool	interiorContains (const OtherTriangle &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<ConvexConcept OtherConvex>
constexpr bool	interiorContains (const OtherConvex &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PolygonConcept OtherPolygon>
constexpr bool	interiorContains (const OtherPolygon &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PointConcept OtherPoint>
constexpr bool	boundaryContains (const OtherPoint &point) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<SegmentConcept OtherSegment>
constexpr bool	boundaryContains (const OtherSegment &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	boundaryContains (const OtherOrientedSegment &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<LineConcept OtherLine>
constexpr bool	boundaryContains (const OtherLine &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	boundaryContains (const OtherOrientedLine &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<RayConcept OtherRay>
constexpr bool	boundaryContains (const OtherRay &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	boundaryContains (const OtherHalfplane &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<RectangleConcept OtherRectangle>
constexpr bool	boundaryContains (const OtherRectangle &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<TriangleConcept OtherTriangle>
constexpr bool	boundaryContains (const OtherTriangle &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<ConvexConcept OtherConvex>
constexpr bool	boundaryContains (const OtherConvex &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<PolygonConcept OtherPolygon>
constexpr bool	boundaryContains (const OtherPolygon &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<DiskConcept OtherDisk>
constexpr bool	boundaryContains (const OtherDisk &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<PointConcept OtherPoint>
constexpr bool	boundaryContains (const Shape< OtherPoint > &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<DiskConcept OtherDisk>
constexpr bool	interiorContains (const OtherDisk &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PointConcept OtherPoint>
constexpr bool	separates (const OtherPoint &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	separates (const OtherHalfplane &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<RectangleConcept OtherRectangle>
constexpr bool	separates (const OtherRectangle &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<TriangleConcept OtherTriangle>
constexpr bool	separates (const OtherTriangle &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<DiskConcept OtherDisk>
constexpr bool	separates (const OtherDisk &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<ConvexConcept OtherConvex>
constexpr bool	separates (const OtherConvex &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<PolygonConcept OtherPolygon>
constexpr bool	separates (const OtherPolygon &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<MonotoneChainConcept OtherChain>
constexpr bool	contains (const OtherChain &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<MonotoneChainConcept OtherChain>
constexpr bool	boundaryContains (const OtherChain &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<MonotoneChainConcept OtherChain>
constexpr bool	interiorContains (const OtherChain &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<MonotoneChainConcept OtherChain>
constexpr bool	intersects (const OtherChain &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<MonotoneChainConcept OtherChain>
constexpr bool	interiorsIntersect (const OtherChain &other) const
	Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
template<MonotoneChainConcept OtherChain>
constexpr bool	separates (const OtherChain &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<MonotoneChainConcept OtherChain>
constexpr bool	crosses (const OtherChain &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
constexpr auto	squaredDistance (const OtherChain &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
constexpr auto	distanceL1 (const OtherChain &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
constexpr auto	distanceLInf (const OtherChain &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<PolylineConcept OtherPolyline>
constexpr bool	contains (const OtherPolyline &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<PolylineConcept OtherPolyline>
constexpr bool	boundaryContains (const OtherPolyline &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<PolylineConcept OtherPolyline>
constexpr bool	interiorContains (const OtherPolyline &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PolylineConcept OtherPolyline>
constexpr bool	intersects (const OtherPolyline &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<PolylineConcept OtherPolyline>
constexpr bool	interiorsIntersect (const OtherPolyline &other) const
	Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
template<PolylineConcept OtherPolyline>
constexpr bool	separates (const OtherPolyline &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<HalfplaneIntersectionConcept OtherRegion>
constexpr bool	contains (const OtherRegion &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<HalfplaneIntersectionConcept OtherRegion>
constexpr bool	boundaryContains (const OtherRegion &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<HalfplaneIntersectionConcept OtherRegion>
constexpr bool	interiorContains (const OtherRegion &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<HalfplaneIntersectionConcept OtherRegion>
constexpr bool	separates (const OtherRegion &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<PolygonWithHolesConcept OtherRegion>
constexpr bool	contains (const OtherRegion &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<PolygonWithHolesConcept OtherRegion>
constexpr bool	boundaryContains (const OtherRegion &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<PolygonWithHolesConcept OtherRegion>
constexpr bool	interiorContains (const OtherRegion &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PolygonWithHolesConcept OtherRegion>
bool	separates (const OtherRegion &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<PolygonSetConcept OtherSet>
constexpr bool	contains (const OtherSet &other) const
	Tests whether this shape contains the other shape (A ⊇ B).
template<PolygonSetConcept OtherSet>
constexpr bool	boundaryContains (const OtherSet &other) const
	Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
template<PolygonSetConcept OtherSet>
constexpr bool	interiorContains (const OtherSet &other) const
	Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
template<PolygonSetConcept OtherSet>
bool	separates (const OtherSet &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<PolylineConcept OtherPolyline>
constexpr bool	crosses (const OtherPolyline &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
constexpr auto	squaredDistance (const OtherPolyline &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
constexpr auto	distanceL1 (const OtherPolyline &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
constexpr auto	distanceLInf (const OtherPolyline &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<PointConcept OtherPoint>
constexpr bool	intersects (const OtherPoint &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<SegmentConcept OtherSegment>
constexpr bool	intersects (const OtherSegment &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	intersects (const OtherOrientedSegment &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<LineConcept OtherLine>
constexpr bool	intersects (const OtherLine &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	intersects (const OtherOrientedLine &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<RayConcept OtherRay>
constexpr bool	intersects (const OtherRay &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	intersects (const OtherHalfplane &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<RectangleConcept OtherRectangle>
constexpr bool	intersects (const OtherRectangle &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<TriangleConcept OtherTriangle>
constexpr bool	intersects (const OtherTriangle &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<ConvexConcept OtherConvex>
constexpr bool	intersects (const OtherConvex &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<PolygonConcept OtherPolygon>
constexpr bool	intersects (const OtherPolygon &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<PolygonConcept OtherPolygon>
constexpr bool	boundariesIntersect (const OtherPolygon &other) const
	Tests whether the two polygon boundaries share at least one point (∂A ∩ ∂B ≠ ∅).
template<PolygonConcept OtherPolygon>
constexpr bool	boundariesStrongCross (const OtherPolygon &other) const
	Tests whether the two polygon boundaries have mononotone chains that strong cross.
template<DiskConcept OtherDisk>
constexpr bool	intersects (const OtherDisk &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<PointConcept OtherPoint>
constexpr bool	interiorsIntersect (const OtherPoint &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<LineConcept OtherLine>
constexpr bool	interiorsIntersect (const OtherLine &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	interiorsIntersect (const OtherOrientedLine &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<SegmentConcept OtherSegment>
constexpr bool	interiorsIntersect (const OtherSegment &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	interiorsIntersect (const OtherOrientedSegment &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<RayConcept OtherRay>
constexpr bool	interiorsIntersect (const OtherRay &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	interiorsIntersect (const OtherHalfplane &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<RectangleConcept OtherRectangle>
constexpr bool	interiorsIntersect (const OtherRectangle &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<TriangleConcept OtherTriangle>
constexpr bool	interiorsIntersect (const OtherTriangle &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<ConvexConcept OtherConvex>
constexpr bool	interiorsIntersect (const OtherConvex &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<PolygonConcept OtherPolygon>
constexpr bool	interiorsIntersect (const OtherPolygon &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<DiskConcept OtherDisk>
constexpr bool	interiorsIntersect (const OtherDisk &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<SegmentConcept OtherSegment>
constexpr bool	separates (const OtherSegment &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	separates (const OtherOrientedSegment &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<RayConcept OtherRay>
constexpr bool	separates (const OtherRay &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<LineConcept OtherLine>
constexpr bool	separates (const OtherLine &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	separates (const OtherOrientedLine &other) const
	Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
template<PointConcept OtherPoint>
constexpr bool	crosses (const OtherPoint &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<SegmentConcept OtherSegment>
constexpr bool	crosses (const OtherSegment &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool	crosses (const OtherOrientedSegment &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<RayConcept OtherRay>
constexpr bool	crosses (const OtherRay &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<LineConcept OtherLine>
constexpr bool	crosses (const OtherLine &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<OrientedLineConcept OtherOrientedLine>
constexpr bool	crosses (const OtherOrientedLine &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<HalfplaneConcept OtherHalfplane>
constexpr bool	crosses (const OtherHalfplane &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<RectangleConcept OtherRectangle>
constexpr bool	crosses (const OtherRectangle &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<TriangleConcept OtherTriangle>
constexpr bool	crosses (const OtherTriangle &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<ConvexConcept OtherConvex>
constexpr bool	crosses (const OtherConvex &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<DiskConcept OtherDisk>
constexpr bool	crosses (const OtherDisk &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<PolygonConcept OtherPolygon>
constexpr bool	crosses (const OtherPolygon &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<PointConcept OtherPoint>
constexpr bool	crosses (const Shape< OtherPoint > &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<PointConcept OtherPoint>
constexpr bool	intersects (const Shape< OtherPoint > &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<PointConcept OtherPoint>
constexpr bool	interiorsIntersect (const Shape< OtherPoint > &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)
constexpr bool	crosses (const OtherShape &other) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)
constexpr bool	intersects (const OtherShape &other) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)
constexpr bool	interiorsIntersect (const OtherShape &other) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<class EmptyPoint>
constexpr bool	crosses (const EmptyShape< EmptyPoint > &) const
	Tests whether the two shapes mutually separate each other (each disconnects the other).
template<class EmptyPoint>
constexpr bool	intersects (const EmptyShape< EmptyPoint > &) const
	Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
template<class EmptyPoint>
constexpr bool	interiorsIntersect (const EmptyShape< EmptyPoint > &) const
	Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
constexpr auto	squaredDistance (const OtherPoint &point) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
constexpr auto	squaredDistance (const OtherSegment &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto	squaredDistance (const OtherOrientedSegment &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
constexpr auto	squaredDistance (const OtherLine &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
constexpr auto	squaredDistance (const OtherOrientedLine &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
constexpr auto	squaredDistance (const OtherRay &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
constexpr auto	squaredDistance (const OtherHalfplane &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
constexpr auto	squaredDistance (const OtherRectangle &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
constexpr auto	squaredDistance (const OtherTriangle &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
constexpr auto	squaredDistance (const OtherConvex &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
constexpr auto	squaredDistance (const OtherPolygon &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self) { o.template squaredDistance<ResultNumber>(self); })
constexpr auto	squaredDistance (const OtherShape &other) const
	Returns the squared Euclidean distance to the given shape.
template<class ResultNumber = double, class DiskPointType, class DiskLabel>
detail::floating_result_t< ResultNumber >	squaredDistance (const Disk< DiskPointType, DiskLabel > &disk) const
	Returns the squared Euclidean distance to a disk.
template<class ResultNumber = NumberType, BoundedPolygonalConcept OtherShape> requires detail::ClosestPairConcept<Polygon<PointType_, TLabel>, OtherShape>
constexpr auto	closestSegments (const OtherShape &other) const
	Returns the pair of elements realizing the distance, nothing when the shapes meet.
template<class ResultNumber = division_result_t<NumberType>, class OtherShape> requires detail::ClosestPointsPairConcept<Polygon<PointType_, TLabel>, OtherShape>
constexpr auto	closestPoints (const OtherShape &other) const
	Returns the pair of points realizing the distance, nothing when the shapes meet.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
constexpr auto	distanceL1 (const OtherPoint &point) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
constexpr auto	distanceL1 (const OtherSegment &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto	distanceL1 (const OtherOrientedSegment &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
constexpr auto	distanceL1 (const OtherLine &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
constexpr auto	distanceL1 (const OtherOrientedLine &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
constexpr auto	distanceL1 (const OtherRay &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
constexpr auto	distanceL1 (const OtherHalfplane &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
constexpr auto	distanceL1 (const OtherRectangle &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
constexpr auto	distanceL1 (const OtherTriangle &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
constexpr auto	distanceL1 (const OtherConvex &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
constexpr auto	distanceL1 (const OtherPolygon &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self) { o.template distanceL1<ResultNumber>(self); })
constexpr auto	distanceL1 (const OtherShape &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
constexpr auto	intersection (const Shape< OtherPoint > &other) const
	Returns the intersection of the two shapes (A ∩ B), re-dispatching through the wrapper's own intersection.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
auto	regularizedIntersection (const Shape< OtherPoint > &other) const
	Re-dispatches a regularized intersection through a runtime shape.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
auto	regularizedUnion (const Shape< OtherPoint > &other) const
	Returns the regularized union of the two shapes (A ∪ B), re-dispatching through the wrapper's own regularizedUnion.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
auto	difference (const Shape< OtherPoint > &other) const
	Returns the regularized set difference of the two shapes (A ∖ B), re-dispatching through the wrapper's own difference.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
auto	symmetricDifference (const Shape< OtherPoint > &other) const
	Returns the regularized symmetric difference of the two shapes (A △ B), re-dispatching through the wrapper's own symmetricDifference.
template<class ResultNumber = double, PointConcept OtherPoint>
constexpr auto	distanceL1 (const Shape< OtherPoint > &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
constexpr auto	distanceLInf (const OtherPoint &point) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
constexpr auto	distanceLInf (const OtherSegment &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto	distanceLInf (const OtherOrientedSegment &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
constexpr auto	distanceLInf (const OtherLine &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
constexpr auto	distanceLInf (const OtherOrientedLine &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
constexpr auto	distanceLInf (const OtherRay &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
constexpr auto	distanceLInf (const OtherHalfplane &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
constexpr auto	distanceLInf (const OtherRectangle &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
constexpr auto	distanceLInf (const OtherTriangle &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
constexpr auto	distanceLInf (const OtherConvex &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
constexpr auto	distanceLInf (const OtherPolygon &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self) { o.template distanceLInf<ResultNumber>(self); })
constexpr auto	distanceLInf (const OtherShape &other) const
	Returns the Chebyshev (LInf) distance to the given shape.
template<class ResultNumber = double, PointConcept OtherPoint>
constexpr auto	distanceLInf (const Shape< OtherPoint > &other) const
	Returns the Manhattan (L1) distance to the given shape.
template<class ResultNumber = NumberType, PointConcept OtherPoint>
constexpr std::optional< Point< ResultNumber, typename PointType::LabelType > >	intersection (const OtherPoint &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherSegment &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherOrientedSegment &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherLine &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherOrientedLine &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherRay &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherPolygon &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherConvex &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherTriangle &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherRectangle &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires (!PointConcept<OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self) { o.template intersection<ResultNumber>(self); })
auto	intersection (const OtherShape &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires (!PointConcept<OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self) { o.template regularizedIntersection<ResultNumber>(self); })
auto	regularizedIntersection (const OtherShape &other) const
	Forwards a regularized intersection to the shape that owns it.
template<class ResultNumber = NumberType, class EmptyPoint>
constexpr EmptyShape< EmptyPoint >	intersection (const EmptyShape< EmptyPoint > &) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > >	intersection (const OtherHalfplane &other) const
	Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
constexpr auto	intersection (const OtherPolyline &other) const
	Returns the intersection with an open polyline (A ∩ B), a sequence of points and segments.
template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
constexpr auto	intersection (const OtherChain &other) const
	Returns the intersection with a monotone chain (A ∩ B), a sequence of points and segments.
constexpr Polygon	rotated90 (int k=1) const
	Returns the polygon rotated by 90k degrees around the origin.
constexpr void	rotate90 (int k=1)
	Rotates the polygon by 90k degrees around the origin in place.
constexpr void	untangle ()
	Makes the polygon simple in place by uncrossing its boundary.
template<class OtherNumber>
constexpr Polygon	scaledUpX (const OtherNumber scalar) const
	Returns the polygon with its x-coordinates multiplied by a factor.
template<class OtherNumber>
constexpr void	scaleUpX (const OtherNumber scalar)
	Multiplies the polygon's x-coordinates by a factor in place.
template<class OtherNumber>
constexpr Polygon	scaledUpY (const OtherNumber scalar) const
	Returns the polygon with its y-coordinates multiplied by a factor.
template<class OtherNumber>
constexpr void	scaleUpY (const OtherNumber scalar)
	Multiplies the polygon's y-coordinates by a factor in place.
template<class OtherNumber>
constexpr Polygon	scaledDownX (const OtherNumber scalar) const
	Returns the polygon with its x-coordinates divided by a divisor.
template<class OtherNumber>
constexpr void	scaleDownX (const OtherNumber scalar)
	Divides the polygon's x-coordinates by a divisor in place.
template<class OtherNumber>
constexpr Polygon	scaledDownY (const OtherNumber scalar) const
	Returns the polygon with its y-coordinates divided by a divisor.
template<class OtherNumber>
constexpr void	scaleDownY (const OtherNumber scalar)
	Divides the polygon's y-coordinates by a divisor in place.
template<class OtherShape> requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>
constexpr auto	minkowskiSum (const OtherShape &other) const
	Returns the Minkowski sum of this shape and another (A ⊕ B).
template<class OtherShape> requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>
constexpr auto	minkowskiErosion (const OtherShape &other) const
	Returns the Minkowski erosion of this shape by another (A ⊖ B).
template<class ResultNumber = division_result_t<NumberType>, class OtherShape> requires (!MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape> && BoundedPolygonalConcept<OtherShape>)
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiErosion (const OtherShape &other) const
	Returns the regularized Minkowski erosion of this shape by a bounded polygonal one (A ⊖ B), as a set of regions.
template<PointConcept OtherPoint>
constexpr Polygon &	operator+= (const OtherPoint &translation)
	Translates the polygon by the given point.
template<PointConcept OtherPoint>
constexpr Polygon &	operator-= (const OtherPoint &translation)
	Translates the polygon by the negation of the given point.
template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr Polygon &	operator*= (const Scalar &scalar)
	Scales the polygon by the given scalar.
template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr Polygon &	operator/= (const Scalar &scalar)
	Divides the polygon by the given scalar.
template<class ResultNumber, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherPolygon &other) const
template<class ResultNumber, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherConvex &other) const
template<class ResultNumber, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherTriangle &other) const
template<class ResultNumber, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherRectangle &other) const
template<class ResultNumber, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherRegion &other) const
template<class ResultNumber, PolygonSetConcept OtherSet>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherSet &other) const
template<class ResultNumber, HalfplaneIntersectionConcept OtherIntersection>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherIntersection &other) const
template<class ResultNumber, HalfplaneConcept OtherHalfplane>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	difference (const OtherHalfplane &other) const
template<class ResultNumber, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	regularizedUnion (const OtherPolygon &other) const
template<class ResultNumber, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	regularizedUnion (const OtherConvex &other) const
template<class ResultNumber, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	regularizedUnion (const OtherTriangle &other) const
template<class ResultNumber, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	regularizedUnion (const OtherRectangle &other) const
template<class ResultNumber, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	regularizedUnion (const OtherRegion &other) const
template<class ResultNumber, PolygonConcept OtherPolygon>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	symmetricDifference (const OtherPolygon &other) const
template<class ResultNumber, ConvexConcept OtherConvex>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	symmetricDifference (const OtherConvex &other) const
template<class ResultNumber, TriangleConcept OtherTriangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	symmetricDifference (const OtherTriangle &other) const
template<class ResultNumber, RectangleConcept OtherRectangle>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	symmetricDifference (const OtherRectangle &other) const
template<class ResultNumber, PolygonWithHolesConcept OtherRegion>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	symmetricDifference (const OtherRegion &other) const
template<class ResultNumber, PolygonConcept OtherPolygon>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherPolygon &other) const
template<class ResultNumber, ConvexConcept OtherConvex>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherConvex &other) const
template<class ResultNumber, TriangleConcept OtherTriangle>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherTriangle &other) const
template<class ResultNumber, RectangleConcept OtherRectangle>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherRectangle &other) const
template<class ResultNumber, PolygonWithHolesConcept OtherRegion>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherRegion &other) const
template<class ResultNumber, SegmentConcept OtherSegment>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherSegment &other) const
template<class ResultNumber, OrientedSegmentConcept OtherOriented>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherOriented &other) const
template<class ResultNumber, PolylineConcept OtherPolyline>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherPolyline &other) const
template<class ResultNumber, MonotoneChainConcept OtherChain>
PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherChain &other) const
template<class ResultNumber, PolygonSetConcept OtherSet>
PolygonSet< Point< ResultNumber, typename PointType_::LabelType > >	minkowskiSum (const OtherSet &other) const
template<class OtherNumber>
constexpr Polygon< PointType, LabelType >	scaledUpX (const OtherNumber scalar) const
template<class OtherNumber>
constexpr Polygon< PointType, LabelType >	scaledUpY (const OtherNumber scalar) const
template<class OtherNumber>
constexpr Polygon< PointType, LabelType >	scaledDownX (const OtherNumber scalar) const
template<class OtherNumber>
constexpr Polygon< PointType, LabelType >	scaledDownY (const OtherNumber scalar) const

Detailed Description

template<class PointType_, class TLabel>
struct pgl::Polygon< PointType_, TLabel >

Closed simple polygon stored by its vertices.

A simple polygon stored by its vertices plus a translation.

Polygon mirrors the storage layout of Convex — a vector of vertices and a translation_ applied lazily on access — but makes no convexity assumption. The boundary is the closed polyline through the vertices in the stored order, with the last vertex joined back to the first.

The constructor normalizes the vertex sequence to a canonical form: it is oriented counterclockwise and rotated so the lexicographically smallest vertex (smallest x, ties broken by smallest y) comes first. Because a constant translation preserves both orientation and lexicographic order, operator==/operator<=> give a translation-consistent geometric equality.

Template Parameters

PointType_

The vertex point type.

Member Typedef Documentation

BoundaryType

template<class PointType_, class TLabel>

template<bool Oriented>

using pgl::Polygon< PointType_, TLabel >::BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>>

EdgeIterator

template<class PointType_, class TLabel>

using pgl::Polygon< PointType_, TLabel >::EdgeIterator = BoundaryIterator<false>

LabelType

template<class PointType_, class TLabel>

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

NumberType

template<class PointType_, class TLabel>

using pgl::Polygon< PointType_, TLabel >::NumberType = PointType::NumberType

OrientedEdgeIterator

template<class PointType_, class TLabel>

using pgl::Polygon< PointType_, TLabel >::OrientedEdgeIterator = BoundaryIterator<true>

PointType

template<class PointType_, class TLabel>

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

Constructor & Destructor Documentation

Polygon() [1/4]

template<class PointType_, class TLabel>

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

constexprdefault

Creates a polygon with no vertex.

Polygon() [2/4]

template<class PointType_, class TLabel>

template<std::ranges::input_range Range = std::initializer_list<PointType>>
requires std::ranges::common_range<Range> && std::convertible_to<std::ranges::range_value_t<Range>, PointType>

pgl::Polygon< PointType_, TLabel >::Polygon ( Range && points, bool trusted = false )

inlineexplicitconstexpr

Creates a polygon from a range of points.

The points must be given in the order they appear along the boundary. Unless trusted is set, the vertices are normalized to the canonical form (counterclockwise, lexicographically smallest vertex first).

Template Parameters

Range

Input range whose elements can be converted to PointType.

Parameters

points	Range of boundary points in order.
trusted	Set to true if the points are already in canonical form.

Polygon() [3/4]

template<class PointType_, class TLabel>

pgl::Polygon< PointType_, TLabel >::Polygon ( std::initializer_list< NumberType > coords, bool trusted = false )

inlineexplicitconstexpr

Creates a polygon from a flat list of coordinates.

The values are consumed in pairs (x0, y0, x1, y1, …), each pair forming one boundary vertex in order, so the list must hold an even number of values. Unless trusted is set, the vertices are normalized to the canonical form (counterclockwise, lexicographically smallest vertex first).

Parameters

coords	Interleaved x/y coordinates of the boundary vertices.
trusted	Set to true if the points are already in canonical form.

Polygon() [4/4]

template<class PointType_, class TLabel>

template<PointConcept OtherPointType, class OtherLabelType>
requires (std::constructible_from<PointType, const OtherPointType&>)

pgl::Polygon< PointType_, TLabel >::Polygon ( const Polygon< OtherPointType, OtherLabelType > & other )

inlineconstexpr

Converts a polygon with compatible vertex type.

The source is already canonical and a translation/type conversion preserves that, so no renormalization is needed.

Template Parameters

OtherPointType

Source vertex type.

Parameters

other

Source polygon.

Member Function Documentation

area()

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>>

auto pgl::Polygon< PointType_, TLabel >::area ( ) const

inlineconstexpr

Computes the area of the polygon.

Warning

Uses division by 2.

asBitMatrix()

template<class PointType_, class TLabel>
requires (std::signed_integral<ResultNumber>)

template<class ResultNumber>
requires (std::signed_integral<ResultNumber>)

auto pgl::Polygon< PointType_, TLabel >::asBitMatrix ( ) const

nodiscard

Rasterizes this polygon into a BitMatrix, one bit per covered cell.

Equivalent to BitMatrix(*this): the window is the bounding box and the set cells are the ones the polygon covers. Only a rectilinear polygon is exactly a set of grid cells, so every edge must be axis-parallel; use innerRaster or outerRaster to approximate any other polygon.

A cell is an integer position, so the coordinates must be whole numbers too. An integer polygon rasterizes as it stands; one over a Rational or a floating-point type is checked vertex by vertex and throws unless every coordinate happens to be whole – rounding one would move the polygon.

Template Parameters

ResultNumber

Integer coordinate type of the grid (default: the coordinate type itself when it is a signed integer, the integer a Rational is built on, and int64_t otherwise).

Returns

A BitMatrix over the bounding box, covering this polygon.

Exceptions

std::logic_error

If an edge is not axis-parallel, or a coordinate is not a whole number the grid can hold.

asPolygonSet()

template<class PointType_, class TLabel>

PolygonSet< PointType > pgl::Polygon< PointType_, TLabel >::asPolygonSet ( ) const

inlinenodiscardconstexpr

Returns the polygon as a one-component set of regions.

A polygon with no area covers nothing that survives regularization, so it gives back the empty set rather than a component without area.

Returns

PolygonSet whose only component is this polygon as a region.

asPolygonWithHoles()

template<class PointType_, class TLabel>

PolygonWithHoles< PointType > pgl::Polygon< PointType_, TLabel >::asPolygonWithHoles ( ) const

inlinenodiscardconstexpr

Returns the polygon as a hole-free region.

The boundary is already canonical, and a region without holes needs no further normalization.

Returns

PolygonWithHoles whose outer boundary is this polygon and which has no holes.

bbox()

template<class PointType, class LabelType>

const Rectangle< PointType > & pgl::Polygon< PointType, LabelType >::bbox ( ) const

constexpr

Computes the bounding box of the polygon.

Unlike Convex::bbox, a simple polygon has no monotone boundary structure to exploit, so the corners come from a linear scan. The result is computed on the first call and cached in bbox_; later calls return the stored value. Any operation that modifies the polygon resets the cache.

Complexity: O(n) for n vertices on the first call, O(1) thereafter.

Returns

A constant reference to the rectangle bounding the polygon.

begin()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::begin ( ) const

inlineconstexpr

Returns a constant iterator to the first vertex.

boundariesIntersect()

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::boundariesIntersect ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Tests whether the two polygon boundaries share at least one point (∂A ∩ ∂B ≠ ∅).

Decomposes each boundary into its maximal lexicographically monotone chains — MonotoneChainView spans into one buffer per polygon — and tests them with MonotoneChain's linear merge sweep. The two decompositions are produced in lockstep and every newly produced chain is tested against all already-produced chains of the other polygon, so all computed pairs are covered before the next chain is built and the search stops at the first shared point. This underlies both intersects and interiorsIntersect, which add the interior reasoning on top.

Returns

true if the boundaries touch or cross anywhere.

boundariesStrongCross()

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::boundariesStrongCross ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Tests whether the two polygon boundaries have mononotone chains that strong cross.

Returns

true if two monotone chains strong cross.

boundaryContains() [1/19]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::boundaryContains ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [2/19]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [3/19]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherConvex & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [4/19]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherDisk & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [5/19]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherHalfplane & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [6/19]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherLine & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [7/19]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherOrientedLine & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [8/19]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherOrientedSegment & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [9/19]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherPoint & point ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

Complexity: O(n) for n vertices.

boundaryContains() [10/19]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [11/19]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [12/19]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherRay & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [13/19]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherRectangle & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

Complexity: O(n) per edge for n vertices.

boundaryContains() [14/19]

template<class PointType_, class TLabel>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType_, TLabel >::boundaryContains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

A boundary has no area, so it holds only a region with no area — which is exactly the union of that region's ring edges.

boundaryContains() [15/19]

template<class PointType, class LabelType>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [16/19]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherSegment & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

True iff the segment lies within a single boundary edge (the simple-polygon model also used by Convex::boundaryContains).

Complexity: O(n) for n vertices.

boundaryContains() [17/19]

template<class PointType_, class TLabel>

template<PolygonSetConcept OtherSet>

bool pgl::Polygon< PointType_, TLabel >::boundaryContains ( const OtherSet & other ) const

inlinenodiscardconstexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

boundaryContains() [18/19]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const OtherTriangle & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

Complexity: O(n) per edge for n vertices.

boundaryContains() [19/19]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::boundaryContains ( const Shape< OtherPoint > & other ) const

constexpr

Tests whether this shape's boundary contains the other shape (∂A ⊇ B).

cbegin()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::cbegin ( ) const

inlineconstexpr

Returns a constant iterator to the first vertex.

cend()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::cend ( ) const

inlineconstexpr

Returns a constant iterator past the last vertex.

centroid()

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>>

Point< ResultNumber > pgl::Polygon< PointType_, TLabel >::centroid ( ) const

inlineconstexpr

Computes the area-weighted centroid of the polygon.

Template Parameters

ResultNumber

The number type for the result.

Warning

Uses division by 3 and the area, so the result may be inexact even for floating-point types.

chainCount()

template<class PointType_, class TLabel>

std::size_t pgl::Polygon< PointType_, TLabel >::chainCount ( ) const

inlinenodiscardconstexpr

Counts the maximal lexicographically monotone chains the boundary decomposes into, without building any of them.

Consecutive boundary vertices of a simple polygon are distinct, so every edge runs strictly lex-up or lex-down and the boundary breaks into chains exactly at the vertices where that direction reverses. Counting those reversals is one pass and no allocation, and it returns precisely the number of chains BoundaryChains would produce: two for a convex polygon, up to n for a comb or a star, and zero for a boundary collapsed to a single point (no reversal exists there).

The count is what the chain-pair boundary tests pay for quadratically, so it is the input the sweep-versus-chains dispatch reads (see preferSweep).

Complexity: O(n) for n vertices.

Returns

The number of maximal lexicographically monotone boundary chains.

clearlyVisibleVertices()

template<class PointType, class LabelType>

std::vector< PointType > pgl::Polygon< PointType, LabelType >::clearlyVisibleVertices ( const PointType & query ) const

nodiscard

The polygon vertices clearly visible from query.

The strict counterpart of visibleVertices, matching clearVisibilityGraph: the open segment query–v must lie in the interior of the polygon and hold no other vertex, so neither grazing nor passing through a vertex counts. Always a subset of visibleVertices.

Parameters

query

Point to look from; outside the polygon nothing is visible.

Returns

The clearly visible vertices, ordered as in visibleVertices.

clearVisibilityGraph()

template<class PointType, class LabelType>

Graph< PointType > pgl::Polygon< PointType, LabelType >::clearVisibilityGraph ( ) const

nodiscard

Returns the clear visibility graph of the polygon vertices.

Two vertices are adjacent exactly when the open segment joining them lies in the interior of the polygon and contains no other vertex — the strict reading of visibility, which admits neither grazing nor passing through a vertex. The polygon's own sides are therefore absent, their relative interiors lying on the boundary, and what remains is exactly the set of legal triangulation diagonals. Always a subgraph of visibilityGraph.

The answer is meaningful for a simple polygon. A degenerate polygon has no interior, so its vertices come back with no edges at all.

Complexity: as visibilityGraph, with no convex shortcut.

Returns

An undirected graph whose vertices are this polygon's vertices.

closestPoints()

template<class PointType_, class TLabel>
requires detail::ClosestPointsPairConcept<Polygon<PointType_, TLabel>, OtherShape>

template<class ResultNumber, class OtherShape>
requires detail::ClosestPointsPairConcept<Polygon<PointType_, TLabel>, OtherShape>

auto pgl::Polygon< PointType_, TLabel >::closestPoints ( const OtherShape & other ) const

nodiscardconstexpr

Returns the pair of points realizing the distance, nothing when the shapes meet.

The first point lies on this shape and the second on other. Empty exactly when squaredDistance is zero. Unlike closestSegments this also takes an unbounded convex other — a line, an oriented line, a ray, a half-plane, a half-plane intersection — which realizes the distance at a point on no edge and at no vertex: there is no element to name there, but there is still a point to give.

Template Parameters

ResultNumber

Coordinate type of the returned points (default: division_result_t).

Warning

A point interior to an element comes from a division, so with an integer ResultNumber it truncates. Request a floating-point or pgl::Rational result type for an accurate value.

closestSegments()

template<class PointType_, class TLabel>
requires detail::ClosestPairConcept<Polygon<PointType_, TLabel>, OtherShape>

template<class ResultNumber, BoundedPolygonalConcept OtherShape>
requires detail::ClosestPairConcept<Polygon<PointType_, TLabel>, OtherShape>

auto pgl::Polygon< PointType_, TLabel >::closestSegments ( const OtherShape & other ) const

nodiscardconstexpr

Returns the pair of elements realizing the distance, nothing when the shapes meet.

The first element is this shape's, the second is other's; each is one of the shape's edges, degenerate to a vertex where the shape has none. Empty exactly when squaredDistance is zero.

Template Parameters

ResultNumber

Coordinate type of the returned segments (default: NumberType).

Warning

other's coordinates and labels are re-expressed in this shape's, so a narrower ResultNumber loses them.

contains() [1/19]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::contains ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [2/19]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [3/19]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherConvex & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

Complexity: O((n + m) log n) for n and m vertices.

contains() [4/19]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherDisk & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

A non-degenerate closed disk lies in the closed polygon iff its center is contained and no boundary edge cuts into the open disk (so the disk cannot poke out through a reflex notch). A degenerate disk reduces to a segment.

Complexity: O(n) for n vertices.

contains() [5/19]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherHalfplane & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [6/19]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherLine & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [7/19]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherOrientedLine & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [8/19]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherOrientedSegment & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

Complexity: O(n log n) for n vertices.

contains() [9/19]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherPoint & point ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

Uses an exact winding-number test, preceded by an explicit boundary check so the closed boundary counts as contained.

Complexity: O(n) for n vertices.

contains() [10/19]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

For simple polygons (no holes) this holds iff every edge of other is contained, which is what this checks.

Complexity: O((n + m) log n) for n and m vertices.

contains() [11/19]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [12/19]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherRay & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [13/19]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherRectangle & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

Complexity: O(n log n) for n vertices.

contains() [14/19]

template<class PointType_, class TLabel>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType_, TLabel >::contains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

A region is contained exactly when its outer polygon is: the region holds the whole outer ring whatever its holes do, and this shape has a connected complement. See implementation/contains.hpp.

contains() [15/19]

template<class PointType, class LabelType>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [16/19]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherSegment & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

The segment is split at its boundary intersections and each piece is classified by its midpoint, so the test is correct for non-convex polygons (both endpoints inside does not suffice).

Complexity: O(n log n) for n vertices.

contains() [17/19]

template<class PointType_, class TLabel>

template<PolygonSetConcept OtherSet>

bool pgl::Polygon< PointType_, TLabel >::contains ( const OtherSet & other ) const

inlinenodiscardconstexpr

Tests whether this shape contains the other shape (A ⊇ B).

contains() [18/19]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::contains ( const OtherTriangle & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

Complexity: O(n log n) for n vertices.

contains() [19/19]

template<class PointType, class LabelType>

bool pgl::Polygon< PointType, LabelType >::contains ( const Shape< PointType > & other ) const

constexpr

Tests whether this shape contains the other shape (A ⊇ B).

containsChainBased()

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::containsChainBased ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Same contract as contains(const OtherPolygon&) const, by the chain-pair strategy alone.

Reaches the same answer by testing this polygon's and other's lexicographically monotone chains (see BoundaryChains) against each other pairwise instead of running a combined plane sweep. Cheaper when both boundaries are near-convex (few chains), since its cost is the product of the two chain counts; that product degrades to O(n * m) on a jagged, comb-like or star-shaped boundary, where sweepContains stays at O((n + m) log(n + m)) regardless.

contains calls whichever of the two preferSweep judges cheaper for the operands at hand, so reach for it rather than this; naming this one commits to the chain strategy even where the sweep would win by two orders of magnitude. It stays public so a benchmark can time the two strategies against each other over the same inputs.

Complexity: O(chains(A) * chains(B) * average chain length), i.e. O(n) for near-convex input and O(n * m) in the worst case.

convexCovering()

template<class PointType_, class TLabel>

std::vector< Convex< PointType_ > > pgl::Polygon< PointType_, TLabel >::convexCovering ( ) const

nodiscard

Covers this polygon with convex hulls derived from triangle cliques.

The polygon is triangulated and the paper's dual-graph BFS builds a full-visibility subgraph: triangles are graph vertices and every edge certifies that the endpoints' joint convex hull lies in the polygon. A DSATUR vertex clique cover is then converted into convex pieces by taking the hull of every clique. This is the Delaunay-partition variant of the clique-cover construction of Abrahamsen, Meyling, and Nusser (SoCG 2023).

The polygon has the same precondition as triangulation: simple and non-degenerate. Every piece is contained in this polygon and their union is the polygon, but unlike convexPartition their interiors may overlap. Redundant pieces are removed; the result is not necessarily a minimum-cardinality cover.

A convex polygon comes back as a single piece.

Complexity: O(n^3 log n) worst-case time and O(n^2) space for n polygon vertices; the dual search usually avoids most of the quadratic candidate pairs even though the worst-case bound is unchanged.

Returns

The convex covering, in canonical order.

convexHull()

template<class PointType_, class TLabel>

Convex< PointType > pgl::Polygon< PointType_, TLabel >::convexHull ( ) const

inlineconstexpr

Returns the convex hull of the polygon's vertices.

convexPartition()

template<class PointType_, class TLabel>

std::vector< Convex< PointType_ > > pgl::Polygon< PointType_, TLabel >::convexPartition ( ) const

nodiscard

Cuts this polygon into convex pieces with disjoint interiors.

Equivalent to triangulation().convexPartition(), and the polygon has the same precondition it does: simple and non-degenerate. The pieces' union is the polygon and their interiors are pairwise disjoint, so anything additive over a decomposition — an area, a sweep, a Minkowski sum — may be summed over them. There are at most four times as many as the fewest possible; see Triangulation::convexPartition for why that is all one should want.

A convex polygon comes back as a single piece.

Returns

The convex pieces, in canonical order.

crosses() [1/17]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::crosses ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [2/17]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

Warning

Relies on the not-yet-implemented separates and throws.

crosses() [3/17]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherConvex & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [4/17]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherDisk & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [5/17]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherHalfplane & ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [6/17]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherLine & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [7/17]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherOrientedLine & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [8/17]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherOrientedSegment & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [9/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherPoint & ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [10/17]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [11/17]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [12/17]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherRay & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [13/17]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherRectangle & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [14/17]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherSegment & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [15/17]

template<class PointType_, class TLabel>

template<typename OtherShape>
requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)

bool pgl::Polygon< PointType_, TLabel >::crosses ( const OtherShape & other ) const

inlinenodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [16/17]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::crosses ( const OtherTriangle & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

crosses() [17/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::crosses ( const Shape< OtherPoint > & other ) const

nodiscardconstexpr

Tests whether the two shapes mutually separate each other (each disconnects the other).

diameter()

template<class PointType_, class TLabel>

Segment< PointType > pgl::Polygon< PointType_, TLabel >::diameter ( ) const

inlineconstexpr

Returns a segment realizing the diameter (the farthest vertex pair).

The farthest pair of vertices of a simple polygon lies on its convex hull, so this builds a Convex from the polygon vertices and returns that hull's Convex::diameter(). Distances are compared exactly via squared length.

Returns

A longest segment between two vertices (degenerate if fewer than two vertices).

difference() [1/17]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherConvex &

other

)

const

difference() [2/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherConvex & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

difference() [3/17]

template<class PointType_, class TLabel>

template<class ResultNumber, HalfplaneConcept OtherHalfplane>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherHalfplane &

other

)

const

difference() [4/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherHalfplane & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

A half-plane is the one-constraint half-plane intersection, and is handled as one: see difference(const OtherIntersection&) const.

difference() [5/17]

template<class PointType_, class TLabel>

template<class ResultNumber, HalfplaneIntersectionConcept OtherIntersection>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherIntersection &

other

)

const

difference() [6/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherIntersection & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

A half-plane intersection may be unbounded, which stops it being a regularizedUnion operand but not a subtrahend: A ∖ B is bounded whenever A is, however far B reaches, so a PolygonSet can hold it. See PolygonWithHoles::difference(const OtherIntersection&) const for the clip that bounds it and for the rest of the contract.

difference() [7/17]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherPolygon< PointType_, TLabel > &

other

)

const

difference() [8/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

The result is closure(A° ∖ B): the part of this polygon with area that survives the removal, as a set of regions with pairwise disjoint interiors whose union is the difference. Lower-dimensional leftovers — a stretch of the boundary that other touches without covering, an isolated contact point — are dropped, which is the usual convention for boolean operations on solids and what makes the result a set of regions.

This is the construction PolygonWithHoles exists for: removing a polygon from the middle of another one leaves a hole, which no other shape in the library can express. Unlike intersection(const OtherPolygon&) const, which never needs one, this is where the nesting matters.

The pieces are not nested: an island of this polygon stranded inside a hole of the result comes back as a region of its own.

Complexity: O(m²) for m boundary edges, then a constrained triangulation over the arrangement of both boundaries.

Template Parameters

ResultNumber

The number type for the result.

Parameters

other

The shape to remove.

Returns

The pieces of the difference, in canonical order.

Note

The arrangement is built over exact rationals whatever ResultNumber is, and converted only at the end. So an integral result type is exact whenever the boundaries cross at integral points, and truncates only where they genuinely do not.

difference() [9/17]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherRectangle &

other

)

const

difference() [10/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherRectangle & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

difference() [11/17]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherRegion &

other

)

const

difference() [12/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherRegion & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

difference() [13/17]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonSetConcept OtherSet>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherSet &

other

)

const

difference() [14/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherSet & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

A difference is not symmetric, so this pair stays here rather than going to the higher-ranked set the way regularizedUnion(const OtherSet&) const does. It costs no more for it: the set goes into the one arrangement whole, exactly as it would have on the other side. See difference(const OtherPolygon&) const for the contract.

difference() [15/17]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::difference

(

const OtherTriangle &

other

)

const

difference() [16/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::difference ( const OtherTriangle & other ) const

nodiscard

Returns the regularized set difference of the two shapes (A ∖ B).

difference() [17/17]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::difference ( const Shape< OtherPoint > & other ) const

inlinenodiscard

Returns the regularized set difference of the two shapes (A ∖ B), re-dispatching through the wrapper's own difference.

A difference is not symmetric, so unlike regularizedUnion this cannot be handed to other as it stands. It wraps this shape instead and lets the wrapper visit both sides, which throws if the pair is unsupported — here, whenever other turns out to hold anything without area, or a Disk. An unbounded alternative is fine on this side, the result being contained in this shape either way. See difference(const OtherPolygon&) const for the contract.

The point type is deduced from other so a plain concrete shape cannot reach this overload through an implicit conversion to Shape.

distanceL1() [1/15]

template<class PointType_, class TLabel>

template<class ResultNumber, MonotoneChainConcept OtherChain>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherChain & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [2/15]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherConvex & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [3/15]

template<class PointType_, class TLabel>

template<class ResultNumber, HalfplaneConcept OtherHalfplane>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherHalfplane & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [4/15]

template<class PointType_, class TLabel>

template<class ResultNumber, LineConcept OtherLine>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherLine & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [5/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedLineConcept OtherOrientedLine>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherOrientedLine & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [6/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherOrientedSegment & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [7/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherPoint & point ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [8/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [9/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolylineConcept OtherPolyline>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherPolyline & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [10/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RayConcept OtherRay>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherRay & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [11/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherRectangle & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [12/15]

template<class PointType_, class TLabel>

template<class ResultNumber, SegmentConcept OtherSegment>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherSegment & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [13/15]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, typename OtherShape>
requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self)
{ o.template distanceL1<ResultNumber>(self); })

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherShape & other ) const

inlinenodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

Forwards to the other shape's implementation so that each unordered pair needs distanceL1 defined only once, on the higher-ranked shape.

distanceL1() [14/15]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const OtherTriangle & other ) const

nodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

distanceL1() [15/15]

template<class PointType_, class TLabel>

template<class ResultNumber = double, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::distanceL1 ( const Shape< OtherPoint > & other ) const

inlinenodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

Distance is symmetric, so this just calls other's own distanceL1, which visits its wrapped alternative and throws if the pair is unsupported.

distanceLInf() [1/15]

template<class PointType_, class TLabel>

template<class ResultNumber, MonotoneChainConcept OtherChain>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherChain & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [2/15]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherConvex & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [3/15]

template<class PointType_, class TLabel>

template<class ResultNumber, HalfplaneConcept OtherHalfplane>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherHalfplane & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [4/15]

template<class PointType_, class TLabel>

template<class ResultNumber, LineConcept OtherLine>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherLine & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [5/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedLineConcept OtherOrientedLine>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherOrientedLine & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [6/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherOrientedSegment & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [7/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherPoint & point ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [8/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [9/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolylineConcept OtherPolyline>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherPolyline & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [10/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RayConcept OtherRay>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherRay & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [11/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherRectangle & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [12/15]

template<class PointType_, class TLabel>

template<class ResultNumber, SegmentConcept OtherSegment>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherSegment & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [13/15]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, typename OtherShape>
requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self)
{ o.template distanceLInf<ResultNumber>(self); })

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherShape & other ) const

inlinenodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

Forwards to the other shape's implementation so that each unordered pair needs distanceLInf defined only once, on the higher-ranked shape.

distanceLInf() [14/15]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const OtherTriangle & other ) const

nodiscardconstexpr

Returns the Chebyshev (LInf) distance to the given shape.

distanceLInf() [15/15]

template<class PointType_, class TLabel>

template<class ResultNumber = double, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::distanceLInf ( const Shape< OtherPoint > & other ) const

inlinenodiscardconstexpr

Returns the Manhattan (L1) distance to the given shape.

Distance is symmetric, so this just calls other's own distanceL1, which visits its wrapped alternative and throws if the pair is unsupported.

edges()

template<class PointType_, class TLabel>

std::vector< Segment< PointType > > pgl::Polygon< PointType_, TLabel >::edges ( ) const

inlineconstexpr

Returns the edges of the polygon.

edgesBegin()

template<class PointType_, class TLabel>

EdgeIterator pgl::Polygon< PointType_, TLabel >::edgesBegin ( ) const

inlineconstexpr

Returns an iterator to the first unoriented edge.

Returns

Iterator to edge (vertex 0, vertex 1).

edgesEnd()

template<class PointType_, class TLabel>

EdgeIterator pgl::Polygon< PointType_, TLabel >::edgesEnd ( ) const

inlineconstexpr

Returns an iterator past the last unoriented edge.

Returns

Sentinel iterator for edgesBegin().

edgesView()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::edgesView ( ) const

inlineconstexpr

Returns a lazy view over the edges, materializing each Segment on the fly instead of allocating a vector.

Same edge sequence as edges() (including the closing edge back to vertex 0) but with no heap allocation, so it is preferable when the edges are only iterated once — e.g. inside predicate loops.

empty()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::empty ( ) const

inlinenodiscardconstexpr

Returns whether the polygon is the empty set of points.

A polygon with no vertices covers nothing, which is the state of a default-constructed one and of every polygon-valued result that comes back empty. It behaves as EmptyShape: every predicate reads it as the empty set.

Complexity: O(1).

Returns

true if the polygon covers no point.

end()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::end ( ) const

inlineconstexpr

Returns a constant iterator past the last vertex.

fbox()

template<class PointType, class LabelType>

template<std::floating_point ResultNumber>

Rectangle< Point< ResultNumber > > pgl::Polygon< PointType, LabelType >::fbox ( ) const

constexpr

Computes the floating-point bounding box of the polygon.

Template Parameters

ResultNumber

The floating-point type for the result.

Returns

A rectangle with floating-point coordinates representing the bounding box.

get()

template<class PointType_, class TLabel>

PointType pgl::Polygon< PointType_, TLabel >::get ( std::ptrdiff_t index ) const

inlineconstexpr

Cyclic access: same as operator[] but index is taken modulo size(); negative indices wrap from the end. Useful for iterating polygon edges where the last edge wraps around.

getIfPoint()

template<class PointType_, class TLabel>

std::optional< PointType > pgl::Polygon< PointType_, TLabel >::getIfPoint ( ) const

inlinenodiscardconstexpr

Returns the point the polygon collapses to, if it does.

Complexity: O(n), returning at the first differing vertex.

Returns

The common vertex if isPoint, std::nullopt otherwise.

getIfSegment()

template<class PointType_, class TLabel>

std::optional< BoundaryType< false > > pgl::Polygon< PointType_, TLabel >::getIfSegment ( ) const

inlinenodiscardconstexpr

Returns the segment the polygon collapses to, if it does.

Complexity: O(n).

Returns

The spanned segment if isSegment, std::nullopt otherwise.

getStarShapedKernel()

template<class PointType_, class TLabel>

std::optional< HalfplaneIntersection< PointType_ > > pgl::Polygon< PointType_, TLabel >::getStarShapedKernel ( ) const

nodiscardconstexpr

Returns the kernel: the set of points that see the whole polygon.

Returns the kernel: the set of points that see the whole polygon.

A point p of the polygon belongs to the kernel when the segment pq stays inside the polygon for every point q of it. For a simple polygon the kernel is exactly the intersection of the closed half-planes bounded by the edge lines and lying on the interior side, hence convex — that intersection is what is returned.

The answer is only meaningful for a simple polygon (isSimple); as elsewhere in the library, a self-intersecting boundary is outside the contract. Degenerate polygons are handled: one collapsed to a point or a segment is its own kernel. The empty polygon (empty) and an undefined one (isUndefined) yield std::nullopt.

Complexity: O(n log n) for n vertices.

Returns

The kernel, or std::nullopt when it is empty (the polygon is not star-shaped).

A point p of the polygon belongs to the kernel when the segment pq stays inside the polygon for every point q of it. For a simple polygon the kernel is exactly the intersection of the closed half-planes bounded by the edge lines and lying on the interior side, hence convex — that intersection is what is returned.

The answer is only meaningful for a simple polygon (isSimple); as elsewhere in the library, a self-intersecting boundary is outside the contract. Degenerate polygons are handled: one collapsed to a point or a segment is its own kernel. The empty polygon (empty) and an undefined one (isUndefined) yield std::nullopt.

Complexity: O(n log n) for n vertices.

Returns

The kernel, or std::nullopt when it is empty (the polygon is not star-shaped).

Defined here because the result type must be complete: the polygon's vertices are canonically counterclockwise, so the interior lies to the left of every boundary edge and the kernel is built by inserting the half-plane of each edge in turn. Repeated consecutive vertices contribute no edge line and are skipped; collinear ones give a redundant constraint that HalfplaneIntersection::insert discards.

Defined here because the result type must be complete: the polygon's vertices are canonically counterclockwise, so the interior lies to the left of every boundary edge and the kernel is built by inserting the half-plane of each edge in turn. Repeated consecutive vertices contribute no edge line and are skipped; collinear ones give a redundant constraint that HalfplaneIntersection::insert discards.

index()

template<class PointType_, class TLabel>

std::ptrdiff_t pgl::Polygon< PointType_, TLabel >::index ( const PointType & point ) const

inlineconstexpr

Returns the smallest index i with (*this)[i] == point, or -1 if point is not a vertex.

Complexity: O(n) for n vertices (linear scan, since a simple polygon has no monotone structure to binary-search).

Parameters

point

The vertex to locate.

Returns

The vertex index, or -1 if point is not a vertex.

interiorContains() [1/18]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::interiorContains ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [2/18]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [3/18]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherConvex & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Complexity: O((n + m) log n) for n and m vertices.

interiorContains() [4/18]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherDisk & other ) const

nodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [5/18]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherHalfplane & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [6/18]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherLine & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [7/18]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherOrientedLine & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [8/18]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherOrientedSegment & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Complexity: O(n) for n vertices.

interiorContains() [9/18]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherPoint & point ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

True iff the point is contained but lies on no edge. A polygon with fewer than three vertices has empty interior, so the result is always false.

Complexity: O(n) for n vertices.

interiorContains() [10/18]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Like contains(const Polygon&), this reduces to an edge-by-edge check, which is exact for simple polygons (no holes).

Complexity: O((n + m) log n) for n and m vertices.

interiorContains() [11/18]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [12/18]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherRay & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [13/18]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherRectangle & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Complexity: O(n log n) for n vertices.

interiorContains() [14/18]

template<class PointType_, class TLabel>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType_, TLabel >::interiorContains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [15/18]

template<class PointType, class LabelType>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [16/18]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherSegment & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Requires both endpoints strictly inside and no contact with the boundary, so a segment cannot dip out through a reflex notch and return.

Complexity: O(n) for n vertices.

interiorContains() [17/18]

template<class PointType_, class TLabel>

template<PolygonSetConcept OtherSet>

bool pgl::Polygon< PointType_, TLabel >::interiorContains ( const OtherSet & other ) const

inlinenodiscardconstexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

interiorContains() [18/18]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::interiorContains ( const OtherTriangle & other ) const

constexpr

Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).

Complexity: O(n log n) for n vertices.

interiorContainsInterior()

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::interiorContainsInterior ( const OtherSegment & other ) const

constexpr

Tests whether this shape's interior contains the segment's interior.

Every point of the open segment must lie strictly inside the polygon; either endpoint may lie on the polygon boundary. A degenerate segment is accepted exactly when its sole point is contained.

Complexity: O(n) for n vertices.

interiorsIntersect() [1/17]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::interiorsIntersect ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

interiorsIntersect() [2/17]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).

interiorsIntersect() [3/17]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherConvex & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

interiorsIntersect() [4/17]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherDisk & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

interiorsIntersect() [5/17]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherHalfplane & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n) for n vertices.

interiorsIntersect() [6/17]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherLine & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n) for n vertices.

interiorsIntersect() [7/17]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherOrientedLine & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n) for n vertices.

interiorsIntersect() [8/17]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherOrientedSegment & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n^2) for n vertices.

interiorsIntersect() [9/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherPoint & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n) for n vertices.

interiorsIntersect() [10/17]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

interiorsIntersect() [11/17]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).

interiorsIntersect() [12/17]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherRay & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n^2) for n vertices.

interiorsIntersect() [13/17]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherRectangle & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

interiorsIntersect() [14/17]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherSegment & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n^2) for n vertices.

interiorsIntersect() [15/17]

template<class PointType_, class TLabel>

template<typename OtherShape>
requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)

bool pgl::Polygon< PointType_, TLabel >::interiorsIntersect ( const OtherShape & other ) const

inlinenodiscardconstexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Forwards to the other shape's implementation so that each unordered pair needs interiorsIntersect defined only once, on the higher-ranked shape.

interiorsIntersect() [16/17]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const OtherTriangle & other ) const

constexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

interiorsIntersect() [17/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::interiorsIntersect ( const Shape< OtherPoint > & other ) const

nodiscardconstexpr

Tests whether the interiors of the two shapes intersect ((A∖∂A) ∩ (B∖∂B) ≠ ∅).

intersection() [1/16]

template<class PointType_, class TLabel>

template<class ResultNumber = NumberType, class EmptyPoint>

EmptyShape< EmptyPoint > pgl::Polygon< PointType_, TLabel >::intersection ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

intersection() [2/16]

template<class PointType, class LabelType>

template<class ResultNumber, MonotoneChainConcept OtherChain>

auto pgl::Polygon< PointType, LabelType >::intersection ( const OtherChain & other ) const

nodiscardconstexpr

Returns the intersection with a monotone chain (A ∩ B), a sequence of points and segments.

Same contract as intersection(const OtherPolyline&) const: Polygon outranks MonotoneChain and owns the pair. The chain is viewed as a Polyline (its lexicographic vertex order is a valid traversal) and clipped against the polygon.

Template Parameters

ResultNumber	Number type of the returned coordinates.
OtherChain	Type of the monotone chain.

Parameters

other

Monotone chain to intersect with.

Returns

Vector of points and segments forming the intersection.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [3/16]

template<class PointType, class LabelType>

template<class ResultNumber, ConvexConcept OtherConvex>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherConvex & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Forwards to the intersection(const Polygon&) overload via the convex polygon's Convex::asPolygon representation.

Template Parameters

ResultNumber	The number type for the result.
OtherConvex	The convex polygon type.

Parameters

other

The convex polygon to intersect with.

Returns

The intersection components: points, polylines, and polygons.

intersection() [4/16]

template<class PointType, class LabelType>

template<class ResultNumber, HalfplaneConcept OtherHalfplane>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherHalfplane & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

The boundary of the intersection region P ∩ H is (∂P ∩ H) ∪ (∂H ∩ P), so the method clips every polygon edge to the closed half-plane and clips the half-plane's boundary line to the polygon (via intersection(const Line&)), collecting the pieces into a deduplicated set. They are assembled exactly as in intersection(const Polygon&) – a graph whose nodes have degree at most two (asserted) – into isolated Point components, Segment components, and Polygon components, returned in no particular order. Unlike the polygon overload the 1D pieces are Segment rather than Polyline, because every 1D part of the intersection lies on the half-plane's straight boundary and so is collinear.

Complexity: O(n log n) for n vertices.

Template Parameters

ResultNumber	The number type for the result.
OtherPoint	The point type of the half-plane.

Parameters

other

The half-plane to intersect with.

Returns

The intersection components: points, segments, and polygons.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [5/16]

template<class PointType, class LabelType>

template<class ResultNumber, LineConcept OtherLine>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherLine & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Since a polygon is bounded, the intersection of its closed region with an infinite line is a bounded set of disjoint pieces: each is either a Point (an isolated boundary touch) or a Segment (a maximal chord), returned in order along the line. An empty vector means no intersection.

Uses the same exact, division-free ray-parity sweep as intersection(const Segment&), but without clipping to a finite range.

Complexity: O(n log n) for n vertices.

Template Parameters

ResultNumber	The number type for the result.
OtherPoint	The point type of the line.

Parameters

other

The line to intersect with.

Returns

The disjoint intersection pieces in order along the line.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [6/16]

template<class PointType, class LabelType>

template<class ResultNumber, OrientedLineConcept OtherOrientedLine>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherOrientedLine & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Same as the Line overload, ignoring orientation.

Complexity: O(n log n) for n vertices.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [7/16]

template<class PointType, class LabelType>

template<class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherOrientedSegment & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Same as the Segment overload, ignoring orientation.

Complexity: O(n log n) for n vertices.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [8/16]

template<class PointType, class LabelType>

template<class ResultNumber, PointConcept OtherPoint>

std::optional< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherPoint & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Template Parameters

ResultNumber	Coordinate type of the returned point.
OtherPoint	Point type.

Parameters

other

Point to intersect with.

Returns

The point when contained, otherwise empty.

intersection() [9/16]

template<class PointType, class LabelType>

template<class ResultNumber, PolygonConcept OtherPolygon>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

The boundary of the intersection region A ∩ B is exactly (∂A ∩ B) ∪ (∂B ∩ A), so the method clips every edge of each polygon against the other (via intersection(const Segment&)) and collects the resulting boundary pieces into a deduplicated set of points and segments. The segments are assembled into a graph whose nodes are endpoints; in a non-degenerate configuration every node has degree at most two (asserted), so each connected component is an isolated node, a simple path, or a simple cycle. These become a Point, a Polyline, and a Polygon respectively, returned in no particular order.

Complexity: O(n m log(n + m)) for polygons with n and m vertices.

Template Parameters

ResultNumber	The number type for the result.
OtherPoint	The point type of the other polygon.

Parameters

other

The other polygon to intersect with.

Returns

The intersection components: points, polylines, and polygons.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [10/16]

template<class PointType, class LabelType>

template<class ResultNumber, PolylineConcept OtherPolyline>

auto pgl::Polygon< PointType, LabelType >::intersection ( const OtherPolyline & other ) const

nodiscardconstexpr

Returns the intersection with an open polyline (A ∩ B), a sequence of points and segments.

A polyline is 1-dimensional, so the intersection with this polygon's region is a set of points and segments. Polygon owns this pair (it outranks Polyline); the computation is the polyline clipped against the polygon, delegated to Polyline::polygonIntersection. The pieces carry the polyline's label, matching polyline.intersection(polygon).

Template Parameters

ResultNumber	Number type of the returned coordinates.
OtherPolyline	Type of the polyline.

Parameters

other

Polyline to intersect with.

Returns

Vector of points and segments forming the intersection.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [11/16]

template<class PointType, class LabelType>

template<class ResultNumber, RayConcept OtherRay>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherRay & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

A ray is its supporting line restricted to the half starting at the source, so the result is the disjoint pieces of that half inside the closed polygon: each is either a Point (an isolated boundary touch) or a Segment (a maximal chord), returned in order from the source outward. An empty vector means no intersection.

Uses the same exact, division-free ray-parity sweep as intersection(const Line&), clipped to the ray's half-line.

Complexity: O(n log n) for n vertices.

Template Parameters

ResultNumber	The number type for the result.
OtherPoint	The point type of the ray.

Parameters

other

The ray to intersect with.

Returns

The disjoint intersection pieces in order from the source outward.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [12/16]

template<class PointType, class LabelType>

template<class ResultNumber, RectangleConcept OtherRectangle>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherRectangle & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Forwards to the intersection(const Convex&) overload via the rectangle's Rectangle::asConvex representation.

Template Parameters

ResultNumber	The number type for the result.
OtherRectangle	The rectangle type.

Parameters

other

The rectangle to intersect with.

Returns

The intersection components: points, polylines, and polygons.

intersection() [13/16]

template<class PointType, class LabelType>

template<class ResultNumber, SegmentConcept OtherSegment>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherSegment & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Unlike Convex::intersection, a simple polygon need not be convex, so the intersection of its closed region with a segment can be several disjoint pieces. The pieces are returned in order along the segment (from its min() endpoint to its max() endpoint); each piece is either a Point (an isolated boundary touch) or a Segment (a maximal overlap with the closed region). An empty vector means no intersection.

The supporting line is split at every boundary crossing and each cell is classified by exact (division-free) ray parity, so the result is correct for reflex polygons where both endpoints may lie inside yet the segment dips out through a notch.

Complexity: O(n log n) for n vertices.

Template Parameters

ResultNumber	The number type for the result.
OtherPoint	The point type of the segment.

Parameters

other

The segment to intersect with.

Returns

The disjoint intersection pieces in order along the segment.

Warning

Divides coordinates after casting to ResultNumber.

intersection() [14/16]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, typename OtherShape>
requires (!PointConcept<OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape&
o, const Polygon& self) { o.template intersection<ResultNumber>(self); })

auto pgl::Polygon< PointType_, TLabel >::intersection ( const OtherShape & other ) const

inlinenodiscard

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Forwards to the other shape's implementation so that each unordered pair needs intersection defined only once, on the higher-ranked shape. The result is then the higher-ranked shape's: intersecting with a PolygonWithHoles gives regions, not the component vector the polygon-polygon overload returns.

intersection() [15/16]

template<class PointType, class LabelType>

template<class ResultNumber, TriangleConcept OtherTriangle>

std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, Polygon< Point< ResultNumber, typename PointType::LabelType > > > > pgl::Polygon< PointType, LabelType >::intersection ( const OtherTriangle & other ) const

nodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.

Forwards to the intersection(const Convex&) overload via the triangle's Triangle::asConvex representation.

Template Parameters

ResultNumber	The number type for the result.
OtherTriangle	The triangle type.

Parameters

other

The triangle to intersect with.

Returns

The intersection components: points, polylines, and polygons.

intersection() [16/16]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::intersection ( const Shape< OtherPoint > & other ) const

inlinenodiscardconstexpr

Returns the intersection of the two shapes (A ∩ B), re-dispatching through the wrapper's own intersection.

An intersection is symmetric, so this just calls other's own intersection, which visits its wrapped alternative and throws if the pair is unsupported.

The point type is deduced from other so a plain concrete shape cannot reach this overload through an implicit conversion to Shape.

Returns

The intersection wrapped in a Shape, rather than the tighter type the concrete pair would answer with: which alternative other holds is not known until run time, so neither is the result's.

intersects() [1/17]

template<class PointType_, class TLabel>

template<class EmptyPoint>

bool pgl::Polygon< PointType_, TLabel >::intersects ( const EmptyShape< EmptyPoint > & ) const

inlinenodiscardconstexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

intersects() [2/17]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

intersects() [3/17]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherConvex & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

intersects() [4/17]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherDisk & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

intersects() [5/17]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherHalfplane & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [6/17]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherLine & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [7/17]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherOrientedLine & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [8/17]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherOrientedSegment & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [9/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherPoint & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [10/17]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherPolygon< PointType_, TLabel > & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Decomposes both boundaries into monotone chains via boundariesIntersect; when the boundaries are disjoint a single point-in-polygon test each way settles containment.

intersects() [11/17]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

intersects() [12/17]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherRay & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [13/17]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherRectangle & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

intersects() [14/17]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherSegment & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n) for n vertices.

intersects() [15/17]

template<class PointType_, class TLabel>

template<typename OtherShape>
requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>)

bool pgl::Polygon< PointType_, TLabel >::intersects ( const OtherShape & other ) const

inlinenodiscardconstexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Forwards to the other shape's implementation so that each unordered pair needs intersects defined only once, on the higher-ranked shape.

intersects() [16/17]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::intersects ( const OtherTriangle & other ) const

constexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

Complexity: O(n m) for polygons with n and m vertices.

intersects() [17/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::intersects ( const Shape< OtherPoint > & other ) const

nodiscardconstexpr

Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).

isConvex()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isConvex ( ) const

inlinenodiscardconstexpr

Tests whether the polygon is convex.

True when every turn along the boundary has the same orientation, i.e. there is no reflex vertex (collinear vertices are permitted). The answer is only meaningful for a simple polygon (isSimple); as elsewhere in the library, a self-intersecting boundary is outside the contract. A polygon with fewer than three vertices is reported as non-convex.

Complexity: O(n).

Returns

true if the polygon is convex.

isDegenerate()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isDegenerate ( ) const

inlineconstexpr

Checks if the polygon is degenerate (has zero area).

The empty polygon has no area either, so it is degenerate.

Collinear vertices are what a well-defined polygon without area looks like, and isPoint / isSegment decide that exactly whatever the coordinates. Only isUndefined — a boundary that retraces itself — has no area without being collinear, and it is the one branch that needs the shoelace sum, taken in the promoted type. twiceArea() == 0 would instead narrow that sum to NumberType, where the area of an ordinary polygon past the coordinate range wraps to zero.

isPoint()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isPoint ( ) const

inlinenodiscardconstexpr

Checks whether the polygon covers exactly one point.

Complexity: O(n), returning at the first differing vertex.

Returns

true if the polygon has at least one vertex and all are equal.

isSegment()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isSegment ( ) const

inlinenodiscardconstexpr

Checks whether the polygon covers exactly one segment of positive length.

True when the vertices are collinear but not all equal. The boundary is a closed walk, so collinear vertices make it cover the single segment spanning them.

Complexity: O(n), returning at the first non-collinear vertex.

isSimple()

template<class PointType_, class LabelType>

template<class Rational>

bool pgl::Polygon< PointType_, LabelType >::isSimple ( ) const

nodiscard

Tests whether the polygon is simple (its boundary does not touch or cross itself).

Tests whether the polygon boundary is simple.

Uses a brute-force pairwise edge test in O(n^2) for few vertices (n <= 8) or floating-point coordinates, and the Bentley-Ottmann sweep (O(n log n)) for larger exact (integer or rational) polygons. A polygon with fewer than three vertices, or a zero-length edge (a repeated consecutive vertex), is not simple.

Template Parameters

Rational

Exact rational type used by the sweep for large polygons.

Returns

true if no two edges meet except adjacent edges at their shared vertex.

Integer and rational coordinates go to the exact sweep line, which needs them; floating-point ones go to the bounding-box sweep of detail::visitXYSweepPairs, which reaches the same verdict through the same predicates as the pairwise scan while testing only the pairs that can possibly meet. A polygon small enough for the pairwise scan to win takes it directly.

Template Parameters

Rational

Exact rational type used internally by the sweep line.

Returns

true if the edges only meet at the shared endpoints of consecutive edges.

isStarShaped()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isStarShaped ( ) const

inlinenodiscardconstexpr

Tests whether the polygon is star-shaped.

True when some point of the polygon sees all of it, i.e. when the kernel (getStarShapedKernel) is non-empty. Every convex polygon is star-shaped; the converse does not hold.

Complexity: O(n log n) for n vertices.

isUndefined()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::isUndefined ( ) const

inlinenodiscardconstexpr

Checks whether the polygon is degenerate without covering a point or a segment.

Zero area does not imply collinear vertices: a self-overlapping boundary whose signed area cancels out (or one that retraces a non-straight path) is degenerate yet covers more than a segment. Such a polygon is the only undefined case; the empty polygon is the well-defined empty set, so use empty for it.

Complexity: O(n).

label()

template<class PointType_, class TLabel>

template<class A = LabelType>
requires (detail::has_label_v<A>)

A & pgl::Polygon< PointType_, TLabel >::label ( ) const

inlineconstexpr

Returns the polygon label.

The label is mutable even through a const polygon: it is metadata that does not participate in equality, hashing, or geometric predicates.

Returns

Reference to the stored label.

latticePoints()

template<class PointType, class LabelType>
requires (detail::extended_integral<ResultNumber> || std::same_as<ResultNumber, BigInt>)

template<class ResultNumber>
requires (detail::extended_integral<ResultNumber> || std::same_as<ResultNumber, BigInt>)

std::vector< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType, LabelType >::latticePoints ( ) const

nodiscard

Returns the integer points the polygon contains.

The boundary included: a point on an edge is a point of the shape. The boundary answers for its own points, edge by edge as segments, and a sweep over the columns of the bounding box answers for the rest, so the cost is one pass over the edges plus one point per point reported.

Template Parameters

ResultNumber

Integer coordinate type of the points: the shape's own coordinate type when that is a signed integer, the integer a pgl::Rational is built on, and int64_t for anything else.

Returns

The lattice points, in increasing order, carrying no label.

Exceptions

std::logic_error	If a coordinate is not finite, or a lattice point of the shape does not fit ResultNumber.
std::length_error	If there are more of them than a vector holds.

minkowskiErosion() [1/2]

template<class PointType_, class TLabel>
requires (!MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape> && BoundedPolygonalConcept<OtherShape>)

template<class ResultNumber, class OtherShape>
requires (!MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape> && BoundedPolygonalConcept<OtherShape>)

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiErosion ( const OtherShape & other ) const

nodiscard

Returns the regularized Minkowski erosion of this shape by a bounded polygonal one (A ⊖ B), as a set of regions.

The pairs MinkowskiSummableConcept turns away, which for this receiver is every bounded operand: the erosion of a shape that is not convex is no more convex than it was, and it is not even connected – a dumbbell eroded by anything wider than its handle is two regions, for operands that are in no way degenerate. That is why this returns a PolygonSet where minkowskiSum returns one PolygonWithHoles, and the difference is structural rather than a missing guarantee.

The result is regularized, closure((A ⊖ B)°), as the sum and the boolean operations are: an erosion produces thin material readily – a corridor exactly as wide as the operand erodes to a curve – and a set of regions holds none of it. A receiver with no area erodes to the empty set for the same reason.

A convex receiver is answered by its own constraints in O(a·b); everything else pays for a complement, a sum and a difference. See implementation/minkowskierosion.hpp for both constructions and their cost.

Template Parameters

ResultNumber	Coordinate type of the result.
OtherShape	Type of the shape to erode by.

Parameters

other

Shape to erode by.

Returns

The erosion, as a PolygonSet.

Exceptions

std::logic_error

when other covers no point: that erosion is the whole plane, which no set of bounded regions represents.

minkowskiErosion() [2/2]

template<class PointType, class LabelType>
requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>

template<class OtherShape>
requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>

auto pgl::Polygon< PointType, LabelType >::minkowskiErosion ( const OtherShape & other ) const

nodiscardconstexpr

Returns the Minkowski erosion of this shape by another (A ⊖ B).

The erosion is the point set {x : x ⊕ B ⊆ A}, the translations of other that keep it inside this shape – equivalently ⋂ {A - b : b ∈ B}. It is the morphological dual of minkowskiSum and is defined for the same pairs, but it is not commutative.

Eroding by a Point is the translation by its negation, so it returns this shape's own type; the other pairs come back as the convex region they are, a HalfplaneIntersection, which holds a lower-dimensional erosion and the empty one as readily as a two-dimensional one. A polygon eroded by a bounded operand needs a PolygonSet, since an erosion can disconnect what it shrinks.

Eroding by a shape that covers no point is the whole plane, which a HalfplaneIntersection returns and the tighter result types cannot.

Template Parameters

OtherShape

Type of the shape to erode by.

Parameters

other

Shape to erode by.

Returns

The erosion, in the tightest type that represents it.

minkowskiSum() [1/21]

template<class PointType_, class TLabel>

template<class ResultNumber, MonotoneChainConcept OtherChain>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherChain &

other

)

const

minkowskiSum() [2/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherChain & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

A MonotoneChain summand is a polyline that happens to be sorted, and it sums here exactly as one: its monotonicity is what makes MonotoneChain::minkowskiSum(const OtherConvex&) const one polygon, and a non-convex receiver takes that away again — this polygon's own concavity can strand a cavity whatever the chain does. So the chain contributes its edges and the answer is one region, which may have holes.

minkowskiSum() [3/21]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherConvex &

other

)

const

minkowskiSum() [4/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherConvex & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

minkowskiSum() [5/21]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedSegmentConcept OtherOriented>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherOriented &

other

)

const

minkowskiSum() [6/21]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherPolygon< PointType_, TLabel > &

other

)

const

minkowskiSum() [7/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

The sum is {p + q : p ∈ A, q ∈ B}, regularized to closure((A ⊕ B)°) and returned as a region with holes. A non-convex operand is what makes that necessary: sliding a shape around the inside of a U sweeps out a region whose boundary closes over a hole, and no other shape in the library can say so. This is the gap PolygonWithHoles was proposed to close.

This polygon must be nondegenerate, and that is what buys the single region: a nondegenerate polygon is the closure of its connected interior, so A ⊕ B covers ⋃_{b ∈ B} (A° + b), which is connected and open for any connected B and whose closure is the sum. A degenerate polygon — one with no area — is not on this contract; the sum can then fall into several pieces, of which one comes back. An empty or wholly flat regularized sum is the empty region.

Distinguish this from minkowskiSum(const OtherShape&) const, which sums a bounded convex operand and returns a single Convex (or a Rectangle, or a translation of this polygon by a Point). The two never overlap: the pairs that fit in one shape are exactly the pairs MinkowskiSummableConcept accepts, and this overload set takes the rest.

Complexity: one convex merge per pair of triangles of the two operands' triangulations, then a constrained triangulation over the arrangement of all of them.

Template Parameters

ResultNumber

The number type for the result.

Parameters

other

The shape to sum with.

Returns

The sum, as one region.

Precondition

This polygon is nondegenerate.

Note

Every vertex of every piece sum is a sum of two input vertices, so the pieces are exact; only their union can put a vertex at a crossing, and that arrangement is built over exact rationals and converted to ResultNumber only at the end.

minkowskiSum() [8/21]

template<class PointType_, class TLabel>

template<class ResultNumber, PolylineConcept OtherPolyline>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherPolyline &

other

)

const

minkowskiSum() [9/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherPolyline & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

A Polyline summand has no area, but it sweeps this polygon along itself all the same, so the sum is a region like every other one here. This is the mirror of Polyline::minkowskiSum(const OtherPolygon&) const and gives the same single-region answer: which operand is written first never decides which sum answers.

minkowskiSum() [10/21]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherRectangle &

other

)

const

minkowskiSum() [11/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherRectangle & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

minkowskiSum() [12/21]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonWithHolesConcept OtherRegion>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherRegion &

other

)

const

minkowskiSum() [13/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherRegion & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

minkowskiSum() [14/21]

template<class PointType_, class TLabel>

template<class ResultNumber, SegmentConcept OtherSegment>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherSegment &

other

)

const

minkowskiSum() [15/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherSegment>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherSegment & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

An orientation is not part of a point set, so this is the sum with the underlying segment, vertex for vertex.

minkowskiSum() [16/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherSegment & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

The thinnest summand that still needs a region. A segment has no area, but sliding this polygon along one sweeps the band between the polygon and its translate by the segment's vector, and that band closes over a cavity for the same reason a wider summand's does: a C whose opening is no wider than the vector is plugged by the sweep of its own arms. The summand is a single convex piece, so this is the cheapest of these sums — one convex merge per triangle of the triangulated domain.

Distinguish it from segment + segment, which stays a single Convex: two bounded convex operands never need a region, and it is the receiver's concavity, not the summand's thinness, that brings one in. As everywhere here the result is regularized, so a summand that has collapsed to a point comes back empty rather than as a flat copy of this polygon.

minkowskiSum() [17/21]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonSetConcept OtherSet>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherSet &

other

)

const

minkowskiSum() [18/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherSet & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions.

A PolygonSet operand is the one whose answer needs a set whatever the other operand is: its components are disjoint, and a sum small relative to the gaps between them leaves them so. The set outranks every shape here and owns the pair, so this is the mirror spelling of PolygonSet::minkowskiSum, and the same call.

minkowskiSum() [19/21]

template<class PointType, class LabelType>
requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>

template<class OtherShape>
requires MinkowskiSummableConcept<Polygon<PointType_, TLabel>, OtherShape>

auto pgl::Polygon< PointType, LabelType >::minkowskiSum ( const OtherShape & other ) const

nodiscardconstexpr

Returns the Minkowski sum of this shape and another (A ⊕ B).

The sum is the point set {a + b : a ∈ A, b ∈ B}. Summing with a Point is a translation, so it returns this shape's own type; two bounded convex shapes sum to a Convex, or to a Rectangle when both are rectangles. See MinkowskiSummableConcept for the pairs a Minkowski sum is defined for.

Template Parameters

OtherShape

Type of the other shape.

Parameters

other

Shape to sum with.

Returns

The Minkowski sum, in the tightest type that represents it.

minkowskiSum() [20/21]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum

(

const OtherTriangle &

other

)

const

minkowskiSum() [21/21]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>

PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::minkowskiSum ( const OtherTriangle & other ) const

nodiscard

Returns the regularized Minkowski sum of the two shapes (A ⊕ B).

operator*=()

template<class PointType_, class TLabel>

template<class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

Polygon & pgl::Polygon< PointType_, TLabel >::operator*= ( const Scalar & scalar )

inlineconstexpr

Scales the polygon by the given scalar.

Complexity: O(n) for n vertices. Scaling by a negative factor flips the orientation, so the polygon is renormalized to stay canonical.

operator+=()

template<class PointType_, class TLabel>

template<PointConcept OtherPoint>

Polygon & pgl::Polygon< PointType_, TLabel >::operator+= ( const OtherPoint & translation )

inlineconstexpr

Translates the polygon by the given point.

Complexity: O(1).

operator-=()

template<class PointType_, class TLabel>

template<PointConcept OtherPoint>

Polygon & pgl::Polygon< PointType_, TLabel >::operator-= ( const OtherPoint & translation )

inlineconstexpr

Translates the polygon by the negation of the given point.

Complexity: O(1).

operator/=()

template<class PointType_, class TLabel>

template<class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

Polygon & pgl::Polygon< PointType_, TLabel >::operator/= ( const Scalar & scalar )

inlineconstexpr

Divides the polygon by the given scalar.

Complexity: O(n) for n vertices.

operator<=>()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::operator<=> ( const Polygon< PointType_, TLabel > & other ) const

inlineconstexpr

Compares two polygons by their canonical vertex sequences.

operator==()

template<class PointType_, class TLabel>

bool pgl::Polygon< PointType_, TLabel >::operator== ( const Polygon< PointType_, TLabel > & other ) const

inlineconstexpr

Checks equality of two polygons.

Returns

True if both polygons have the same vertices in the same order.

operator[]()

template<class PointType_, class TLabel>

const PointType pgl::Polygon< PointType_, TLabel >::operator[] ( std::size_t index ) const

inlineconstexpr

Accesses a vertex by index.

Parameters

index

The index of the vertex.

Returns

The vertex at the given index.

orientedEdges()

template<class PointType_, class TLabel>

std::vector< OrientedSegment< PointType > > pgl::Polygon< PointType_, TLabel >::orientedEdges ( ) const

inlineconstexpr

Returns the oriented edges of the polygon.

orientedEdgesBegin()

template<class PointType_, class TLabel>

OrientedEdgeIterator pgl::Polygon< PointType_, TLabel >::orientedEdgesBegin ( ) const

inlineconstexpr

Returns an iterator to the first oriented edge.

Returns

Iterator to edge vertex 0 -> vertex 1.

orientedEdgesEnd()

template<class PointType_, class TLabel>

OrientedEdgeIterator pgl::Polygon< PointType_, TLabel >::orientedEdgesEnd ( ) const

inlineconstexpr

Returns an iterator past the last oriented edge.

Returns

Sentinel iterator for orientedEdgesBegin().

orientedEdgesView()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::orientedEdgesView ( ) const

inlineconstexpr

Lazy view counterpart of orientedEdges(); see edgesView().

pointInside()

template<class PointType, class LabelType>

template<class ResultNumber>

Point< ResultNumber > pgl::Polygon< PointType, LabelType >::pointInside ( ) const

nodiscardconstexpr

Returns a point strictly inside the (simple) polygon.

Works for non-convex polygons. The lexicographically smallest vertex p0 (stored first in canonical form) is convex, so the triangle formed by p0 and its two boundary neighbours a, b lies locally inside the polygon. If no other vertex falls inside that triangle it is an ear and its interior point is returned; otherwise the lexicographically smallest vertex q inside the triangle yields a valid diagonal p0 q, and its midpoint is returned. Only meaningful for a simple polygon.

Complexity: O(n).

Template Parameters

ResultNumber

The number type for the result.

Returns

A point guaranteed to be inside the polygon.

Warning

The ear branch calls Triangle::pointInside and so divides coordinates by 4; the diagonal branch divides by 2. Inexact for integer coordinates not divisible by that factor.

pointInsideInteriorContainedIn()

template<class PointType, class LabelType>

template<class OtherShape>

bool pgl::Polygon< PointType, LabelType >::pointInsideInteriorContainedIn ( const OtherShape & shape ) const

nodiscardconstexpr

Tests whether some point in this shape's relative interior lies in the strict interior of shape.

Uses pointInside as the witness. When integer truncation rounds that witness onto or outside the boundary, this shape and shape are scaled so the witness is exact, leaving the containment relation unchanged.

reducedVisibilityGraph()

template<class PointType, class LabelType>

Graph< PointType > pgl::Polygon< PointType, LabelType >::reducedVisibilityGraph ( ) const

nodiscard

Returns the reduced visibility graph of the polygon vertices.

The subgraph of visibilityGraph holding the edges a shortest path inside the polygon can bend along: those tangent to the boundary at both ends. An edge uv is tangent at u when the two sides meeting at u lie in one closed half-plane of the line uv, which is what lets a taut path bend there. Every side survives; among the diagonals only the bitangents between reflex corners do, so this is far sparser than visibilityGraph.

This graph alone does not answer shortest-path queries. It guarantees only the interior of a geodesic — an edge strictly inside a shortest path has the path bending at both ends, hence is tangent at both and survives. A path does not bend at its own endpoints, so its first and last hop need no tangency and may have been pruned; a convex corner keeps only its two sides, and a route starting there comes back forced along the boundary. To route between two points, add each joined to everything it sees, taken from visibilityGraph.

The answer is meaningful for a simple polygon. A degenerate polygon has every vertex collinear with every side, so the tangency test passes everywhere and the result matches visibilityGraph.

Complexity: as visibilityGraph, plus O(m) for m visibility edges.

Returns

An undirected graph whose vertices are this polygon's vertices.

regularizedIntersection() [1/2]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, typename OtherShape>
requires (!PointConcept<OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape&
o, const Polygon& self) { o.template regularizedIntersection<ResultNumber>(self); })

auto pgl::Polygon< PointType_, TLabel >::regularizedIntersection ( const OtherShape & other ) const

inlinenodiscard

Forwards a regularized intersection to the shape that owns it.

regularizedIntersection() [2/2]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::regularizedIntersection ( const Shape< OtherPoint > & other ) const

inlinenodiscard

Re-dispatches a regularized intersection through a runtime shape.

regularizedUnion() [1/12]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion

(

const OtherConvex &

other

)

const

regularizedUnion() [2/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherConvex & other ) const

nodiscard

Returns the regularized union of the two shapes (A ∪ B).

regularizedUnion() [3/12]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion

(

const OtherPolygon< PointType_, TLabel > &

other

)

const

regularizedUnion() [4/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscard

Returns the regularized union of the two shapes (A ∪ B).

The result is closure(A° ∪ B°), as a set of regions with pairwise disjoint interiors. It needs PolygonWithHoles for the same reason the difference does: two shapes that wrap round between them enclose a hole neither of them has, as a U united with the bar that caps it.

Operands meeting only along a stretch of boundary or at a single point fuse only where they have area in common to fuse through — an isolated contact point comes back as two pieces meeting there, since a region may not have a self-touching outer ring. Disjoint operands come back as two pieces.

Complexity: O(m²) for m boundary edges, then a constrained triangulation over the arrangement of both boundaries.

Template Parameters

ResultNumber

The number type for the result.

Parameters

other

The shape to unite with.

Returns

The pieces of the union, in canonical order.

Note

The arrangement is built over exact rationals whatever ResultNumber is, and converted only at the end. So an integral result type is exact whenever the boundaries cross at integral points, and truncates only where they genuinely do not.

regularizedUnion() [5/12]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion

(

const OtherRectangle &

other

)

const

regularizedUnion() [6/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherRectangle & other ) const

nodiscard

Returns the regularized union of the two shapes (A ∪ B).

regularizedUnion() [7/12]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion

(

const OtherRegion &

other

)

const

regularizedUnion() [8/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherRegion & other ) const

nodiscard

Returns the regularized union of the two shapes (A ∪ B).

regularizedUnion() [9/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>

auto pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherSet & other ) const

inlinenodiscard

Returns the regularized union of the two shapes (A ∪ B).

A set of regions is the one PolygonalRegionConcept operand ranked above a polygon, and it states its operations over every operand at once, so this hands the pair back to it rather than restating it. A union is symmetric, so the order costs nothing — and going through the set is what puts every component into one arrangement instead of folding the polygon over them one at a time. See regularizedUnion(const OtherPolygon&) const for the contract.

regularizedUnion() [10/12]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion

(

const OtherTriangle &

other

)

const

regularizedUnion() [11/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const OtherTriangle & other ) const

nodiscard

Returns the regularized union of the two shapes (A ∪ B).

regularizedUnion() [12/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::regularizedUnion ( const Shape< OtherPoint > & other ) const

inlinenodiscard

Returns the regularized union of the two shapes (A ∪ B), re-dispatching through the wrapper's own regularizedUnion.

A union is symmetric, so this just calls other's own regularizedUnion, which visits its wrapped alternative and throws if the pair is unsupported — here, whenever other turns out to hold anything but a bounded polygonal region. See Polygon::regularizedUnion for the contract.

The point type is deduced from other so a plain concrete shape cannot reach this overload through an implicit conversion to Shape.

regularizedVisiblePolygon()

template<class PointType, class LabelType>

template<class ResultNumber>

Polygon< Point< ResultNumber > > pgl::Polygon< PointType, LabelType >::regularizedVisiblePolygon ( const PointType & query ) const

nodiscard

The part of the polygon visible from query, regularized.

The visibility polygon: every point reachable from query by a segment staying inside. Being star-shaped about query it is simply connected, so one Polygon holds it.

Regularized means the closure of the interior, which drops what grazing sight would otherwise add: a sightline running along the boundary, or straight through a vertex into a part 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 polygon's own 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. A query on the boundary is a vertex of the result.

The answer is meaningful for a simple polygon; a degenerate one bounds no area and gives an empty polygon.

Template Parameters

ResultNumber

Coordinate type of the result (default: division_result_t of the polygon's own).

Parameters

query

Point to look from.

Returns

The visible region, counterclockwise; empty when query lies outside the polygon.

rotate90()

template<class PointType, class LabelType>

void pgl::Polygon< PointType, LabelType >::rotate90 ( int k = 1 )

constexpr

Rotates the polygon by 90k degrees around the origin in place.

Parameters

k	Number of 90-degree CCW rotations (may be negative).

rotated90()

template<class PointType, class LabelType>

Polygon< PointType, LabelType > pgl::Polygon< PointType, LabelType >::rotated90 ( int k = 1 ) const

nodiscardconstexpr

Returns the polygon rotated by 90k degrees around the origin.

Parameters

k	Number of 90-degree CCW rotations (may be negative).

Returns

Rotated polygon.

samePointSet()

template<class PointType, class LabelType>

template<AnyShapeConcept OtherShape>

bool pgl::Polygon< PointType, LabelType >::samePointSet ( const OtherShape & other ) const

nodiscardconstexpr

Tests whether another shape defines exactly the same point set.

scaledDownX() [1/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon< PointType, LabelType > pgl::Polygon< PointType_, TLabel >::scaledDownX ( const OtherNumber scalar ) const

constexpr

scaledDownX() [2/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon pgl::Polygon< PointType_, TLabel >::scaledDownX ( const OtherNumber scalar ) const

nodiscardconstexpr

Returns the polygon with its x-coordinates divided by a divisor.

scaledDownY() [1/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon< PointType, LabelType > pgl::Polygon< PointType_, TLabel >::scaledDownY ( const OtherNumber scalar ) const

constexpr

scaledDownY() [2/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon pgl::Polygon< PointType_, TLabel >::scaledDownY ( const OtherNumber scalar ) const

nodiscardconstexpr

Returns the polygon with its y-coordinates divided by a divisor.

scaleDownX()

template<class PointType, class LabelType>

template<class OtherNumber>

void pgl::Polygon< PointType, LabelType >::scaleDownX ( const OtherNumber scalar )

constexpr

Divides the polygon's x-coordinates by a divisor in place.

scaleDownY()

template<class PointType, class LabelType>

template<class OtherNumber>

void pgl::Polygon< PointType, LabelType >::scaleDownY ( const OtherNumber scalar )

constexpr

Divides the polygon's y-coordinates by a divisor in place.

scaledUpX() [1/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon< PointType, LabelType > pgl::Polygon< PointType_, TLabel >::scaledUpX ( const OtherNumber scalar ) const

constexpr

scaledUpX() [2/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon pgl::Polygon< PointType_, TLabel >::scaledUpX ( const OtherNumber scalar ) const

nodiscardconstexpr

Returns the polygon with its x-coordinates multiplied by a factor.

scaledUpY() [1/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon< PointType, LabelType > pgl::Polygon< PointType_, TLabel >::scaledUpY ( const OtherNumber scalar ) const

constexpr

scaledUpY() [2/2]

template<class PointType_, class TLabel>

template<class OtherNumber>

Polygon pgl::Polygon< PointType_, TLabel >::scaledUpY ( const OtherNumber scalar ) const

nodiscardconstexpr

Returns the polygon with its y-coordinates multiplied by a factor.

scaleUpX()

template<class PointType, class LabelType>

template<class OtherNumber>

void pgl::Polygon< PointType, LabelType >::scaleUpX ( const OtherNumber scalar )

constexpr

Multiplies the polygon's x-coordinates by a factor in place.

scaleUpY()

template<class PointType, class LabelType>

template<class OtherNumber>

void pgl::Polygon< PointType, LabelType >::scaleUpY ( const OtherNumber scalar )

constexpr

Multiplies the polygon's y-coordinates by a factor in place.

separates() [1/17]

template<class PointType, class LabelType>

template<MonotoneChainConcept OtherChain>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherChain & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

The chain is an arc whose arc order is its lexicographic vertex order, so removing this polygon cuts the chain exactly when the chain has ordered points a < b < c with b inside the polygon and a, c outside (an edge carrying all three is a separated edge; otherwise a and c straddle a covered vertex or edge).

separates() [2/17]

template<class PointType, class LabelType>

template<ConvexConcept OtherConvex>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherConvex & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [3/17]

template<class PointType, class LabelType>

template<DiskConcept OtherDisk>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherDisk & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [4/17]

template<class PointType, class LabelType>

template<HalfplaneConcept OtherHalfplane>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherHalfplane & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [5/17]

template<class PointType, class LabelType>

template<LineConcept OtherLine>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherLine & other ) const

constexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [6/17]

template<class PointType, class LabelType>

template<OrientedLineConcept OtherOrientedLine>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherOrientedLine & other ) const

constexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [7/17]

template<class PointType, class LabelType>

template<OrientedSegmentConcept OtherOrientedSegment>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherOrientedSegment & other ) const

constexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [8/17]

template<class PointType, class LabelType>

template<PointConcept OtherPoint>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherPoint & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

Polygon

Polygon-vs-shape cut predicates.

separates() [9/17]

template<class PointType, class LabelType>

template<PolygonConcept OtherPolygon>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [10/17]

template<class PointType, class LabelType>

template<PolylineConcept OtherPolyline>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherPolyline & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

Set semantics: the polyline's free pieces may reconnect through its own self-intersections, so they are joined geometrically rather than in traversal order (see detail::separates1DSet).

separates() [11/17]

template<class PointType, class LabelType>

template<RayConcept OtherRay>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherRay & other ) const

constexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

Like the segment overload, but a ray has a single finite end (its source); its far end runs to infinity, always outside the bounded polygon, so only the source can lie inside.

Complexity: O(n) for n vertices.

separates() [12/17]

template<class PointType, class LabelType>

template<RectangleConcept OtherRectangle>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherRectangle & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [13/17]

template<class PointType, class LabelType>

template<PolygonWithHolesConcept OtherRegion>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherRegion & other ) const

nodiscard

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

The region is settled by the cell engine of implementation/separates.hpp; see the notes on pgl::PolygonWithHoles::separates for what a region admits that a simply connected target does not.

separates() [14/17]

template<class PointType, class LabelType>

template<HalfplaneIntersectionConcept OtherRegion>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherRegion & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

separates() [15/17]

template<class PointType, class LabelType>

template<SegmentConcept OtherSegment>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherSegment & other ) const

constexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

True iff some boundary edge cuts transversally through the segment's interior while the segment does not lie on the boundary, so the polygon's body interrupts the segment.

Complexity: O(n) for n vertices.

separates() [16/17]

template<class PointType, class LabelType>

template<PolygonSetConcept OtherSet>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherSet & other ) const

nodiscard

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

A set of regions is the one target that may already be in several pieces before anything is removed, so this neither folds over its components nor answers false for a remover that misses it. See implementation/separates.hpp.

separates() [17/17]

template<class PointType, class LabelType>

template<TriangleConcept OtherTriangle>

bool pgl::Polygon< PointType, LabelType >::separates ( const OtherTriangle & other ) const

nodiscardconstexpr

Tests whether removing this shape disconnects the other shape (B∖A is disconnected).

size()

template<class PointType_, class TLabel>

std::size_t pgl::Polygon< PointType_, TLabel >::size ( ) const

inlineconstexpr

Returns the number of vertices in the polygon.

squaredDistance() [1/15]

template<class PointType_, class TLabel>

template<class ResultNumber, class DiskPointType, class DiskLabel>

detail::floating_result_t< ResultNumber > pgl::Polygon< PointType_, TLabel >::squaredDistance ( const Disk< DiskPointType, DiskLabel > & disk ) const

nodiscard

Returns the squared Euclidean distance to a disk.

Zero when the polygon's closed region intersects the disk; otherwise the squared exterior gap. Reports in detail::floating_result_t<ResultNumber>: the gap to a circle is generally irrational, so a floating-point ResultNumber is honoured as asked and any other request falls back to double.

squaredDistance() [2/15]

template<class PointType_, class TLabel>

template<class ResultNumber, MonotoneChainConcept OtherChain>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherChain & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [3/15]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherConvex & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [4/15]

template<class PointType_, class TLabel>

template<class ResultNumber, HalfplaneConcept OtherHalfplane>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherHalfplane & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [5/15]

template<class PointType_, class TLabel>

template<class ResultNumber, LineConcept OtherLine>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherLine & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [6/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedLineConcept OtherOrientedLine>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherOrientedLine & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [7/15]

template<class PointType_, class TLabel>

template<class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherOrientedSegment & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [8/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherPoint & point ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [9/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [10/15]

template<class PointType_, class TLabel>

template<class ResultNumber, PolylineConcept OtherPolyline>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherPolyline & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [11/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RayConcept OtherRay>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherRay & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [12/15]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherRectangle & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [13/15]

template<class PointType_, class TLabel>

template<class ResultNumber, SegmentConcept OtherSegment>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherSegment & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

squaredDistance() [14/15]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, typename OtherShape>
requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polygon>) && requires(const OtherShape& o, const Polygon& self)
{ o.template squaredDistance<ResultNumber>(self); })

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherShape & other ) const

inlinenodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Forwards to the other shape's implementation so that each unordered pair needs squaredDistance defined only once, on the higher-ranked shape.

squaredDistance() [15/15]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

auto pgl::Polygon< PointType_, TLabel >::squaredDistance ( const OtherTriangle & other ) const

nodiscardconstexpr

Returns the squared Euclidean distance to the given shape.

Zero when the polygon's closed region intersects the other shape; otherwise the smallest squared distance between the two shapes. When they are disjoint the polygon's closest point lies on its boundary, so the result is the minimum over the boundary edges of the edge-to-shape squared distance.

Complexity: O(n) edge queries for n vertices, each against the other shape.

Template Parameters

ResultNumber

Coordinate type of the returned distance (default: division_result_t).

Warning

With an integer ResultNumber the exact squared distance is generally a fraction, so the internal division truncates and the result is inexact. Request a floating-point or pgl::Rational result type, e.g. squaredDistance<double>(point), for an accurate value.

symmetricDifference() [1/12]

template<class PointType_, class TLabel>

template<class ResultNumber, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference

(

const OtherConvex &

other

)

const

symmetricDifference() [2/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherConvex & other ) const

nodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

symmetricDifference() [3/12]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference

(

const OtherPolygon< PointType_, TLabel > &

other

)

const

symmetricDifference() [4/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherPolygon< PointType_, TLabel > & other ) const

nodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

The result is closure((A° ∖ B) ∪ (B° ∖ A)), as a set of regions with pairwise disjoint interiors: the part covered by exactly one of the two operands. It is the union of the two differences, and inherits holes from both.

Complexity: O(m²) for m boundary edges, then a constrained triangulation over the arrangement of both boundaries.

Template Parameters

ResultNumber

The number type for the result.

Parameters

other

The other shape.

Returns

The pieces of the symmetric difference, in canonical order.

Note

The arrangement is built over exact rationals whatever ResultNumber is, and converted only at the end.

symmetricDifference() [5/12]

template<class PointType_, class TLabel>

template<class ResultNumber, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference

(

const OtherRectangle &

other

)

const

symmetricDifference() [6/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherRectangle & other ) const

nodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

symmetricDifference() [7/12]

template<class PointType_, class TLabel>

template<class ResultNumber, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference

(

const OtherRegion &

other

)

const

symmetricDifference() [8/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherRegion & other ) const

nodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

symmetricDifference() [9/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>

auto pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherSet & other ) const

inlinenodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

A set of regions is the one PolygonalRegionConcept operand ranked above a polygon, and it states its operations over every operand at once, so this hands the pair back to it rather than restating it, exactly as regularizedUnion(const OtherSet&) const does. See symmetricDifference(const OtherPolygon&) const for the contract.

symmetricDifference() [10/12]

template<class PointType_, class TLabel>

template<class ResultNumber, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference

(

const OtherTriangle &

other

)

const

symmetricDifference() [11/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>

PolygonSet< Point< ResultNumber, typename PointType::LabelType > > pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const OtherTriangle & other ) const

nodiscard

Returns the regularized symmetric difference of the two shapes (A △ B).

symmetricDifference() [12/12]

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>

auto pgl::Polygon< PointType_, TLabel >::symmetricDifference ( const Shape< OtherPoint > & other ) const

inlinenodiscard

Returns the regularized symmetric difference of the two shapes (A △ B), re-dispatching through the wrapper's own symmetricDifference.

A symmetric difference is symmetric, so this just calls other's own, which visits its wrapped alternative and throws if the pair is unsupported. See symmetricDifference(const OtherPolygon&) const for the contract.

The point type is deduced from other so a plain concrete shape cannot reach this overload through an implicit conversion to Shape.

triangulation() [1/3]

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::triangulation

(

)

const

Builds the constrained Delaunay triangulation of this polygon.

Equivalent to Triangulation(*this). The polygon must be simple (non-self-intersecting) and non-degenerate.

Returns

A Triangulation whose in-domain triangles cover the polygon.

triangulation() [2/3]

template<class PointType_, class TLabel>

template<class PointRange, class SegmentRange>

auto pgl::Polygon< PointType_, TLabel >::triangulation	(	const PointRange &	points,
		const SegmentRange &	segments ) const

Builds the constrained Delaunay triangulation of this polygon with the given interior vertices and constraint segments.

Equivalent to Triangulation(*this, points, segments). The polygon must be simple (non-self-intersecting) and non-degenerate, and the points and segments are assumed to lie inside it (not checked).

Returns

A Triangulation whose in-domain triangles cover the polygon, with every point present as a vertex and every segment as a constrained edge.

triangulation() [3/3]

template<class PointType_, class TLabel>

template<class SegmentRange>

auto pgl::Polygon< PointType_, TLabel >::triangulation

(

const SegmentRange &

segments

)

const

Builds the constrained Delaunay triangulation of this polygon with the given interior constraint segments.

Equivalent to Triangulation(*this, segments). The polygon must be simple (non-self-intersecting) and non-degenerate, and the segments are assumed to lie inside it (not checked).

Returns

A Triangulation whose in-domain triangles cover the polygon, with every segment present as a constrained edge.

twiceArea()

template<class PointType_, class TLabel>

template<class ResultNumber = NumberType>

ResultNumber pgl::Polygon< PointType_, TLabel >::twiceArea ( ) const

inlineconstexpr

Computes twice the (unsigned) area of the polygon via the shoelace formula.

Template Parameters

ResultNumber

Type the sum is accumulated in, NumberType by default. The shoelace terms are products of coordinates, so a polygon whose area leaves the coordinate range wraps; pass a wider type to measure such a polygon.

Returns

Twice the area, or zero for fewer than three vertices.

untangle()

template<class PointType, class LabelType>

void pgl::Polygon< PointType, LabelType >::untangle ( )

constexpr

Makes the polygon simple in place by uncrossing its boundary.

Repeatedly removes self-intersections until the boundary is a simple closed curve. At runtime, every round indexes the current boundary edges in an interval tree, greedily selects an edge-disjoint batch of crossing pairs, applies all of their flips, and rebuilds the tree for the changed boundary. Two kinds of moves are applied:

• Flip (2-opt): when two non-adjacent edges cross transversally, the sub-path between them is reversed, turning the crossing pair (v_i,v_{i+1}),(v_j,v_{j+1}) into the uncrossed (v_i,v_j),(v_{i+1},v_{j+1}). By the triangle inequality each flip strictly shortens the perimeter, so no vertex-set polygonalization can repeat.
• Vertex removal: a transversal flip is impossible when the offending edges only touch or overlap collinearly (a vertex lying on a non-incident edge, coincident vertices, or a zero-length edge). One such vertex is redundant for simplicity and is deleted, which also strictly decreases the vertex count.

Because every move either shortens the perimeter at a fixed vertex count or drops a vertex, the process terminates, and on return the polygon is simple (isSimple). The surviving vertices are a subset of the originals with their positions unchanged, then renormalized to canonical form. A polygon with fewer than three vertices is left untouched.

Warning

Relies on exact orientation predicates; use an exact coordinate type. Termination is not guaranteed for floating-point coordinates.

Runtime candidate searches are output-sensitive after an O(n log n) tree build per batch. A batch can still take O(n^2) when many projected intervals overlap or many vector sub-paths are reversed, and the number of batches has no polynomial bound in n. Constant evaluation uses an O(n^2) pairwise scan for each move instead of the runtime index.

vertices()

template<class PointType_, class TLabel>

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

inlineconstexpr

Returns the vertices of the polygon (translation applied).

verticesCentroid()

template<class PointType_, class TLabel>

template<class ResultNumber = division_result_t<NumberType>>

Point< ResultNumber > pgl::Polygon< PointType_, TLabel >::verticesCentroid ( ) const

inlineconstexpr

Computes the centroid of the vertex set (the average of the vertices).

Template Parameters

ResultNumber

The number type for the result.

Warning

Uses division by the number of vertices, so the result may be inexact even for floating-point types.

verticesView()

template<class PointType_, class TLabel>

auto pgl::Polygon< PointType_, TLabel >::verticesView ( ) const

inlineconstexpr

Returns a lazy view over the vertices, translating each on the fly instead of allocating a vector.

Same vertex sequence as vertices(), with no heap allocation. The polygon is itself a vertex range, so this is just begin() and end() packaged as a view for callers that take one.

visibilityGraph()

template<class PointType, class LabelType>

Graph< PointType > pgl::Polygon< PointType, LabelType >::visibilityGraph ( ) const

nodiscard

Returns the visibility graph of the polygon vertices.

Two vertices are adjacent exactly when the closed segment joining them is contained in the closed polygon. Consequently boundary edges, and diagonals that touch or overlap the boundary without leaving the polygon, are visible.

The answer is meaningful for a simple polygon. Degenerate polygons are handled as their represented point set: an empty polygon gives an empty graph, while a polygon collapsed to a point or segment connects every pair of distinct contained vertices.

Triangulates the polygon and runs one cone-clipped traversal of the mesh per vertex — triangular expansion — whose cost is proportional to the part of the polygon that vertex actually sees. A convex polygon skips the triangulation: every segment between its vertices is inside it, so the answer is the complete graph. See Triangulation::visibilityGraph.

Complexity: O(n·t + m) time for n vertices, m visibility edges and t triangles seen per vertex, plus O(m) space for the returned graph.

Returns

An undirected graph whose vertices are this polygon's vertices.

visibleVertices()

template<class PointType, class LabelType>

std::vector< PointType > pgl::Polygon< PointType, LabelType >::visibleVertices ( const PointType & query ) const

nodiscard

The polygon 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 is contained in the closed polygon, grazing included. This is what joins a query point to reducedVisibilityGraph, which by itself holds only the edges a shortest path can bend along.

The answer is meaningful for a simple polygon.

Parameters

query

Point to look from; outside the polygon nothing is visible.

Returns

The visible vertices, counterclockwise around query starting from the lexicographically smallest, as sortAround orders them. Empty when query lies outside the polygon.