 |
Pangolin
Header-only C++20 plane computational geometry library
|
|
Pangolin
Header-only C++20 plane computational geometry library
|
Set of closed regions with pairwise disjoint interiors. More...
#include <polygonset.hpp>
Classes | |
| class | VertexIterator |
| Forward iterator flattening every component's rings into one vertex sequence, components in canonical order. More... | |
Public Types | |
| using | PointType = PointType_ |
| using | NumberType = typename PointType::NumberType |
| using | LabelType = TLabel |
| using | ComponentType = PolygonWithHoles<PointType> |
| using | PolygonType = Polygon<PointType> |
| using | EdgeType = Segment<PointType> |
Public Member Functions | |
| constexpr | PolygonSet ()=default |
| Creates the empty set (no components). | |
| constexpr | PolygonSet (ComponentType component) |
| Creates a set with a single component. | |
| template<std::ranges::input_range ComponentRange> requires detail::is_polygon_with_holes_v<std::ranges::range_value_t<ComponentRange>> | |
| constexpr | PolygonSet (ComponentRange &&components, bool trusted=false) |
| Creates a set from a range of components. | |
| template<PointConcept OtherPointType, class OtherLabelType> requires (std::constructible_from<PointType, const OtherPointType&>) | |
| constexpr | PolygonSet (const PolygonSet< OtherPointType, OtherLabelType > &other) |
| Converts a set with compatible vertex type. | |
| template<class A = LabelType> requires (detail::has_label_v<A>) | |
| constexpr A & | label () const |
| Returns the set label. | |
| constexpr std::size_t | componentCount () const |
| Returns the number of components. | |
| constexpr const ComponentType & | component (std::size_t index) const |
| Accesses a component by index. | |
| constexpr const std::vector< ComponentType > & | components () const |
| Returns the components in canonical order. | |
| constexpr auto | begin () const |
| Returns a constant iterator to the first component. | |
| constexpr auto | cbegin () const |
| Returns a constant iterator to the first component. | |
| constexpr auto | end () const |
| Returns a constant iterator past the last component. | |
| constexpr auto | cend () const |
| Returns a constant iterator past the last component. | |
| constexpr void | addComponent (ComponentType component) |
| Adds a component, keeping the canonical order. | |
| constexpr void | eraseComponent (std::size_t index) |
| Erases the component at the given index. | |
| constexpr bool | eraseComponent (const ComponentType &component) |
| Erases the component equal to the given region, if the set has one. | |
| constexpr std::size_t | holeCount () const |
| Returns the total number of holes over all components. | |
| constexpr bool | hasHoles () const |
| Tests whether any component has a hole. | |
| constexpr std::size_t | vertexCount () const |
| Returns the total number of vertices over every ring of every component. | |
| constexpr std::vector< PointType > | vertices () const |
| Returns the vertices of every ring of every component. | |
| constexpr auto | verticesView () const |
| Returns a lazy view over the vertices of every ring of every component, without allocating a vector. | |
| constexpr VertexIterator | verticesBegin () const |
| Returns an iterator to the first vertex of the first component. | |
| constexpr VertexIterator | verticesEnd () const |
| Returns an iterator past the last vertex of the last component. | |
| constexpr std::vector< EdgeType > | edges () const |
| Returns the boundary edges of every ring of every component. | |
| constexpr std::vector< OrientedSegment< PointType > > | orientedEdges () const |
| Returns the boundary edges directed so the set lies to the left. | |
| constexpr auto | operator<=> (const PolygonSet &other) const |
| Compares two sets by component count, then lexicographically. | |
| constexpr bool | operator== (const PolygonSet &other) const |
| Checks equality of two sets. | |
| template<AnyShapeConcept OtherShape> | |
| constexpr bool | samePointSet (const OtherShape &other) const |
| Tests whether another shape defines exactly the same point set. | |
| constexpr bool | empty () const |
| Tests whether the set has no components at all. | |
| constexpr bool | isDegenerate () const |
| Tests whether the set has zero area. | |
| constexpr bool | isPoint () const |
| Tests whether the set covers exactly one point. | |
| constexpr bool | isSegment () const |
| Tests whether the set covers exactly one segment of positive length. | |
| constexpr bool | isUndefined () const |
| Tests whether the set is degenerate without covering a point or a segment (which includes the empty set). | |
| template<class Rational = pgl::Rational<pgl::BigInt>> | |
| bool | isSimple () const |
| Tests whether every ring of every component is simple. | |
| template<class Rational = pgl::Rational<pgl::BigInt>> | |
| bool | isValid () const |
| Tests the structural contract: every component valid, component interiors pairwise disjoint, no two components sharing a stretch of edge. | |
| bool | isRegular () const |
| Tests whether the set is the closure of its own interior (A = closure(A°)). | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | regularized () const |
| Returns the set without its slits (closure(A°)). | |
| template<class ResultNumber = NumberType> | |
| constexpr ResultNumber | twiceArea () const |
| Computes twice the area of the set. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| constexpr auto | area () const |
| Computes the area of the set. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| constexpr Point< ResultNumber > | centroid () const |
| Computes the area-weighted centroid of the set. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| constexpr Point< ResultNumber > | verticesCentroid () const |
| Computes the centroid of the vertex set over every ring of every component. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| Point< ResultNumber > | pointInside () const |
| Returns a point strictly inside the set. | |
| 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 set's vertices. | |
| constexpr const Rectangle< PointType > & | bbox () const |
| Computes the bounding box of the set. | |
| 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 set contains. | |
| template<std::floating_point ResultNumber = double> | |
| constexpr Rectangle< Point< ResultNumber > > | fbox () const |
| Computes the floating-point bounding box of the set. | |
| auto | triangulation () const |
| Builds the constrained Delaunay triangulation of this set. | |
| template<class SegmentRange> | |
| auto | triangulation (const SegmentRange &segments) const |
| Builds the constrained Delaunay triangulation of this set with the given interior constraint segments. | |
| std::vector< Convex< PointType > > | convexPartition () const |
| Cuts this set into convex pieces with disjoint interiors. | |
| std::vector< Convex< PointType > > | convexCovering () const |
| Covers this set with a greedily selected set of convex polygons. | |
| template<class ResultNumber = grid_number_t<typename PointType_::NumberType>> requires (std::signed_integral<ResultNumber>) | |
| auto | asBitMatrix () const |
| Rasterizes this set into a BitMatrix, one bit per covered cell. | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | difference (const OtherShape &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>, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | regularizedUnion (const OtherShape &other) const |
| Returns the regularized union of the two shapes (A ∪ B). | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | regularizedIntersection (const OtherShape &other) const |
| Returns the regularized intersection of the two shapes (A ∩ B). | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | symmetricDifference (const OtherShape &other) const |
| Returns the regularized symmetric difference of the two shapes (A △ B). | |
| template<class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | regularizedIntersection (const OtherIntersection &other) const |
| Returns the regularized intersection of the two shapes (A ∩ B). | |
| template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | regularizedIntersection (const OtherHalfplane &other) const |
| Returns the regularized intersection of the two shapes (A ∩ B). | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetBooleanOperandConcept OtherShape> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > > > | 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>, HalfplaneIntersectionConcept OtherIntersection> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherIntersection &other) const |
| Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint. | |
| template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Polyline< Point< ResultNumber, typename PointType::LabelType > >, PolygonWithHoles< 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 = 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<detail::SetOperandConcept OtherShape> | |
| bool | intersects (const OtherShape &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | interiorsIntersect (const OtherShape &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | contains (const OtherShape &other) const |
| Tests whether this shape contains the other shape (A ⊇ B). | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | interiorContains (const OtherShape &other) const |
| Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B). | |
| template<SegmentConcept OtherSegment> | |
| bool | interiorContainsInterior (const OtherSegment &other) const |
| Tests whether this shape's interior contains the segment's interior. | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | boundaryContains (const OtherShape &other) const |
| Tests whether this shape's boundary contains the other shape (∂A ⊇ B). | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | separates (const OtherShape &other) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| template<detail::SetOperandConcept OtherShape> | |
| bool | crosses (const OtherShape &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<PolygonSetConcept OtherSet> | |
| bool | intersects (const OtherSet &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<PolygonSetConcept OtherSet> | |
| bool | interiorsIntersect (const OtherSet &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<PolygonSetConcept OtherSet> | |
| bool | contains (const OtherSet &other) const |
| Tests whether this shape contains the other shape (A ⊇ B). | |
| template<PolygonSetConcept OtherSet> | |
| bool | interiorContains (const OtherSet &other) const |
| Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B). | |
| template<PolygonSetConcept OtherSet> | |
| bool | boundaryContains (const OtherSet &other) const |
| Tests whether this shape's boundary contains the other shape (∂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<PolygonSetConcept OtherSet> | |
| bool | crosses (const OtherSet &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| 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 | interiorContains (const EmptyShape< EmptyPoint > &) const |
| Tests whether this shape's interior contains the other shape (A∖∂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 | 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 shapes intersect (A° ∩ B° ≠ ∅). | |
| template<class EmptyPoint> | |
| constexpr bool | separates (const EmptyShape< EmptyPoint > &) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| template<class EmptyPoint> | |
| constexpr bool | crosses (const EmptyShape< EmptyPoint > &) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<PointConcept OtherPoint> | |
| bool | contains (const Shape< OtherPoint > &other) const |
| Tests whether this shape contains the other shape (A ⊇ B). | |
| template<PointConcept OtherPoint> | |
| bool | interiorContains (const Shape< OtherPoint > &other) const |
| Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B). | |
| template<PointConcept OtherPoint> | |
| bool | boundaryContains (const Shape< OtherPoint > &other) const |
| Tests whether this shape's boundary contains the other shape (∂A ⊇ B). | |
| template<PointConcept OtherPoint> | |
| bool | intersects (const Shape< OtherPoint > &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<PointConcept OtherPoint> | |
| bool | interiorsIntersect (const Shape< OtherPoint > &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<PointConcept OtherPoint> | |
| bool | separates (const Shape< OtherPoint > &other) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| template<PointConcept OtherPoint> | |
| bool | crosses (const Shape< OtherPoint > &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetOperandConcept OtherShape> | |
| auto | squaredDistance (const OtherShape &other) const |
| Computes the squared Euclidean distance to the other shape. | |
| template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet> | |
| auto | squaredDistance (const OtherSet &other) const |
| Computes the squared Euclidean distance to the other shape. | |
| template<class ResultNumber = NumberType, BoundedPolygonalConcept OtherShape> requires detail::ClosestPairConcept<PolygonSet<PointType_, TLabel>, OtherShape> | |
| 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<PolygonSet<PointType_, TLabel>, OtherShape> | |
| 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>, detail::SetOperandConcept OtherShape> requires detail::ComponentDistanceL1Concept<ResultNumber, PolygonWithHoles<PointType_>, OtherShape> | |
| auto | distanceL1 (const OtherShape &other) const |
| Computes the squared Euclidean distance to the other shape. | |
| template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet> | |
| auto | distanceL1 (const OtherSet &other) const |
| Computes the squared Euclidean distance to the other shape. | |
| template<class ResultNumber = division_result_t<NumberType>, detail::SetOperandConcept OtherShape> requires detail::ComponentDistanceLInfConcept<ResultNumber, PolygonWithHoles<PointType_>, OtherShape> | |
| auto | distanceLInf (const OtherShape &other) const |
| Computes the squared Euclidean distance to the other shape. | |
| template<class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet> | |
| auto | distanceLInf (const OtherSet &other) const |
| Computes the squared Euclidean distance to the other 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, using symmetry to re-dispatch through the wrapper's own distanceL1. | |
| template<class ResultNumber = double, PointConcept OtherPoint> | |
| constexpr auto | distanceLInf (const Shape< OtherPoint > &other) const |
| Returns the Chebyshev (L∞) distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceLInf. | |
| bool | isPinched () const |
| Tests whether two components touch each other anywhere. | |
| bool | isConnected () const |
| Tests whether the set is connected as a point set. | |
| template<class OtherShape> requires MinkowskiSummableConcept<PolygonSet<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<PolygonSet<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<PolygonSet<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<class ResultNumber = division_result_t<NumberType>, detail::SetMinkowskiOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherShape &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions. | |
| template<class TranslationNumber, class TranslationLabel> | |
| constexpr PolygonSet & | operator+= (const Point< TranslationNumber, TranslationLabel > &translation) |
| Translates the set in place. | |
| template<class TranslationNumber, class TranslationLabel> | |
| constexpr PolygonSet & | operator-= (const Point< TranslationNumber, TranslationLabel > &translation) |
| Translates the set in place by the opposite vector. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>) | |
| constexpr PolygonSet & | operator*= (const Scalar &scalar) |
| Scales the set in place. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>) | |
| constexpr PolygonSet & | operator/= (const Scalar &scalar) |
| Scales the set in place. | |
| constexpr PolygonSet | rotated90 (int k) const |
| Returns the set rotated by 90k degrees around the origin. | |
| constexpr void | rotate90 (int k) |
| Rotates the set by 90k degrees around the origin in place. | |
| template<class OtherNumber> | |
| constexpr PolygonSet | scaledUpX (const OtherNumber scalar) const |
Returns the set with its x-coordinates multiplied by scalar. | |
| template<class OtherNumber> | |
| constexpr void | scaleUpX (const OtherNumber scalar) |
| Scales the set's x-coordinates up in place. | |
| template<class OtherNumber> | |
| constexpr PolygonSet | scaledUpY (const OtherNumber scalar) const |
Returns the set with its x-coordinates multiplied by scalar. | |
| template<class OtherNumber> | |
| constexpr void | scaleUpY (const OtherNumber scalar) |
| Scales the set's y-coordinates up in place. | |
| template<class OtherNumber> | |
| constexpr PolygonSet | scaledDownX (const OtherNumber scalar) const |
Returns the set with its x-coordinates multiplied by scalar. | |
| template<class OtherNumber> | |
| constexpr void | scaleDownX (const OtherNumber scalar) |
| Scales the set's x-coordinates down in place. | |
| template<class OtherNumber> | |
| constexpr PolygonSet | scaledDownY (const OtherNumber scalar) const |
Returns the set with its x-coordinates multiplied by scalar. | |
| template<class OtherNumber> | |
| constexpr void | scaleDownY (const OtherNumber scalar) |
| Scales the set's y-coordinates down in place. | |
| template<class ResultNumber> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | regularized () 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, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | difference (const OtherShape &other) const |
| template<class ResultNumber, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | regularizedUnion (const OtherShape &other) const |
| template<class ResultNumber, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | regularizedIntersection (const OtherShape &other) const |
| template<class ResultNumber, detail::SetBooleanOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | symmetricDifference (const OtherShape &other) const |
| template<class ResultNumber, HalfplaneIntersectionConcept OtherIntersection> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | regularizedIntersection (const OtherIntersection &other) const |
| template<class ResultNumber, HalfplaneConcept OtherHalfplane> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | regularizedIntersection (const OtherHalfplane &other) const |
| template<class ResultNumber, detail::SetBooleanOperandConcept OtherShape> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > | intersection (const OtherShape &other) const |
| template<class ResultNumber, HalfplaneIntersectionConcept OtherIntersection> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > | intersection (const OtherIntersection &other) const |
| template<class ResultNumber, HalfplaneConcept OtherHalfplane> | |
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > | intersection (const OtherHalfplane &other) const |
| template<class ResultNumber, detail::SetMinkowskiOperandConcept OtherShape> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherShape &other) const |
Friends | |
| template<class OtherPointType, class OtherLabelType> | |
| struct | PolygonSet |
Set of closed regions with pairwise disjoint interiors.
A closed region of the plane given as a set of PolygonWithHoles components with pairwise disjoint interiors.
The point set is exactly
— the union of the components, each of them a closed region in its own right. This is the shape the regularized boolean operations produce: a difference, a union or a symmetric difference of two regions can come apart into several pieces, and an island stranded inside a hole of the answer is a piece like any other. Having it as a shape rather than a std::vector is what makes those operations closed — a result can be fed straight back in, compared, hashed, drawn, transformed and measured.
Storage. The components are ordinary PolygonWithHoles values, each in its own canonical form, kept sorted by PolygonWithHoles::operator<=>. So equality, ordering and hashing do not depend on the order they were supplied in. Components of zero area cover nothing that survives and are dropped, as PolygonWithHoles drops a zero-area hole, and duplicates are erased — two equal components would violate the disjointness precondition anyway.
Components are deliberately not nested: a component stranded inside another's hole is stored beside it, not within it. That is what the cell engine emits and what a flat list can say.
Preconditions. As with Polygon and PolygonWithHoles, structural validity is a documented precondition rather than an enforced invariant:
The third clause is what buys the identity A° = ⋃ Aᵢ°, on which the componentwise predicates rest: two squares glued along an edge would have interior points lying in no component's interior. The cell engine already produces boundaries that satisfy it, so the clause costs nothing.
| PointType_ | The vertex point type. |
| TLabel | Optional label payload. |
| using pgl::PolygonSet< PointType_, TLabel >::ComponentType = PolygonWithHoles<PointType> |
| using pgl::PolygonSet< PointType_, TLabel >::EdgeType = Segment<PointType> |
| using pgl::PolygonSet< PointType_, TLabel >::LabelType = TLabel |
| using pgl::PolygonSet< PointType_, TLabel >::NumberType = typename PointType::NumberType |
| using pgl::PolygonSet< PointType_, TLabel >::PointType = PointType_ |
| using pgl::PolygonSet< PointType_, TLabel >::PolygonType = Polygon<PointType> |
|
constexprdefault |
Creates the empty set (no components).
|
inlineexplicitconstexpr |
Creates a set with a single component.
A component of zero area covers nothing and leaves the set empty.
| component | The only component. |
|
inlineconstexpr |
Creates a set from a range of components.
Components of zero area are dropped, the rest are sorted into canonical order and duplicates are erased.
| ComponentRange | Range whose elements are regions. |
| components | The components; their interiors must be pairwise disjoint and no two may share a stretch of edge (a precondition, see isValid). |
| trusted | When true, adopt components as given without dropping degenerate ones, sorting, or removing duplicates. Only pass true for a range that is already in canonical form — over rational coordinates the area test alone dominates the construction. |
|
inlineconstexpr |
Converts a set with compatible vertex type.
The source components are already canonical and a coordinate-type conversion preserves both their own normalization and their relative order, so no renormalization is needed.
| OtherPointType | Source vertex type. |
| OtherLabelType | Source label type. |
| other | Source set. |
|
inlineconstexpr |
Adds a component, keeping the canonical order.
A zero-area component covers nothing and is ignored, and one equal to a component already present is ignored too.
| component | The component to add; its interior must be disjoint from the existing components' and it must share no stretch of edge with them (a precondition, see isValid). |
|
inlinenodiscardconstexpr |
Computes the area of the set.
|
nodiscard |
Rasterizes this set into a BitMatrix, one bit per covered cell.
Equivalent to BitMatrix(*this): the window is the bounding box of the whole set and the set cells are the ones its components cover, holes left unset. Only a rectilinear set is exactly a set of grid cells, so every edge of every ring must be axis-parallel; use innerRaster or outerRaster to approximate any other set.
A cell is an integer position, so the coordinates must be whole numbers too. An integer set 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 set.
Two components that touch only at a corner stay apart, since the cells do too and BitMatrix::asPolygonSet splits on edge connectivity, so the round trip through the raster recovers a rectilinear set.
| 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). |
| std::logic_error | If an edge of a ring is not axis-parallel, or a coordinate is not a whole number the grid can hold. |
|
nodiscardconstexpr |
Computes the bounding box of the set.
The union of the components' boxes, cached — unlike a region, which delegates to the box its outer ring already caches.
|
inlinenodiscardconstexpr |
Returns a constant iterator to the first component.
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
nodiscard |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
nodiscard |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
∂A = ⋃ ∂Aᵢ, which has no area, so only an operand that has collapsed can lie on it. Like contains, a one-dimensional one may run from one component's boundary onto another's.
|
nodiscard |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Returns a constant iterator to the first component.
|
inlinenodiscardconstexpr |
Returns a constant iterator past the last component.
|
nodiscardconstexpr |
Computes the area-weighted centroid of the set.
The components enter with their own areas as weights. When the total area is zero the set has no area-weighted centroid and the centroid of the vertex set is returned instead, matching Polygon::centroid and PolygonWithHoles::centroid.
| ResultNumber | The number type for the result. |
ResultNumber.
|
nodiscard |
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.
| ResultNumber | Coordinate type of the returned points (default: division_result_t). |
ResultNumber it truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscard |
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.
| ResultNumber | Coordinate type of the returned segments (default: NumberType). |
other's coordinates and labels are re-expressed in this shape's, so a narrower ResultNumber loses them.
|
inlinenodiscardconstexpr |
Accesses a component by index.
| index | The index of the component, in canonical (sorted) order. |
|
inlinenodiscardconstexpr |
Returns the number of components.
|
inlinenodiscardconstexpr |
Returns the components in canonical order.
|
inlinenodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscard |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscard |
Tests whether this shape contains the other shape (A ⊇ B).
Componentwise for every operand but a one-dimensional one, which may run from one component into another through a point where they touch; see the section note above.
Complexity: O(n) over the total vertex count for the componentwise answer, plus one split of the operand against every component boundary when the components touch and no single one contains it.
|
nodiscard |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscard |
Covers this set with a greedily selected set of convex polygons.
Equivalent to triangulation().convexCovering(), with the same precondition (isValid). Every piece is contained in this set and together they cover closure(interior). Unlike convexPartition, piece interiors may overlap. The returned cover is irredundant, not necessarily minimum.
|
inlinenodiscardconstexpr |
Returns the convex hull of the set's vertices.
Every hole lies inside its own component's outer ring, so only the outer rings can contribute a hull vertex.
|
nodiscard |
Cuts this set into convex pieces with disjoint interiors.
Equivalent to triangulation().convexPartition(), with the same precondition (isValid). What the pieces cover is the part of the set that has area — closure(interior) — so the holes and the gaps between components are where there is no piece, and a slit appears in none of them.
|
inlinenodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscard |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscard |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscard |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
inlinenodiscardconstexpr |
Returns a segment realizing the diameter (the farthest vertex pair).
Unlike PolygonWithHoles::diameter, this cannot be delegated to any one component: the farthest pair generally has its two ends in different components. Every hole lies inside its own component's outer ring, though, so only the outer rings can carry the pair, and the diameter is that of their convex hull.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< 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.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< 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 set of regions can hold it. See PolygonWithHoles::difference(const OtherIntersection&) const for the clip that bounds it and for the rest of the contract.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::difference | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the regularized set difference of the two shapes (A ∖ B).
The result is closure(A° ∖ B): the part of this set with area that survives the removal. See Polygon::difference for the full contract.
| ResultNumber | The number type for the result. |
| other | The shape to remove. |
|
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 Polygon::difference 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.
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value.
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value. A set measures whatever its components measure, and no more; see detail::ComponentDistanceL1Concept for the one operand that leaves out.
|
inlinenodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceL1.
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value.
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value. A set measures whatever its components measure, and no more; see detail::ComponentDistanceL1Concept for the one operand that leaves out.
|
inlinenodiscardconstexpr |
Returns the Chebyshev (L∞) distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceLInf.
|
inlinenodiscardconstexpr |
Returns the boundary edges of every ring of every component.
|
inlinenodiscardconstexpr |
Tests whether the set has no components at all.
|
inlinenodiscardconstexpr |
Returns a constant iterator past the last component.
|
inlineconstexpr |
Erases the component equal to the given region, if the set has one.
The components are sorted, so this finds it by binary search: O(log k) comparisons for k components, plus the element moves the erase costs.
| component | The component to erase. |
component.
|
inlineconstexpr |
Erases the component at the given index.
Dropping a component needs no revalidation: the ones that remain still have pairwise disjoint interiors and still share no stretch of edge, and erasing preserves both their sorted order and the absence of zero-area components, so nothing is renormalized.
| index | The index of the component, in canonical (sorted) order. |
|
nodiscardconstexpr |
Computes the floating-point bounding box of the set.
|
inlinenodiscardconstexpr |
Tests whether any component has a hole.
|
inlinenodiscardconstexpr |
Returns the total number of holes over all components.
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscard |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscard |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
The component interiors are open and pairwise disjoint, so a connected operand inside the set's interior is inside one component's — exact componentwise for every operand.
|
nodiscard |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscard |
Tests whether this shape's interior contains the segment's interior.
Every point of the open segment must lie strictly inside one component; either endpoint may lie on the set boundary. A degenerate segment is accepted exactly when its sole point is contained.
|
inlinenodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscard |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscard |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
A° = ⋃ Aᵢ° for a valid set, so this too is exact componentwise.
|
nodiscard |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
inlinenodiscardconstexpr |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > pgl::PolygonSet< PointType_, TLabel >::intersection | ( | const OtherHalfplane & | other | ) | const |
|
nodiscard |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
A half-plane and a half-plane intersection may be unbounded, but this set is not, so the operand is first clipped to a box strictly containing the bounding rectangle — which leaves A ∩ B untouched and makes it a convex polygon. Unlike regularizedIntersection(const OtherIntersection&) const, a clip with empty interior is not the end of it: the set can still meet the carrier it collapsed to in points and segments.
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > pgl::PolygonSet< PointType_, TLabel >::intersection | ( | const OtherIntersection & | other | ) | const |
|
nodiscard |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
A half-plane and a half-plane intersection may be unbounded, but this set is not, so the operand is first clipped to a box strictly containing the bounding rectangle — which leaves A ∩ B untouched and makes it a convex polygon. Unlike regularizedIntersection(const OtherIntersection&) const, a clip with empty interior is not the end of it: the set can still meet the carrier it collapsed to in points and segments.
| std::vector< std::variant< Point< ResultNumber, typename PointType_::LabelType >, Polyline< Point< ResultNumber, typename PointType_::LabelType > >, PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > > > pgl::PolygonSet< PointType_, TLabel >::intersection | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
The literal point set A ∩ B, as its connected pieces — the regions regularizedIntersection(const OtherShape&) const returns plus the lower-dimensional material it drops. See PolygonWithHoles::intersection(const OtherPolygon&) const for the full contract; a set reaches the same engine as any other operand, and goes in whole rather than one component at a time.
| ResultNumber | The number type for the result. |
| other | The shape to intersect with. |
|
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.
other holds is not known until run time, so neither is the result's.
|
inlinenodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscard |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscard |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
The set is the union of its components, so it meets a shape exactly when one of them does — exact for every operand.
|
nodiscard |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscard |
Tests whether the set is connected as a point set.
A set of regions is the library's first shape that need not be: two components that never touch are two pieces. Each component is connected on its own (PolygonWithHoles is, however its rings meet), so the set is connected exactly when the graph joining components that intersect is — and the empty set is connected by convention, having nothing to come apart.
This is what the cut predicates ask before dismissing a remover that misses the set: B ∖ A is disconnected whenever B already was.
Complexity: one PolygonWithHoles::intersects per component pair whose bounding boxes meet.
|
inlinenodiscardconstexpr |
Tests whether the set has zero area.
A canonical set drops its zero-area components, so this is exactly empty for one; a set adopted with trusted may still carry a component without area, which is why the areas are summed rather than the components counted. The sum is taken in the promoted type: narrowed to NumberType it wraps to zero for a set larger than the coordinate range and reports an ordinary set as degenerate.
|
nodiscard |
Tests whether two components touch each other anywhere.
false is the cheap exact case: components that stay apart make the set a disjoint union of closed sets at positive distance, and then every relation folds componentwise exactly, one-dimensional operands included. Memoized, since the whole point of it is to be asked before the general machinery is.
Complexity: one bounding-box test per component pair, plus one PolygonWithHoles::intersects per pair whose boxes meet.
|
inlinenodiscardconstexpr |
Tests whether the set covers exactly one point.
Only a single component can, and only a trusted construction can leave one that does.
|
inlinenodiscard |
Tests whether the set is the closure of its own interior (A = closure(A°)).
A valid set is ⋃ Aᵢ with the components meeting at finitely many points at most, so the only material with no area beside it is a component's own slit — see PolygonWithHoles::isRegular. The set is therefore regular exactly when every component is.
The empty set is regular (∅ = closure(∅°)).
The set must satisfy isValid.
Complexity: O(n²) over the total vertex count.
|
inlinenodiscardconstexpr |
Tests whether the set covers exactly one segment of positive length.
|
inlinenodiscard |
Tests whether every ring of every component is simple.
This is a per-ring check only; it says nothing about how the rings or the components sit relative to one another. Use isValid for the structural contract.
Complexity: O(n log n) over the total vertex count.
|
inlinenodiscardconstexpr |
Tests whether the set is degenerate without covering a point or a segment (which includes the empty set).
|
nodiscard |
Tests the structural contract: every component valid, component interiors pairwise disjoint, no two components sharing a stretch of edge.
The third clause is what the componentwise predicates rest on: it is what makes A° = ⋃ Aᵢ°, and hence what lets a question about the set be answered one component at a time. Two components glued along an edge have interior points that lie in no component's interior, and the identity fails.
This is a precondition of every other operation, checked on demand rather than enforced by the constructor — mirroring Polygon and PolygonWithHoles, which likewise leave their contracts to the caller.
Complexity: the components' own PolygonWithHoles::isValid, plus one interior-overlap test and one edge-overlap scan per pair of components whose bounding boxes meet.
|
inlineconstexpr |
Returns the set label.
The label is mutable even through a const set: it is metadata that does not participate in equality, hashing, or geometric predicates.
|
nodiscard |
Returns the integer points the set 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. A point shared by two components, which can only be a boundary point of both, is reported once.
| 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. |
| 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. |
|
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.
| ResultNumber | Coordinate type of the result. |
| OtherShape | Type of the shape to erode by. |
| other | Shape to erode by. |
| std::logic_error | when other covers no point: that erosion is the whole plane, which no set of bounded regions represents. |
|
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 set eroded by a bounded operand is again a set.
Eroding by a shape that covers no point is the whole plane, which a HalfplaneIntersection returns and the tighter result types cannot.
| OtherShape | Type of the shape to erode by. |
| other | Shape to erode by. |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::minkowskiSum | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions.
The sum distributes over a union, and a set is a union:
(⋃ᵢ Aᵢ) ⊕ B = ⋃ᵢ (Aᵢ ⊕ B),
so this sums each component against the operand — against each of its components too, when the operand is a set — and unites the results in a single arrangement rather than one per step. Each component sum is the region-valued construction of implementation/minkowskisum.hpp; see Polygon::minkowskiSum for what it does and what it costs.
This is the one receiver with no precondition to observe, and the one whose answer needs a set however nondegenerate its operands are: the components of a set are disjoint, and an operand small relative to the gaps between them leaves them disjoint. What a body-shaped operand does buy is that each component's sum is a single region — components merge or stay apart, but none of them shatters.
Complexity: the per-component sums, then one arrangement over all the regions they leave.
| ResultNumber | The number type for the result. |
| other | The shape to sum with. |
ResultNumber once, when the union is assembled.
|
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 gives back a set over the promoted coordinate type — this is the reading set + point has always had. A set of regions is not convex, so MinkowskiSummableConcept admits nothing else here; a Halfplane operand, which absorbs the set and gives a half-plane, is the one exception it does admit.
| OtherShape | Type of the other shape. |
| other | Shape to sum with. |
|
inlineconstexpr |
Scales the set in place.
A negative factor reflects the components, which can change their relative order, and a zero one collapses every one of them, so the result is re-canonicalized.
|
inlineconstexpr |
Translates the set in place.
|
inlineconstexpr |
Translates the set in place by the opposite vector.
|
inlineconstexpr |
Scales the set in place.
A negative factor reflects the components, which can change their relative order, and a zero one collapses every one of them, so the result is re-canonicalized.
|
inlinenodiscardconstexpr |
Compares two sets by component count, then lexicographically.
|
inlinenodiscardconstexpr |
Checks equality of two sets.
|
inlinenodiscardconstexpr |
Returns the boundary edges directed so the set lies to the left.
Each component contributes its own PolygonWithHoles::orientedEdges: outer rings counterclockwise, hole rings reversed.
|
nodiscard |
Returns a point strictly inside the set.
Any component's interior is in the set's, so this is the first component's own PolygonWithHoles::pointInside.
| ResultNumber | The number type for the result. |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::regularized | ( | ) | const |
|
nodiscard |
Returns the set without its slits (closure(A°)).
This is PolygonWithHoles::regularized applied to every component and the pieces gathered back into a set — which is exactly where a set of regions starts paying for itself: the result has the type it was called on, so regularization is idempotent in the type system and not only in the mathematics. Dropping a component's slits can break it into several components, and a component without area comes back as nothing at all.
The set must satisfy isValid.
| ResultNumber | The number type for the result. |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::regularizedIntersection | ( | const OtherHalfplane & | other | ) | const |
|
nodiscard |
Returns the regularized intersection of the two shapes (A ∩ B).
A half-plane and a half-plane intersection may be unbounded, but this set is not, so the operand is first clipped to a box strictly containing the bounding rectangle — which leaves A ∩ B untouched and makes it a convex polygon. One with empty interior contributes nothing to a regularized result.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::regularizedIntersection | ( | const OtherIntersection & | other | ) | const |
|
nodiscard |
Returns the regularized intersection of the two shapes (A ∩ B).
A half-plane and a half-plane intersection may be unbounded, but this set is not, so the operand is first clipped to a box strictly containing the bounding rectangle — which leaves A ∩ B untouched and makes it a convex polygon. One with empty interior contributes nothing to a regularized result.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::regularizedIntersection | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the regularized intersection of the two shapes (A ∩ B).
The result is closure(A° ∩ B°): the part both operands cover, with lower-dimensional leftovers dropped. Like PolygonWithHoles::regularizedIntersection(const OtherPolygon&) const, this keeps the holes of a holed operand, and it can split one component into several.
|
inlinenodiscard |
Re-dispatches a regularized intersection through a runtime shape.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::regularizedUnion | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the regularized union of the two shapes (A ∪ B).
The result is closure(A° ∪ B°). A union can close a new hole into being where the operands wrap round between them, and can join two components that were apart into one. See Polygon::regularizedUnion for the full contract.
|
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.
|
inlineconstexpr |
Rotates the set by 90k degrees around the origin in place.
|
inlinenodiscardconstexpr |
Returns the set rotated by 90k degrees around the origin.
|
nodiscardconstexpr |
Tests whether another shape defines exactly the same point set.
|
inlinenodiscardconstexpr |
Returns the set with its x-coordinates multiplied by scalar.
A negative factor reflects the components, which can change their relative order, and a zero one collapses them onto the y-axis; either way the result is re-canonicalized exactly as operator*= does.
|
inlinenodiscardconstexpr |
Returns the set with its x-coordinates multiplied by scalar.
A negative factor reflects the components, which can change their relative order, and a zero one collapses them onto the y-axis; either way the result is re-canonicalized exactly as operator*= does.
|
inlineconstexpr |
Scales the set's x-coordinates down in place.
|
inlineconstexpr |
Scales the set's y-coordinates down in place.
|
inlinenodiscardconstexpr |
Returns the set with its x-coordinates multiplied by scalar.
A negative factor reflects the components, which can change their relative order, and a zero one collapses them onto the y-axis; either way the result is re-canonicalized exactly as operator*= does.
|
inlinenodiscardconstexpr |
Returns the set with its x-coordinates multiplied by scalar.
A negative factor reflects the components, which can change their relative order, and a zero one collapses them onto the y-axis; either way the result is re-canonicalized exactly as operator*= does.
|
inlineconstexpr |
Scales the set's x-coordinates up in place.
|
inlineconstexpr |
Scales the set's y-coordinates up in place.
|
inlinenodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscard |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscard |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
Not componentwise in either direction: removing one component may leave the operand in one piece while removing them all cuts it. This goes to the cell engine of implementation/separates.hpp, which assumes nothing about either operand, with the unbounded ones clipped to a box holding the set first.
|
nodiscard |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value.
|
nodiscard |
Computes the squared Euclidean distance to the other shape.
Zero when the shapes intersect; otherwise the smallest squared distance between them, which is the smallest over the components. An empty set is infinitely far from everything and reports zero, having no component to measure from.
| ResultNumber | Coordinate type of the returned distance (default: division_result_t). |
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 for an accurate value. | PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::PolygonSet< PointType_, TLabel >::symmetricDifference | ( | const OtherShape & | other | ) | const |
|
nodiscard |
Returns the regularized symmetric difference of the two shapes (A △ B).
The result is closure((A° ∖ B) ∪ (B° ∖ A)): the part covered by exactly one of the two operands.
|
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 Polygon::symmetricDifference 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.
| auto pgl::PolygonSet< PointType_, TLabel >::triangulation | ( | ) | const |
Builds the constrained Delaunay triangulation of this set.
Equivalent to Triangulation(*this). Every ring of every component becomes constrained edges; the hole interiors and the gaps between components are left out of the domain, so the in-domain triangles cover exactly the part of the set that has area. The set must satisfy isValid.
| auto pgl::PolygonSet< PointType_, TLabel >::triangulation | ( | const SegmentRange & | segments | ) | const |
Builds the constrained Delaunay triangulation of this set with the given interior constraint segments.
Equivalent to Triangulation(*this, segments).
| SegmentRange | Range whose elements are segments. |
| segments | Constraint edges, assumed to lie in the set. |
|
inlinenodiscardconstexpr |
Computes twice the area of the set.
Σ 2·area(Aᵢ), exact in NumberType with no division. The components have pairwise disjoint interiors, so the sum is the area of their union.
| ResultNumber | Type the components are measured and summed in, NumberType by default. Twice an area is a sum of coordinate products, so a set larger than the coordinate range wraps; pass a wider type to measure such a set. |
|
inlinenodiscardconstexpr |
Returns the total number of vertices over every ring of every component.
Same name and same meaning as PolygonWithHoles::vertexCount, and deliberately not size() for the same reason.
|
inlinenodiscardconstexpr |
Returns the vertices of every ring of every component.
|
inlinenodiscardconstexpr |
Returns an iterator to the first vertex of the first component.
|
nodiscardconstexpr |
Computes the centroid of the vertex set over every ring of every component.
|
inlinenodiscardconstexpr |
Returns an iterator past the last vertex of the last component.
|
inlinenodiscardconstexpr |
Returns a lazy view over the vertices of every ring of every component, without allocating a vector.
Same vertex sequence as vertices(), which materializes one vector per component before copying into its result; this allocates nothing. Unlike begin(), which walks the components, this walks points.
|
friend |
1.17.0