 |
Pangolin
Header-only C++20 plane computational geometry library
|
|
Pangolin
Header-only C++20 plane computational geometry library
|
Weakly x-monotone polyline stored by lexicographically sorted vertices. More...
#include <monotonechain.hpp>
Classes | |
| class | BoundaryIterator |
| Forward iterator over the (optionally oriented) chain edges. More... | |
Public Types | |
| using | PointType = PointType_ |
| using | NumberType = PointType::NumberType |
| using | LabelType = TLabel |
| using | StorageType = Storage |
| using | OwningChain = MonotoneChain<PointType_, TLabel, std::vector<PointType_>> |
| 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 | MonotoneChain ()=default |
| Creates a chain 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> && detail::ownsChainStorage<Storage, PointType> | |
| constexpr | MonotoneChain (Range &&points, bool trusted=false) |
| Creates a chain from a range of points. | |
| template<std::ranges::contiguous_range Range> requires (!detail::ownsChainStorage<Storage, PointType>) && std::constructible_from<Storage, Range&&> | |
| constexpr | MonotoneChain (Range &&points, bool=true) |
| Creates a non-owning chain viewing an external contiguous range of vertices (view instantiations only, e.g. MonotoneChainView). | |
| constexpr | MonotoneChain (std::initializer_list< NumberType > coords, bool trusted=false) |
| Creates a chain from a flat list of coordinates. | |
| template<PointConcept OtherPointType, class OtherLabelType, class OtherStorage> requires (std::constructible_from<PointType, const OtherPointType&> && detail::ownsChainStorage<Storage, PointType>) | |
| constexpr | MonotoneChain (const MonotoneChain< OtherPointType, OtherLabelType, OtherStorage > &other) |
| Converts a chain with compatible vertex type. | |
| template<class A = LabelType> requires (detail::has_label_v<A>) | |
| constexpr A & | label () const |
| Returns the chain label. | |
| constexpr const PointType | operator[] (std::size_t index) const |
| Accesses a vertex by index (in lexicographic order). | |
| constexpr PointType | get (std::ptrdiff_t index) const |
| Accesses a vertex by index modulo the vertex count. | |
| 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. | |
| template<class OtherStorage> | |
| constexpr auto | operator<=> (const MonotoneChain< PointType_, TLabel, OtherStorage > &other) const |
| Compares two chains by their canonical vertex sequences. | |
| template<class OtherStorage> | |
| constexpr bool | operator== (const MonotoneChain< PointType_, TLabel, OtherStorage > &other) const |
| Checks equality of two chains. | |
| 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 chain. | |
| constexpr bool | empty () const |
| Checks whether the chain has no vertex. | |
| constexpr bool | isDegenerate () const |
| Checks if the chain is degenerate (fewer than two vertices, so it has no edge). | |
| constexpr bool | isPoint () const |
| Checks whether the chain covers exactly one point. | |
| constexpr std::optional< PointType > | getIfPoint () const |
| Returns the point the chain collapses to, if it does. | |
| constexpr bool | isSegment () const |
| Checks whether the chain covers exactly one segment of positive length. | |
| constexpr std::optional< BoundaryType< false > > | getIfSegment () const |
| Returns the segment the chain collapses to, if it does. | |
| constexpr bool | isUndefined () const |
| Checks whether the chain is degenerate without covering a point or a segment. | |
| constexpr bool | isStrictlyMonotone () const |
| Tests whether the chain is strictly x-monotone. | |
| 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 chain's vertices. | |
| constexpr const Rectangle< PointType > & | bbox () const |
| Computes the bounding box of the chain. | |
| 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 chain contains. | |
| template<std::floating_point ResultNumber = double> | |
| constexpr Rectangle< Point< ResultNumber > > | fbox () const |
| Computes the floating-point bounding box of the chain. | |
| constexpr std::vector< PointType > | vertices () const |
| Returns the vertices of the chain (translation applied). | |
| constexpr Polyline< PointType > | asPolyline () const |
| Returns the chain as a polyline traversing its vertices in lexicographic order. | |
| constexpr std::vector< Segment< PointType > > | edges () const |
| Returns the edges of the chain. | |
| constexpr std::vector< OrientedSegment< PointType > > | orientedEdges () const |
| Returns the oriented edges of the chain, each directed from the lexicographically smaller to the larger endpoint. | |
| 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 void | insert (const PointType &point) |
| Extends the chain to contain the given point as a vertex. | |
| template<std::ranges::input_range Range> requires std::ranges::common_range<Range> && std::convertible_to<std::ranges::range_value_t<Range>, PointType> && detail::ownsChainStorage<Storage, PointType> | |
| constexpr void | insert (Range &&points) |
| Extends the chain to contain all the given points as vertices. | |
| constexpr void | erase (std::size_t index) |
| Removes the vertex at the given index (in lexicographic order). | |
| constexpr bool | erase (const PointType &point) |
| Removes the given point from the chain's vertices. | |
| template<class OtherNumber> | |
| constexpr std::optional< std::size_t > | indexAtX (const OtherNumber &x) const |
| Locates the vertex or edge of the chain at a given x-coordinate. | |
| template<class ResultNumber = division_result_t<NumberType>, class OtherNumber> | |
| constexpr std::optional< ResultNumber > | yAtX (const OtherNumber &x) const |
| Evaluates the y-coordinate of the chain at a given x-coordinate. | |
| template<PointConcept OtherPoint> | |
| constexpr std::optional< std::size_t > | isStrictlyBelow (const OtherPoint &point) const |
| Tests whether the whole chain lies strictly below a point at its x. | |
| template<PointConcept OtherPoint> | |
| constexpr std::optional< std::size_t > | isStrictlyAbove (const OtherPoint &point) const |
| Tests whether the whole chain lies strictly above a point at its x. | |
| template<PointConcept OtherPoint> | |
| constexpr std::optional< std::size_t > | isBelow (const OtherPoint &point) const |
| Tests whether the chain passes weakly below a point. | |
| template<PointConcept OtherPoint> | |
| constexpr std::optional< std::size_t > | isAbove (const OtherPoint &point) const |
| Tests whether the chain passes weakly above a point. | |
| 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<DiskConcept OtherDisk> | |
| constexpr bool | contains (const OtherDisk &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<MonotoneChainConcept OtherChain> | |
| constexpr bool | contains (const OtherChain &other) const |
| Tests whether this shape contains the other shape (A ⊇ B). | |
| template<PointConcept OtherPoint> | |
| constexpr bool | contains (const Shape< OtherPoint > &other) const |
| Tests whether this shape contains the other shape (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 &) const |
| Tests whether this shape's boundary contains the other shape (∂A ⊇ B). | |
| template<OrientedLineConcept OtherOrientedLine> | |
| constexpr bool | boundaryContains (const OtherOrientedLine &) const |
| Tests whether this shape's boundary contains the other shape (∂A ⊇ B). | |
| template<RayConcept OtherRay> | |
| constexpr bool | boundaryContains (const OtherRay &) const |
| Tests whether this shape's boundary contains the other shape (∂A ⊇ B). | |
| template<HalfplaneConcept OtherHalfplane> | |
| constexpr bool | boundaryContains (const OtherHalfplane &) 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<MonotoneChainConcept OtherChain> | |
| constexpr bool | boundaryContains (const OtherChain &other) const |
| Tests whether this shape's boundary 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<PointConcept OtherPoint> | |
| constexpr bool | boundaryContains (const Shape< OtherPoint > &other) const |
| Tests whether this shape's boundary contains the other shape (∂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<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<TriangleConcept OtherTriangle> | |
| constexpr bool | interiorContains (const OtherTriangle &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<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<DiskConcept OtherDisk> | |
| constexpr bool | interiorContains (const OtherDisk &other) const |
| Tests whether this shape's interior contains the other shape (A∖∂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<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 Shape< OtherPoint > &other) const |
| Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B). | |
| 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<MonotoneChainConcept OtherChain> | |
| constexpr bool | intersects (const OtherChain &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<DiskConcept OtherDisk> | |
| constexpr bool | intersects (const OtherDisk &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<class EmptyPoint> | |
| constexpr bool | intersects (const EmptyShape< EmptyPoint > &) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<PointConcept OtherPoint> | |
| constexpr bool | intersects (const Shape< OtherPoint > &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) | |
| constexpr bool | intersects (const OtherShape &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 shapes intersect (A° ∩ B° ≠ ∅). | |
| template<SegmentConcept OtherSegment> | |
| constexpr bool | interiorsIntersect (const OtherSegment &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<OrientedSegmentConcept OtherOrientedSegment> | |
| constexpr bool | interiorsIntersect (const OtherOrientedSegment &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<LineConcept OtherLine> | |
| constexpr bool | interiorsIntersect (const OtherLine &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<OrientedLineConcept OtherOrientedLine> | |
| constexpr bool | interiorsIntersect (const OtherOrientedLine &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<RayConcept OtherRay> | |
| constexpr bool | interiorsIntersect (const OtherRay &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<HalfplaneConcept OtherHalfplane> | |
| constexpr bool | interiorsIntersect (const OtherHalfplane &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<RectangleConcept OtherRectangle> | |
| constexpr bool | interiorsIntersect (const OtherRectangle &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<TriangleConcept OtherTriangle> | |
| constexpr bool | interiorsIntersect (const OtherTriangle &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<ConvexConcept OtherConvex> | |
| constexpr bool | interiorsIntersect (const OtherConvex &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<DiskConcept OtherDisk> | |
| constexpr bool | interiorsIntersect (const OtherDisk &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<MonotoneChainConcept OtherChain> | |
| constexpr bool | interiorsIntersect (const OtherChain &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<class EmptyPoint> | |
| constexpr bool | interiorsIntersect (const EmptyShape< EmptyPoint > &) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<PointConcept OtherPoint> | |
| constexpr bool | interiorsIntersect (const Shape< OtherPoint > &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) | |
| constexpr bool | interiorsIntersect (const OtherShape &other) const |
| Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅). | |
| template<PointConcept OtherPoint> | |
| constexpr bool | separates (const OtherPoint &) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| 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<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<RayConcept OtherRay> | |
| constexpr bool | separates (const OtherRay &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 | separates (const OtherChain &other) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| 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 | 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<class EmptyPoint> | |
| constexpr bool | separates (const EmptyShape< EmptyPoint > &) const |
| Tests whether removing this shape disconnects the other shape (B∖A is disconnected). | |
| template<PointConcept OtherPoint> | |
| constexpr bool | separates (const Shape< OtherPoint > &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<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<RayConcept OtherRay> | |
| constexpr bool | crosses (const OtherRay &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<HalfplaneConcept OtherHalfplane> | |
| constexpr bool | crosses (const OtherHalfplane &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<RectangleConcept OtherRectangle> | |
| constexpr bool | crosses (const OtherRectangle &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<TriangleConcept OtherTriangle> | |
| constexpr bool | crosses (const OtherTriangle &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<DiskConcept OtherDisk> | |
| constexpr bool | crosses (const OtherDisk &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<ConvexConcept OtherConvex> | |
| constexpr bool | crosses (const OtherConvex &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| 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 EmptyPoint> | |
| constexpr bool | crosses (const EmptyShape< EmptyPoint > &) 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<typename OtherShape> requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) | |
| constexpr bool | crosses (const OtherShape &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| template<MonotoneChainConcept OtherChain> | |
| constexpr bool | edgesCross (const OtherChain &other) const |
| Tests whether the two chains have edges that cross. | |
| 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 with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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 with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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 with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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 with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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 with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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 > > > > | intersection (const OtherHalfplane &other) const |
| Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle> | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherRectangle &other) const |
| Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle> | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherTriangle &other) const |
| Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex> | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherConvex &other) const |
| Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires (!PointConcept<OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) && requires(const OtherShape& o, const MonotoneChain& self) { o.template intersection<ResultNumber>(self); }) | |
| constexpr 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>, MonotoneChainConcept OtherChain> | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherChain &other) const |
| Returns the intersection of the two chains (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| 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>, 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>, MonotoneChainConcept OtherChain> | |
| constexpr auto | squaredDistance (const OtherChain &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 = division_result_t<NumberType>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) && requires(const OtherShape& o, const MonotoneChain& 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 = NumberType, BoundedPolygonalConcept OtherShape> requires detail::ClosestPairConcept<MonotoneChain<PointType_, TLabel, Storage>, 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<MonotoneChain<PointType_, TLabel, Storage>, 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>, 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>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>) && requires(const OtherShape& o, const MonotoneChain& 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 = double, PointConcept OtherPoint> | |
| constexpr auto | distanceL1 (const Shape< OtherPoint > &other) const |
| Returns the distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceL1. | |
| 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>, MonotoneChainConcept OtherChain> | |
| constexpr auto | distanceLInf (const OtherChain &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<MonotoneChain>) && requires(const OtherShape& o, const MonotoneChain& 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 distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceLInf. | |
| template<class ApproximateNumber = double> | |
| ApproximateNumber | length () const |
| Computes the Euclidean length of the chain (the sum of its edge lengths). | |
| constexpr auto | lengthL1 () const |
| Computes the Manhattan (L1) length of the chain. | |
| constexpr auto | lengthLInf () const |
| Computes the Chebyshev (LInf) length of the chain. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| constexpr Point< ResultNumber > | pointInside () const |
| Returns a point inside the chain. | |
| 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. | |
| constexpr OwningChain | rotated90 (int k=1) const |
| Returns the chain rotated by 90k degrees around the origin. | |
| constexpr void | rotate90 (int k=1) |
| Rotates the chain by 90k degrees around the origin in place. | |
| template<class OtherNumber> | |
| constexpr OwningChain | scaledUpX (const OtherNumber scalar) const |
| Returns the chain with its x-coordinates multiplied by a factor. | |
| template<class OtherNumber> requires detail::ownsChainStorage<Storage, PointType> | |
| constexpr void | scaleUpX (const OtherNumber scalar) |
| Multiplies the chain's x-coordinates by a factor in place. | |
| template<class OtherNumber> | |
| constexpr OwningChain | scaledUpY (const OtherNumber scalar) const |
| Returns the chain with its y-coordinates multiplied by a factor. | |
| template<class OtherNumber> requires detail::ownsChainStorage<Storage, PointType> | |
| constexpr void | scaleUpY (const OtherNumber scalar) |
| Multiplies the chain's y-coordinates by a factor in place. | |
| template<class OtherNumber> | |
| constexpr OwningChain | scaledDownX (const OtherNumber scalar) const |
| Returns the chain with its x-coordinates divided by a divisor. | |
| template<class OtherNumber> requires detail::ownsChainStorage<Storage, PointType> | |
| constexpr void | scaleDownX (const OtherNumber scalar) |
| Divides the chain's x-coordinates by a divisor in place. | |
| template<class OtherNumber> | |
| constexpr OwningChain | scaledDownY (const OtherNumber scalar) const |
| Returns the chain with its y-coordinates divided by a divisor. | |
| template<class OtherNumber> requires detail::ownsChainStorage<Storage, PointType> | |
| constexpr void | scaleDownY (const OtherNumber scalar) |
| Divides the chain's y-coordinates by a divisor in place. | |
| template<class OtherShape> requires MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape> | |
| constexpr auto | minkowskiSum (const OtherShape &other) const |
| Returns the Minkowski sum of this shape and another (A ⊕ B). | |
| template<class OtherShape> requires MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, 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<MonotoneChain<PointType_, TLabel, Storage>, 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>, ConvexConcept OtherConvex> | |
| Polygon< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherConvex &other) const |
| Returns the Minkowski sum of the chain and a bounded convex shape (A ⊕ B), as a single polygon. | |
| template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle> | |
| Polygon< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherTriangle &other) const |
| Returns the Minkowski sum of the two shapes (A ⊕ B), as one polygon. | |
| template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle> | |
| Polygon< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherRectangle &other) const |
| Returns the Minkowski sum of the two shapes (A ⊕ B), as one polygon. | |
| template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherSegment &other) const |
| Returns the regularized Minkowski sum of the chain and a segment (A ⊕ B), as a set of regions. | |
| template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOriented> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherOriented &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherChain &other) const |
| Returns the regularized Minkowski sum of the two chains (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires (!MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape> && (detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain<PointType_, TLabel, Storage>>) && requires(const OtherShape& o, const MonotoneChain& self) { o.template minkowskiSum<ResultNumber>(self); }) | |
| auto | minkowskiSum (const OtherShape &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<PointConcept OtherPoint> | |
| constexpr MonotoneChain & | operator+= (const OtherPoint &translation) |
| Translates the chain by the given point. | |
| template<PointConcept OtherPoint> | |
| constexpr MonotoneChain & | operator-= (const OtherPoint &translation) |
| Translates the chain by the negation of the given point. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar> && detail::ownsChainStorage<Storage, PointType>) | |
| constexpr MonotoneChain & | operator*= (const Scalar &scalar) |
| Scales the chain by the given scalar. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar> && detail::ownsChainStorage<Storage, PointType>) | |
| constexpr MonotoneChain & | operator/= (const Scalar &scalar) |
| Divides the chain by the given scalar. | |
| template<class ResultNumber, ConvexConcept OtherConvex> | |
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherConvex &other) const |
| template<class ResultNumber, TriangleConcept OtherTriangle> | |
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherTriangle &other) const |
| template<class ResultNumber, RectangleConcept OtherRectangle> | |
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherRectangle &other) const |
| template<class ResultNumber, SegmentConcept OtherSegment> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherSegment &other) const |
| template<class ResultNumber, OrientedSegmentConcept OtherOriented> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherOriented &other) const |
| template<class ResultNumber, MonotoneChainConcept OtherChain> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherChain &other) const |
| template<class OtherNumber> | |
| constexpr MonotoneChain< PointType, LabelType > | scaledUpX (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr MonotoneChain< PointType, LabelType > | scaledUpY (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr MonotoneChain< PointType, LabelType > | scaledDownX (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr MonotoneChain< PointType, LabelType > | scaledDownY (const OtherNumber scalar) const |
Weakly x-monotone polyline stored by lexicographically sorted vertices.
A weakly x-monotone polyline stored by its sorted vertices plus a translation.
MonotoneChain mirrors the storage layout of Polygon — a vector of vertices and a translation_ applied lazily on access — but the vertices form an open chain, not a closed boundary, and they obey a monotonicity invariant: the stored sequence is strictly increasing in the lexicographic point order (smaller x first, ties broken by smaller y). Consecutive vertices may therefore share an x-coordinate, producing a vertical edge, so the chain is weakly x-monotone; isStrictlyMonotone reports whether every x appears at most once (the chain is the graph of a function).
The constructor normalizes any input to this canonical form by sorting the points lexicographically and removing duplicates. The input is thus treated as a point set, not as a pre-linked chain: shuffled input yields the same object. Because the order is unique, the chain is automatically simple (edges meet only at shared endpoints), and operator==/operator<=> give a translation-consistent geometric equality.
As a 1-dimensional manifold with boundary, the chain's boundary is its two extreme vertices and its relative interior is everything else (matching the convention of Segment).
| PointType_ | The vertex point type. |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>> |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::EdgeIterator = BoundaryIterator<false> |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::LabelType = TLabel |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::NumberType = PointType::NumberType |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::OrientedEdgeIterator = BoundaryIterator<true> |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::OwningChain = MonotoneChain<PointType_, TLabel, std::vector<PointType_>> |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::PointType = PointType_ |
| using pgl::MonotoneChain< PointType_, TLabel, Storage >::StorageType = Storage |
|
constexprdefault |
Creates a chain with no vertex.
|
inlineexplicitconstexpr |
Creates a chain from a range of points.
The points are treated as a set: unless trusted is set, they are sorted lexicographically and duplicates are removed, producing the canonical weakly x-monotone chain through them.
| Range | Input range whose elements can be converted to PointType. |
| points | Range of vertices in any order. |
| trusted | Set to true if the points are already sorted and unique. |
|
inlineexplicitconstexpr |
Creates a non-owning chain viewing an external contiguous range of vertices (view instantiations only, e.g. MonotoneChainView).
The view cannot sort or deduplicate memory it does not own, so the input must already be in canonical form — sorted lexicographically with no duplicates (the trusted contract of the owning constructors). The caller retains ownership of the underlying storage and is responsible for keeping it alive for the lifetime of the view.
| Range | Contiguous range of vertices convertible to Storage. |
| points | Canonical range of vertices to view. |
|
inlineexplicitconstexpr |
Creates a chain from a flat list of coordinates.
The values are consumed in pairs (x0, y0, x1, y1, …), each pair forming one vertex, so the list must hold an even number of values. Unless trusted is set, the vertices are sorted lexicographically and duplicates are removed.
| coords | Interleaved x/y coordinates of the vertices. |
| trusted | Set to true if the points are already sorted and unique. |
|
inlineconstexpr |
Converts a chain with compatible vertex type.
The source is already canonical; a translation or a non-narrowing type conversion preserves that, so no renormalization is needed.
| OtherPointType | Source vertex type. |
| other | Source chain. |
|
nodiscardconstexpr |
Returns the chain as a polyline traversing its vertices in lexicographic order.
The chain's vertices are already sorted lexicographically, which is the canonical polyline direction, so no renormalization is needed. The chain's own label is not carried over.
|
constexpr |
Computes the bounding box of the chain.
The x-extent is free (first and last vertex), but the y-extent requires a scan, so the result is computed on the first call and cached in bbox_; later calls return the stored value. Any operation that modifies the chain resets the cache.
Complexity: O(n) for n vertices on the first call, O(1) thereafter.
|
inlineconstexpr |
Returns a constant iterator to the first vertex.
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
The boundary of a chain is its two extreme vertices (matching the endpoint convention of Segment).
Complexity: O(1).
| OtherPoint | Type of the point. |
| point | Point to test. |
Weakly x-monotone chain predicates: the boundary of a chain is its two extreme vertices, matching the endpoint convention of Segment.
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
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.
|
nodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's boundary contains the other shape (∂A ⊇ B).
|
inlineconstexpr |
Returns a constant iterator to the first vertex.
|
inlineconstexpr |
Returns a constant iterator past the last vertex.
|
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.
| 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.
|
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.
| 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 |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
A chain contains another chain exactly when every edge of the other is a straight sub-path of this chain (and its vertices for a degenerate other).
Complexity: O(m (log n + k)) for m vertices of the other chain.
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
Complexity: O(log n) for n vertices.
| OtherPoint | Type of the point. |
| point | Point to test. |
Weakly x-monotone chain predicates: point location by binary search on x, straight sub-path containment, and degenerate reductions for the shapes a 1-dimensional bounded set can contain.
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
A polygon lies on the 1-dimensional chain exactly when all of its edges do (its interior is then empty), so this folds contains over the polygon's edges.
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
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.
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
A chain contains a segment exactly when the segment is a straight sub-path of the chain: both endpoints lie on the chain and every chain vertex between them is collinear with the segment. The scan exits at the first bend.
Complexity: O(log n + k) for n vertices, where k is the number of chain vertices spanned by the segment's x-range.
| OtherSegment | Type of the other segment. |
| other | Segment to test. |
|
inlinenodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
|
inlineconstexpr |
Returns the convex hull of the chain's vertices.
|
inlinenodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
inlinenodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
Mutual-cut predicates for a weakly x-monotone chain: a.crosses(b) is a.separates(b) && b.separates(a), so the pairs whose separates is not implemented yet throw through it.
|
inlinenodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
nodiscardconstexpr |
Tests whether the two shapes mutually separate each other (each disconnects the other).
|
inlineconstexpr |
Returns a segment realizing the diameter (the farthest vertex pair).
The farthest pair of vertices lies on the convex hull of the vertex set, so this builds a Convex from the chain vertices and returns that hull's Convex::diameter(). Distances are compared exactly via squared length.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
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.
|
nodiscardconstexpr |
Returns the Manhattan (L1) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
inlinenodiscardconstexpr |
Returns the distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceL1.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
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.
|
nodiscardconstexpr |
Returns the Chebyshev (LInf) distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
ResultNumber the exact distance is generally a fraction, so the internal division truncates. Request a floating-point or pgl::Rational result type for an accurate value.
|
inlinenodiscardconstexpr |
Returns the distance to the given shape, using symmetry to re-dispatch through the wrapper's own distanceLInf.
|
inlineconstexpr |
Returns the edges of the chain.
A chain with n vertices has n - 1 edges (none for a degenerate chain); there is no closing edge back to the first vertex.
|
inlineconstexpr |
Returns an iterator to the first unoriented edge.
|
nodiscardconstexpr |
Tests whether the two chains have edges that cross.
True iff some edge of this chain and some edge of other cross: their interiors meet at a single point.
Both edge sequences are sorted by x-interval, so the proper-crossing pair is found by a merge sweep in O(n + m) for chains with n and m vertices.
| OtherChain | Type of the other chain. |
| other | The other chain. |
other.
|
inlineconstexpr |
Returns an iterator past the last unoriented edge.
|
inlineconstexpr |
|
inlineconstexpr |
Checks whether the chain has no vertex.
|
inlineconstexpr |
Returns a constant iterator past the last vertex.
|
inlineconstexpr |
Removes the given point from the chain's vertices.
Nothing happens when the point is not a vertex. Removing an interior vertex reroutes the chain, linking the erased vertex's two neighbours by a single edge; removing an extreme vertex shortens the chain (the vertices are a point set, §constructor). The result stays canonical, so the chain remains weakly x-monotone.
Complexity: O(log n) comparisons plus O(n) vector shift; O(1) shift when erasing the last vertex.
| point | The vertex to remove. |
point is not a vertex of the chain.
|
inlineconstexpr |
Removes the vertex at the given index (in lexicographic order).
The index-taking counterpart of erase(const PointType&), skipping the search when the position is already known — e.g. the index returned by Pangolin or indexAtX. Rerouting works the same way: the erased vertex's neighbours become adjacent, and the chain stays canonical.
Complexity: O(n) vector shift for n vertices; O(1) when erasing the last vertex.
| index | The index of the vertex to remove; must be less than size(). |
|
constexpr |
Computes the floating-point bounding box of the chain.
| ResultNumber | The floating-point type for the result. |
|
inlineconstexpr |
Accesses a vertex by index modulo the vertex count.
Unlike Polygon the chain is not cyclic — edges never wrap around — but get still reduces the index modulo size() (Euclidean, so negative indices count from the back) to satisfy the common vertex access interface of Shape.
| index | The index of the vertex, reduced modulo the vertex count. |
|
inlinenodiscardconstexpr |
Returns the point the chain collapses to, if it does.
Complexity: O(n), returning at the first differing vertex.
|
inlinenodiscardconstexpr |
Returns the segment the chain collapses to, if it does.
Complexity: O(n).
|
inlineconstexpr |
Returns the smallest index i with (*this)[i] == point, or -1 if point is not a vertex.
Complexity: O(log n) for n vertices (binary search on the sorted vertex sequence).
| point | The vertex to locate. |
|
nodiscardconstexpr |
Locates the vertex or edge of the chain at a given x-coordinate.
Returns the smallest index i such that (*this)[i].x() == x, or, when no vertex has that x-coordinate, the unique i with (*this)[i].x() < x < (*this)[i+1].x(). Empty when x lies outside the chain's x-extent or the chain is empty. At a vertical edge the returned index is the edge's bottom vertex.
Complexity: O(log n) for n vertices.
| OtherNumber | Query x-coordinate type. |
| x | Query x-coordinate. |
|
inlineconstexpr |
Extends the chain to contain the given point as a vertex.
Inserts the point at its lexicographic position; a point that is already a vertex leaves the chain unchanged. Note that inserting a point whose x-coordinate lies inside an existing edge's x-range reroutes the chain through the new vertex (the vertices are a point set, §constructor).
Complexity: O(log n) comparisons plus O(n) vector shift; amortized O(1) shift when appending at either end.
| point | The vertex to add. |
|
inlineconstexpr |
Extends the chain to contain all the given points as vertices.
Equivalent to inserting each point of the range, but sorts the new points once and merges, so it is cheaper for bulk insertion.
Complexity: O((n + k) log(n + k)) for k inserted points.
| points | Range of vertices to add, in any order. |
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
The relative interior of a chain is the chain minus its two extreme vertices.
Complexity: O(log n) for n vertices.
| OtherPoint | Type of the point. |
| point | Point to test. |
Weakly x-monotone chain predicates: the relative interior of a chain is the chain minus its two extreme vertices, matching the convention of Segment.
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
Complexity: O(log n + k) for n vertices, where k is the number of chain vertices spanned by the segment's x-range.
| OtherSegment | Type of the other segment. |
| other | Segment to test. |
|
inlinenodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
nodiscardconstexpr |
Tests whether this shape's interior contains the other shape (A∖∂A ⊇ B).
|
inlinenodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
Merge sweep over the open edge pairs plus the crossing-at-a-non-extreme- vertex checks in both directions.
Complexity: O(n + m log n) for chains with n and m vertices.
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
A point's interior is the point itself, so this matches interiorContains.
Complexity: O(log n) for n vertices.
Weakly x-monotone chain predicates. The chain's relative interior is the chain minus its two extreme vertices, so non-extreme vertices count as interior points alongside the open edges.
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
The chain's relative interior is the chain minus its extreme vertices, so a chain vertex other than the extremes counts as interior: a segment whose open part passes exactly through such a vertex engages this predicate even though it crosses no open edge.
Complexity: O(log n + k) for n vertices, where k is the number of chain edges overlapping the segment's x-range (worst case O(n)).
| OtherSegment | Type of the other segment. |
| other | Segment to test. |
|
inlinenodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
|
nodiscardconstexpr |
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.
|
nodiscardconstexpr |
Returns the intersection of the two chains (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Two chains can overlap along collinear sub-segments, so the result is a vector of point-or-segment variants. Pieces are maximal: adjacent collinear overlaps are coalesced into single segments, and points covered by a reported segment are dropped. Computed by the same merge sweep as intersects(const OtherChain&).
Complexity: O(n + m) intersection tests for chains with n and m vertices, plus sorting the resulting pieces.
| ResultNumber | Number type of the returned coordinates. |
| OtherChain | Type of the other chain. |
| other | Chain to intersect with. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
inlinenodiscardconstexpr |
Returns the intersection of the two shapes (A ∩ B), empty when they are disjoint.
|
nodiscardconstexpr |
Returns the intersection with a one-dimensional or convex shape (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Folds the shape over the chain edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherChain&) const.
| ResultNumber | Number type of the returned coordinates. |
|
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 ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
Merge sweep over the two sorted vertex sequences: the pointers advance by lexicographically smaller edge right endpoint, and only edge pairs whose x-ranges overlap are tested.
Complexity: O(n + m) for chains with n and m vertices.
| OtherChain | Type of the other chain. |
| other | Chain to test. |
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
Only the chain edges whose x-range meets the segment's x-range are tested, located by binary search.
Complexity: O(log n + k) for n vertices, where k is the number of chain edges overlapping the segment's x-range (worst case O(n)).
| OtherSegment | Type of the other segment. |
| other | Segment to test. |
|
inlinenodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅).
|
nodiscardconstexpr |
Tests whether the chain passes weakly above a point.
Engaged iff a ray shot straight up from point intersects the chain (a point on the chain counts). The engaged value is the index indexAtX returns for point.x().
Complexity: O(log n) for n vertices. Exact (division-free).
| point | The query point. |
|
nodiscardconstexpr |
Tests whether the chain passes weakly below a point.
Engaged iff a ray shot straight down from point intersects the chain (a point on the chain counts). The engaged value is the index indexAtX returns for point.x().
Note that isBelow and isAbove are not complementary: both are engaged when the point lies on the chain, and both are empty when point.x() is outside the chain's x-extent.
Complexity: O(log n) for n vertices. Exact (division-free).
| point | The query point. |
|
inlineconstexpr |
Checks if the chain is degenerate (fewer than two vertices, so it has no edge).
|
inlinenodiscardconstexpr |
Checks whether the chain covers exactly one point.
Unlike isDegenerate, this is about the point set rather than the edge count: a chain repeating one vertex many times is a single point.
Complexity: O(n), returning at the first differing vertex.
|
inlinenodiscardconstexpr |
Checks whether the chain covers exactly one segment of positive length.
True when the vertices are collinear but not all equal. The chain is connected, so collinear vertices make its edges cover the single segment spanning them.
Complexity: O(n), returning at the first non-collinear vertex.
|
nodiscardconstexpr |
Tests whether the whole chain lies strictly above a point at its x.
Engaged iff, at point.x(), every part of the chain is strictly above point — i.e. the bottom of the chain's vertical run there is above the point. A point lying on the chain (including inside a vertical edge) counts as neither; see isStrictlyBelow.
Complexity: O(log n) for n vertices. Exact (division-free).
| point | The query point. |
|
nodiscardconstexpr |
Tests whether the whole chain lies strictly below a point at its x.
Engaged iff, at point.x(), every part of the chain is strictly below point — i.e. the top of the chain's vertical run there is below the point. A point lying on the chain (including inside a vertical edge) counts as neither below nor above, so isStrictlyBelow and isStrictlyAbove are mutually exclusive, and both are empty when the point is on the chain or point.x() is outside the chain's x-extent. (Contrast the weak isBelow, which a point on the chain satisfies.) The engaged value is the index indexAtX returns for point.x().
Complexity: O(log n) for n vertices. Exact (division-free).
| point | The query point. |
|
inlinenodiscardconstexpr |
Tests whether the chain is strictly x-monotone.
True when no two vertices share an x-coordinate (equivalently, the chain has no vertical edge), so the chain is the graph of a function of x. A chain with fewer than two vertices is trivially strict.
Complexity: O(n).
|
inlinenodiscardconstexpr |
Checks whether the chain is degenerate without covering a point or a segment.
True only for the empty chain, which has no defining vertex: a chain with a single vertex is a point, and any chain with an edge covers at least a segment.
Complexity: O(1).
|
inlineconstexpr |
Returns the chain label.
The label is mutable even through a const chain: it is metadata that does not participate in equality, hashing, or geometric predicates.
|
nodiscard |
Returns the integer points the chain contains.
The lattice points of the edges, one edge at a time, which for a chain is increasing order: a vertex shared by two edges is reported once, and a chain meets no point twice otherwise. A single vertex answers for itself.
| 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. |
| ApproximateNumber pgl::MonotoneChain< PointType, LabelType, Storage >::length | ( | ) | const |
Computes the Euclidean length of the chain (the sum of its edge lengths).
| ApproximateNumber | The floating-point type for the result. |
|
constexpr |
Computes the Manhattan (L1) length of the chain.
|
constexpr |
Computes the Chebyshev (LInf) length of the chain.
|
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 chain has no area, so the erosion of one has none either.
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::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherChain & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two chains (A ⊕ B).
Monotone on both sides and it still buys nothing: the theorem that makes a chain's sum with a convex shape one polygon needs a convex operand, and a second chain is not one — two monotone chains sum to a set that a vertical line can meet in several intervals. So this is the plain region-valued construction, with both operands contributing their edges, exactly as Polyline::minkowskiSum(const OtherPolyline&) const runs it for two chains that need not be sorted at all.
Neither operand has area, so there is no body and no precondition: an edge direction the two share sweeps out nothing, and the answer can come back in pieces or empty for perfectly valid chains.
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > pgl::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherConvex & | other | ) | const |
|
nodiscard |
Returns the Minkowski sum of the chain and a bounded convex shape (A ⊕ B), as a single polygon.
The sum is {p + q : p ∈ A, q ∈ B}. A chain is not convex, so this pair is not one MinkowskiSummableConcept accepts; it is not one of the region-valued sums either. The sum of an x-monotone chain with a convex shape is a monotone polygon: every vertical line meets it in a single interval, so it is the region between two x-monotone chains and can never enclose a hole, split into pieces, or need regularizing. Compare Polyline::minkowskiSum(const OtherConvex&) const, which answers the same question for a chain that may bend back on itself and therefore has to return a PolygonWithHoles region.
The operand must be a body: the closure of a connected, non-empty interior, which for these three types is exactly nondegenerate. That is what makes one polygon the right answer rather than a lucky one. The result is otherwise not regularized — it is the sum's point set exactly — and an operand that has collapsed to a segment or a point is off the contract for that reason and not merely by convention: the sum of a chain with a flat operand can pinch shut where two of its parts merely touch, and what comes back then is a ring that touches itself, which is not a simple polygon. The two operands that legitimately have no area, Segment and OrientedSegment, are kept out of this overload set on the same grounds and keep the region-valued contract — see minkowskiSum(const OtherSegment&) const, which is also the overload a flat operand's point set is available from.
Complexity: one convex merge per chain edge, O(nm) for a chain of n vertices and an operand of m, then one sweep merging the pieces' arcs into the two boundaries. The pieces arrive already sorted along x, so the sweep touches only what an incoming piece can still reach: no arrangement is built and nothing is triangulated.
| ResultNumber | The number type for the result. |
| other | The shape to sum with. |
ResultNumber once, so ask for an exact ResultNumber unless you know the sum lands on the lattice. | PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherOriented & | 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.
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > pgl::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherRectangle & | other | ) | const |
|
nodiscard |
Returns the Minkowski sum of the two shapes (A ⊕ B), as one polygon.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherSegment & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the chain and a segment (A ⊕ B), as a set of regions.
The thinnest operand a chain takes, and the one operand of the set with no area of its own: a chain edge and the segment span a parallelogram unless the two are parallel, in which case they span a segment. That is what puts this pair on the region-valued contract rather than the polygon-valued one above. An edge parallel to the summand sweeps out nothing, so the sum can carry a stretch with no area beside it and can pinch shut where two of its parts merely touch — and a polygon may do neither. The answer is therefore closure((A ⊕ B)°), in pieces, exactly as Polyline::minkowskiSum(const OtherSegment&) const returns it: a chain that is a segment parallel to the summand comes back empty, and one whose parts touch at a point comes back as two regions.
The pieces never have holes — each is a slice of a region that meets every vertical line in an interval — and they are built by the same sweep as the polygon-valued sums, so this stays the cheap answer that the chain's monotonicity buys: no arrangement, and no rational unless a crossing needs one.
| ResultNumber | The number type for the result. |
| other | The shape to sum with. |
|
inlinenodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
The operands left over are the ones whose own concavity can strand a cavity, so the sum needs a region-valued result however monotone the chain is. The exact return type is provided by the higher-ranked operand. Forwards to the other shape's implementation so that each unordered pair needs the sum defined only once, on the higher-ranked shape; see Polygon::minkowskiSum(const OtherChain&) const for the contract.
|
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.
| OtherShape | Type of the other shape. |
| other | Shape to sum with. |
| Polygon< Point< ResultNumber, typename PointType_::LabelType > > pgl::MonotoneChain< PointType_, TLabel, Storage >::minkowskiSum | ( | const OtherTriangle & | other | ) | const |
|
nodiscard |
Returns the Minkowski sum of the two shapes (A ⊕ B), as one polygon.
|
inlineconstexpr |
Scales the chain by the given scalar.
Complexity: O(n log n) for n vertices. Scaling by a negative factor reverses the lexicographic order (and by zero collapses the chain to a point), so the chain is renormalized to stay canonical.
|
inlineconstexpr |
Translates the chain by the given point.
Complexity: O(1).
|
inlineconstexpr |
Translates the chain by the negation of the given point.
Complexity: O(1).
|
inlineconstexpr |
Divides the chain by the given scalar.
Complexity: O(n log n) for n vertices; renormalizes like operator*=.
|
inlineconstexpr |
Compares two chains by their canonical vertex sequences.
Templated on the other chain's storage so an owning chain and a view over the same vertices compare equal; the vertices are read through the public (translation-applied) accessors, so no cross-instantiation access is needed.
|
inlineconstexpr |
Checks equality of two chains.
|
inlineconstexpr |
Accesses a vertex by index (in lexicographic order).
| index | The index of the vertex. |
|
inlineconstexpr |
Returns the oriented edges of the chain, each directed from the lexicographically smaller to the larger endpoint.
|
inlineconstexpr |
Returns an iterator to the first oriented edge.
|
inlineconstexpr |
Returns an iterator past the last oriented edge.
|
inlineconstexpr |
Lazy view counterpart of orientedEdges(); see edgesView().
|
nodiscardconstexpr |
Returns a point inside the chain.
This is the point inside the segment formed by the first two vertices, i.e. the midpoint of that edge.
| ResultNumber | Coordinate type of the result. |
|
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.
|
constexpr |
Rotates the chain by 90k degrees around the origin in place.
| k | Number of 90-degree CCW rotations (may be negative). |
|
nodiscardconstexpr |
Returns the chain rotated by 90k degrees around the origin.
An odd number of rotations turns an x-monotone chain into a y-monotone one, so the result is renormalized: it is the canonical chain on the rotated point set, which generally links the vertices in a different order than the source chain.
| k | Number of 90-degree CCW rotations (may be negative). |
|
nodiscardconstexpr |
Tests whether another shape defines exactly the same point set.
|
constexpr |
|
nodiscardconstexpr |
Returns the chain with its x-coordinates divided by a divisor.
|
constexpr |
|
nodiscardconstexpr |
Returns the chain with its y-coordinates divided by a divisor.
|
constexpr |
Divides the chain's x-coordinates by a divisor in place.
|
constexpr |
Divides the chain's y-coordinates by a divisor in place.
|
constexpr |
|
nodiscardconstexpr |
Returns the chain with its x-coordinates multiplied by a factor.
|
constexpr |
|
nodiscardconstexpr |
Returns the chain with its y-coordinates multiplied by a factor.
|
constexpr |
Multiplies the chain's x-coordinates by a factor in place.
|
constexpr |
Multiplies the chain's y-coordinates by a factor in place.
|
inlinenodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
Both chains are arcs whose arc order matches lexicographic order, so removing this cuts the other exactly when the other has ordered points a < b < c with b on this and a, c off it (an edge carrying all three is a separated edge; otherwise a and c straddle a covered vertex or edge).
Complexity: O(n + m) for n and m vertices.
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
No straight edge can disconnect a halfplane, but a chain bending through the interior between two boundary contacts seals off a pocket against the boundary line.
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
inlinenodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
Removing anything from a single point never disconnects it.
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
The polygon may be non-convex, so the scan also spots edges that leave the interior between two interior vertices (see separatesTwoDimensional).
|
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 (see detail::separates1DSet).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
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).
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.
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
True when some connected component of the intersection with the segment avoids both segment endpoints. Exact and division-free: the component walk only uses edge intersection and containment predicates.
Complexity: O(n) for n vertices.
|
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.
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
|
inlineconstexpr |
Returns the number of vertices in the chain.
|
nodiscard |
Returns the squared Euclidean distance to a disk.
Forwards to Disk::squaredDistance's model. 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.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
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.
|
nodiscardconstexpr |
Returns the squared Euclidean distance to the given shape.
Zero when the shapes intersect, otherwise the minimum over the chain edges. The chain must have at least one edge.
Complexity: O(n) edge queries for n vertices, plus the intersection test.
| 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, e.g. squaredDistance<double>(point), for an accurate value.
|
inlineconstexpr |
Returns the vertices of the chain (translation applied).
|
inlineconstexpr |
Returns a lazy view over the vertices, translating each on the fly instead of allocating a vector.
Same lexicographically sorted vertex sequence as vertices(), with no heap allocation. The chain is itself a vertex range, so this is just begin() and end() packaged as a view for callers that take one.
|
nodiscardconstexpr |
Evaluates the y-coordinate of the chain at a given x-coordinate.
The value is returned only when x lies within the chain's x-extent. Vertices are handled exactly. When x falls on a vertical edge (or on a vertex that starts one), the y of the edge's bottom vertex is returned; isStrictlyMonotone is the precondition for yAtX to be the unique value of the chain at every x.
Complexity: O(log n) for n vertices.
| ResultNumber | Return coordinate type. |
| OtherNumber | Query x-coordinate type. |
| x | Query x-coordinate. |
1.17.0