 |
Pangolin
Header-only C++20 plane computational geometry library
|
|
Pangolin
Header-only C++20 plane computational geometry library
|
Open polygonal chain stored in traversal order; may self-intersect. More...
#include <polyline.hpp>
Classes | |
| class | BoundaryIterator |
| Forward iterator over the (optionally oriented) polyline edges. More... | |
Public Types | |
| using | PointType = PointType_ |
| using | NumberType = PointType::NumberType |
| using | LabelType = TLabel |
| template<bool Oriented> | |
| using | BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>> |
| using | EdgeIterator = BoundaryIterator<false> |
| using | OrientedEdgeIterator = BoundaryIterator<true> |
Public Member Functions | |
| constexpr | Polyline ()=default |
| Creates a polyline with no vertex. | |
| template<std::ranges::input_range Range = std::initializer_list<PointType>> requires std::ranges::common_range<Range> && std::convertible_to<std::ranges::range_value_t<Range>, PointType> | |
| constexpr | Polyline (Range &&points) |
| Creates a polyline from a range of points. | |
| constexpr | Polyline (std::initializer_list< NumberType > coords) |
| Creates a polyline from a flat list of coordinates. | |
| template<PointConcept OtherPointType, class OtherLabelType> requires std::constructible_from<PointType, const OtherPointType&> | |
| constexpr | Polyline (const Polyline< OtherPointType, OtherLabelType > &other) |
| Converts a polyline with compatible vertex type. | |
| template<class A = LabelType> requires (detail::has_label_v<A>) | |
| constexpr A & | label () const |
| Returns the polyline label. | |
| constexpr const PointType | operator[] (std::size_t index) const |
| Accesses a vertex by index (in traversal order). | |
| constexpr PointType | get (std::ptrdiff_t index) const |
| Accesses a vertex by index modulo the vertex count. | |
| template<PointConcept OtherPoint> | |
| constexpr void | set (std::size_t index, const OtherPoint &point) |
| Replaces the vertex at the given index. | |
| 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. | |
| template<PointConcept OtherPoint> | |
| constexpr void | insert (std::size_t index, const OtherPoint &point) |
| Inserts a vertex at the given index, shifting the later vertices back. | |
| template<std::ranges::input_range Range> requires (!detail::is_point_v<std::remove_cvref_t<Range>>) && std::convertible_to<std::ranges::range_value_t<Range>, PointType> | |
| constexpr void | insert (std::size_t index, Range &&points) |
| Inserts a range of vertices at the given index, shifting the later vertices back. | |
| template<PointConcept OtherPoint> | |
| constexpr void | pushBack (const OtherPoint &point) |
| Appends a vertex, extending the polyline by one edge. | |
| template<std::ranges::input_range Range> requires (!detail::is_point_v<std::remove_cvref_t<Range>>) && std::convertible_to<std::ranges::range_value_t<Range>, PointType> | |
| constexpr void | pushBack (Range &&points) |
| Appends a range of vertices in order. | |
| constexpr auto | begin () const |
| Returns a constant iterator to the first vertex. | |
| constexpr auto | cbegin () const |
| Returns a constant iterator to the first vertex. | |
| constexpr auto | end () const |
| Returns a constant iterator past the last vertex. | |
| constexpr auto | cend () const |
| Returns a constant iterator past the last vertex. | |
| constexpr auto | operator<=> (const Polyline &other) const |
| Compares two polylines by their canonical vertex sequences. | |
| constexpr bool | operator== (const Polyline &other) const |
| Checks equality of two polylines. | |
| 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 polyline. | |
| constexpr bool | empty () const |
| Checks whether the polyline has no vertex. | |
| constexpr bool | isDegenerate () const |
| Checks if the polyline is degenerate (all vertices are equal, so it covers at most a single point). | |
| constexpr bool | isPoint () const |
| Checks whether the polyline covers exactly one point. | |
| constexpr std::optional< PointType > | getIfPoint () const |
| Returns the point the polyline collapses to, if it does. | |
| constexpr bool | isSegment () const |
| Checks whether the polyline covers exactly one segment of positive length. | |
| constexpr std::optional< BoundaryType< false > > | getIfSegment () const |
| Returns the segment the polyline collapses to, if it does. | |
| constexpr bool | isUndefined () const |
| Checks whether the polyline is degenerate without covering a point or a segment. | |
| template<class Rational = pgl::Rational<pgl::BigInt>> | |
| bool | isSimple () const |
| Tests whether the polyline is simple (it does not touch or cross itself). | |
| 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 polyline's vertices. | |
| constexpr const Rectangle< PointType > & | bbox () const |
| Computes the bounding box of the polyline. | |
| 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 polyline contains. | |
| template<std::floating_point ResultNumber = double> | |
| constexpr Rectangle< Point< ResultNumber > > | fbox () const |
| Computes the floating-point bounding box of the polyline. | |
| constexpr std::vector< PointType > | vertices () const |
| Returns the vertices of the polyline (translation applied). | |
| constexpr std::vector< Segment< PointType > > | edges () const |
| Returns the edges of the polyline. | |
| constexpr std::vector< OrientedSegment< PointType > > | orientedEdges () const |
| Returns the oriented edges of the polyline, each directed from vertex i to vertex i + 1 in traversal order. | |
| 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. | |
| 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<MonotoneChainConcept OtherChain> | |
| constexpr bool | contains (const OtherChain &other) const |
| Tests whether this shape contains the other shape (A ⊇ B). | |
| template<PolylineConcept OtherPolyline> | |
| constexpr bool | contains (const OtherPolyline &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<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<PolylineConcept OtherPolyline> | |
| constexpr bool | boundaryContains (const OtherPolyline &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<PolylineConcept OtherPolyline> | |
| constexpr bool | interiorContains (const OtherPolyline &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<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<MonotoneChainConcept OtherChain> | |
| constexpr bool | intersects (const OtherChain &other) const |
| Tests whether this shape and the other shape intersect (A ∩ B ≠ ∅). | |
| template<PolylineConcept OtherPolyline> | |
| constexpr bool | intersects (const OtherPolyline &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<Polyline>) | |
| 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<PolylineConcept OtherPolyline> | |
| constexpr bool | interiorsIntersect (const OtherPolyline &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<Polyline>) | |
| 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 | 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<PolylineConcept OtherPolyline> | |
| constexpr bool | crosses (const OtherPolyline &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<Polyline>) | |
| constexpr bool | crosses (const OtherShape &other) const |
| Tests whether the two shapes mutually separate each other (each disconnects the other). | |
| 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>, 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 with a monotone chain (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline> | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | intersection (const OtherPolyline &other) const |
| Returns the intersection of the two polylines (A ∩ B), a sequence of points and segments sorted by lexicographic order. | |
| template<class ResultNumber = division_result_t<NumberType>, class OtherArea> requires (PolygonConcept<OtherArea> || PolygonWithHolesConcept<OtherArea>) | |
| constexpr std::vector< std::variant< Point< ResultNumber, typename PointType::LabelType >, Segment< Point< ResultNumber, typename PointType::LabelType > > > > | polygonIntersection (const OtherArea &other) const |
| Returns the intersection with a polygon or a region (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<Polyline>) && requires(const OtherShape& o, const Polyline& 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 = 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 = division_result_t<NumberType>, PolylineConcept OtherPolyline> | |
| constexpr auto | squaredDistance (const OtherPolyline &other) const |
| Returns the squared Euclidean distance to the given shape. | |
| template<class ResultNumber = 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<Polyline>) && requires(const OtherShape& o, const Polyline& 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<Polyline<PointType_, TLabel>, OtherShape> | |
| constexpr auto | closestSegments (const OtherShape &other) const |
| Returns the pair of elements realizing the distance, nothing when the shapes meet. | |
| template<class ResultNumber = division_result_t<NumberType>, class OtherShape> requires detail::ClosestPointsPairConcept<Polyline<PointType_, TLabel>, OtherShape> | |
| constexpr auto | closestPoints (const OtherShape &other) const |
| Returns the pair of points realizing the distance, nothing when the shapes meet. | |
| template<class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint> | |
| constexpr auto | distanceL1 (const OtherPoint &point) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment> | |
| constexpr auto | distanceL1 (const OtherSegment &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment> | |
| constexpr auto | distanceL1 (const OtherOrientedSegment &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine> | |
| constexpr auto | distanceL1 (const OtherLine &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine> | |
| constexpr auto | distanceL1 (const OtherOrientedLine &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay> | |
| constexpr auto | distanceL1 (const OtherRay &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane> | |
| constexpr auto | distanceL1 (const OtherHalfplane &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle> | |
| constexpr auto | distanceL1 (const OtherRectangle &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle> | |
| constexpr auto | distanceL1 (const OtherTriangle &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex> | |
| constexpr auto | distanceL1 (const OtherConvex &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, 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>, PolylineConcept OtherPolyline> | |
| constexpr auto | distanceL1 (const OtherPolyline &other) const |
| Returns the Manhattan (L1) distance to the given shape. | |
| template<class ResultNumber = division_result_t<NumberType>, typename OtherShape> requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Polyline>) && requires(const OtherShape& o, const Polyline& 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>, PolylineConcept OtherPolyline> | |
| constexpr auto | distanceLInf (const OtherPolyline &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<Polyline>) && requires(const OtherShape& o, const Polyline& 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 polyline (the sum of its edge lengths). | |
| constexpr auto | lengthL1 () const |
| Computes the Manhattan (L1) length of the polyline. | |
| constexpr auto | lengthLInf () const |
| Computes the Chebyshev (LInf) length of the polyline. | |
| template<class ResultNumber = division_result_t<NumberType>> | |
| constexpr Point< ResultNumber > | pointInside () const |
| Returns a point inside the polyline. | |
| constexpr Polyline | rotated90 (int k=1) const |
| Returns the polyline rotated by 90k degrees around the origin. | |
| constexpr void | rotate90 (int k=1) |
| Rotates the polyline by 90k degrees around the origin in place. | |
| template<class OtherNumber> | |
| constexpr Polyline | scaledUpX (const OtherNumber scalar) const |
| Returns the polyline with its x-coordinates multiplied by a factor. | |
| template<class OtherNumber> | |
| constexpr void | scaleUpX (const OtherNumber scalar) |
| Multiplies the polyline's x-coordinates by a factor in place. | |
| template<class OtherNumber> | |
| constexpr Polyline | scaledUpY (const OtherNumber scalar) const |
| Returns the polyline with its y-coordinates multiplied by a factor. | |
| template<class OtherNumber> | |
| constexpr void | scaleUpY (const OtherNumber scalar) |
| Multiplies the polyline's y-coordinates by a factor in place. | |
| template<class OtherNumber> | |
| constexpr Polyline | scaledDownX (const OtherNumber scalar) const |
| Returns the polyline with its x-coordinates divided by a divisor. | |
| template<class OtherNumber> | |
| constexpr void | scaleDownX (const OtherNumber scalar) |
| Divides the polyline's x-coordinates by a divisor in place. | |
| template<class OtherNumber> | |
| constexpr Polyline | scaledDownY (const OtherNumber scalar) const |
| Returns the polyline with its y-coordinates divided by a divisor. | |
| template<class OtherNumber> | |
| constexpr void | scaleDownY (const OtherNumber scalar) |
| Divides the polyline's y-coordinates by a divisor in place. | |
| template<SegmentConcept OldSegment, SegmentConcept NewSegment> | |
| constexpr bool | flippable (const OldSegment &oldEdge, const NewSegment &newEdge) const |
Tests whether oldEdge can be flipped to newEdge. | |
| template<SegmentConcept OldSegment, SegmentConcept NewSegment> | |
| constexpr Polyline | flipped (const OldSegment &oldEdge, const NewSegment &newEdge) const |
Returns the polyline with oldEdge flipped to newEdge. | |
| template<SegmentConcept OldSegment, SegmentConcept NewSegment> | |
| constexpr void | flip (const OldSegment &oldEdge, const NewSegment &newEdge) |
Flips oldEdge to newEdge in place. | |
| template<class OtherShape> requires MinkowskiSummableConcept<Polyline<PointType_, TLabel>, OtherShape> | |
| constexpr auto | minkowskiSum (const OtherShape &other) const |
| Returns the Minkowski sum of this shape and another (A ⊕ B). | |
| template<class OtherShape> requires MinkowskiSummableConcept<Polyline<PointType_, TLabel>, OtherShape> | |
| constexpr auto | minkowskiErosion (const OtherShape &other) const |
| Returns the Minkowski erosion of this shape by another (A ⊖ B). | |
| template<class ResultNumber = division_result_t<NumberType>, class OtherShape> requires (!MinkowskiSummableConcept<Polyline<PointType_, TLabel>, OtherShape> && BoundedPolygonalConcept<OtherShape>) | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiErosion (const OtherShape &other) const |
| Returns the regularized Minkowski erosion of this shape by a bounded polygonal one (A ⊖ B), as a set of regions. | |
| template<class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherTriangle &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherRectangle &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherConvex &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherPolygon &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherRegion &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherSegment &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherSegment> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherSegment &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B). | |
| template<class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherPolyline &other) const |
| Returns the regularized Minkowski sum of the two chains (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>, PolygonSetConcept OtherSet> | |
| PolygonSet< Point< ResultNumber, typename PointType::LabelType > > | minkowskiSum (const OtherSet &other) const |
| Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions. | |
| template<PointConcept OtherPoint> | |
| constexpr Polyline & | operator+= (const OtherPoint &translation) |
| Translates the polyline by the given point. | |
| template<PointConcept OtherPoint> | |
| constexpr Polyline & | operator-= (const OtherPoint &translation) |
| Translates the polyline by the negation of the given point. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>) | |
| constexpr Polyline & | operator*= (const Scalar &scalar) |
| Scales the polyline by the given scalar. | |
| template<class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>) | |
| constexpr Polyline & | operator/= (const Scalar &scalar) |
| Divides the polyline by the given scalar. | |
| template<class ResultNumber, ConvexConcept OtherConvex> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherConvex &other) const |
| template<class ResultNumber, TriangleConcept OtherTriangle> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherTriangle &other) const |
| template<class ResultNumber, RectangleConcept OtherRectangle> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherRectangle &other) const |
| template<class ResultNumber, PolygonConcept OtherPolygon> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherPolygon &other) const |
| template<class ResultNumber, PolygonWithHolesConcept OtherRegion> | |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherRegion &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, PolylineConcept OtherPolyline> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherPolyline &other) const |
| template<class ResultNumber, MonotoneChainConcept OtherChain> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherChain &other) const |
| template<class ResultNumber, PolygonSetConcept OtherSet> | |
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > | minkowskiSum (const OtherSet &other) const |
| template<class OtherNumber> | |
| constexpr Polyline< PointType, LabelType > | scaledUpX (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr Polyline< PointType, LabelType > | scaledUpY (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr Polyline< PointType, LabelType > | scaledDownX (const OtherNumber scalar) const |
| template<class OtherNumber> | |
| constexpr Polyline< PointType, LabelType > | scaledDownY (const OtherNumber scalar) const |
| template<SegmentConcept OldSegment, SegmentConcept NewSegment> | |
| constexpr Polyline< PointType, LabelType > | flipped (const OldSegment &oldEdge, const NewSegment &newEdge) const |
Open polygonal chain stored in traversal order; may self-intersect.
An open polygonal chain stored by its vertices in traversal order plus a translation.
Polyline mirrors the storage layout of Polygon — a vector of vertices and a translation_ applied lazily on access — but the vertices form an open chain: n vertices are joined by n - 1 edges and there is no closing edge back to the first vertex. Unlike MonotoneChain, the vertices keep the order they were given in, so the chain may bend backwards, revisit points, and self-intersect; isSimple reports whether it does not.
The constructor stores the sequence exactly as given: no vertex is reordered or removed, and the traversal direction is kept, so a polyline built backwards iterates backwards. A polyline traversed backwards is still the same set of points, so operator==/operator<=> and std::hash read the vertices in a canonical direction instead of the stored one, giving Polyline({a, b, c}) == Polyline({c, b, a}) without ever flipping the stored sequence. Repeated vertices are kept as given. A repeated consecutive vertex produces a zero-length edge; like other degenerate inputs in the library, such a polyline is outside the contract of the geometric predicates (isSimple reports false for it, and isDegenerate is true only when all vertices are equal).
As a 1-dimensional manifold with boundary, the polyline's boundary is its two extreme vertices and its relative interior is everything else (matching the convention of Segment and MonotoneChain). Note that for a closed polyline (first vertex equal to the last) this convention still subtracts that vertex from the interior.
| PointType_ | The vertex point type. |
| using pgl::Polyline< PointType_, TLabel >::BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>> |
| using pgl::Polyline< PointType_, TLabel >::EdgeIterator = BoundaryIterator<false> |
| using pgl::Polyline< PointType_, TLabel >::LabelType = TLabel |
| using pgl::Polyline< PointType_, TLabel >::NumberType = PointType::NumberType |
| using pgl::Polyline< PointType_, TLabel >::OrientedEdgeIterator = BoundaryIterator<true> |
| using pgl::Polyline< PointType_, TLabel >::PointType = PointType_ |
|
constexprdefault |
Creates a polyline with no vertex.
|
inlineexplicitconstexpr |
Creates a polyline from a range of points.
The points are linked and stored in the given order: nothing is changed — no sorting, no deduplication, no reversal.
| Range | Input range whose elements can be converted to PointType. |
| points | Range of vertices in traversal order. |
|
inlineexplicitconstexpr |
Creates a polyline 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. The vertices are stored in the given order (see the range constructor).
| coords | Interleaved x/y coordinates of the vertices in traversal order. |
|
inlineconstexpr |
Converts a polyline with compatible vertex type.
The traversal order of the source is preserved.
| OtherPointType | Source vertex type. |
| other | Source polyline. |
|
constexpr |
Computes the bounding box of the polyline.
The result is computed on the first call and cached in bbox_; later calls return the stored value. Any operation that modifies the polyline 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 polyline is its two extreme vertices (matching the endpoint convention of Segment).
Complexity: O(1).
| OtherPoint | Type of the point. |
| point | Point to test. |
Open polygonal chain predicates: the boundary of a polyline 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 is exactly the union of its edges, so this folds the (gap-sweeping) segment containment over them.
|
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(n) for n vertices.
| OtherPoint | Type of the point. |
| point | Point to test. |
Open polygonal chain predicates: the polyline keeps its vertices in traversal order and may self-intersect, so there is no monotone structure to exploit — point location scans the edges and segment containment sweeps the union of collinear edge overlaps.
|
nodiscardconstexpr |
Tests whether this shape contains the other shape (A ⊇ B).
A polygon lies on the 1-dimensional polyline 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).
A polyline contains another polyline exactly when it contains every edge of the other (and its vertex for a degenerate other).
Complexity: O(m n log n) for m vertices of the other polyline.
|
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).
The polyline is the one shape whose complement can come apart, so it does not answer a region by that region's outer polygon: having no area itself, it holds only a region with no area, and then edge by edge. 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 self-intersecting polyline can cover a segment with several, possibly non-consecutive collinear edges, so the segment is contained exactly when the union of its overlaps with the polyline edges covers it with no gap.
Complexity: O(n log n) for n vertices (collecting and sorting the overlaps).
| 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 polyline'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).
|
nodiscardconstexpr |
|
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 polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline.
A polyline with n vertices has n - 1 edges (none for an empty or single-vertex polyline); there is no closing edge back to the first vertex.
|
inlineconstexpr |
Returns an iterator to the first unoriented edge.
|
inlineconstexpr |
Returns an iterator past the last unoriented edge.
|
inlineconstexpr |
|
inlineconstexpr |
Checks whether the polyline has no vertex.
|
inlineconstexpr |
Returns a constant iterator past the last vertex.
|
constexpr |
Computes the floating-point bounding box of the polyline.
| ResultNumber | The floating-point type for the result. |
|
constexpr |
Flips oldEdge to newEdge in place.
See flippable for the exact semantics. The flip must be possible. The label is preserved.
Complexity: O(n) for n vertices.
| OldSegment | Type of the removed edge. |
| NewSegment | Type of the added edge. |
| oldEdge | Edge to remove (an existing polyline edge). |
| newEdge | Edge to add in its place. |
|
nodiscardconstexpr |
Tests whether oldEdge can be flipped to newEdge.
A flip removes one edge and adds one edge so that the result is still a single open chain over the very same vertices (a Hamiltonian path move). Removing an edge splits the chain into two sub-paths A (holding the first vertex) and B (holding the last); the new edge rejoins them and therefore has to connect an endpoint of A to an endpoint of B. With A = [p_0 .. p_i] and B = [p_{i+1} .. p_{n-1}] the three non-trivial reconnections are:
The flip is possible when oldEdge equals some edge of the polyline, newEdge is non-degenerate, and newEdge is one of the reconnections above (in particular newEdge differs from oldEdge — re-adding the removed edge is not a flip). Both edges are compared as unordered vertex pairs. In a self-intersecting polyline oldEdge may match several edges; the first (smallest-index) edge admitting newEdge as a valid reconnection is used.
Complexity: O(n) for n vertices.
| OldSegment | Type of the removed edge. |
| NewSegment | Type of the added edge. |
| oldEdge | Edge to remove (an existing polyline edge). |
| newEdge | Edge to add in its place. |
|
constexpr |
|
nodiscardconstexpr |
Returns the polyline with oldEdge flipped to newEdge.
See flippable for the exact semantics. The flip must be possible.
Complexity: O(n) for n vertices.
| OldSegment | Type of the removed edge. |
| NewSegment | Type of the added edge. |
| oldEdge | Edge to remove (an existing polyline edge). |
| newEdge | Edge to add in its place. |
|
inlineconstexpr |
Accesses a vertex by index modulo the vertex count.
Unlike Polygon the polyline 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 polyline collapses to, if it does.
Complexity: O(n), returning at the first differing vertex.
|
inlinenodiscardconstexpr |
Returns the segment the polyline 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(n) for n vertices (linear scan; the vertices follow the traversal order, not a searchable order).
| point | The vertex to locate. |
|
inlineconstexpr |
Inserts a vertex at the given index, shifting the later vertices back.
The vertex becomes (*this)[index]; passing size() appends. The two edges that met at the old index are replaced by three, so the polyline may stop being simple.
Complexity: O(n) for n vertices.
| OtherPoint | Type of the inserted point. |
| index | Position the new vertex takes, in [0, size()]. |
| point | Vertex to insert. |
|
inlineconstexpr |
Inserts a range of vertices at the given index, shifting the later vertices back.
The range keeps its order: its first point becomes (*this)[index]. Passing size() appends. The points are collected before the insertion, so a range that reads from this polyline (e.g. its own vertices) is safe.
Complexity: O(n + m) for n vertices and m inserted points.
| Range | Input range whose elements can be converted to PointType. |
| index | Position the first new vertex takes, in [0, size()]. |
| points | Vertices to insert, in traversal 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 polyline is the polyline minus its two extreme vertices.
Complexity: O(n) for n vertices.
| OtherPoint | Type of the point. |
| point | Point to test. |
Open polygonal chain predicates. The relative interior of a polyline is the polyline minus its two extreme vertices as a point set: a self-intersecting polyline may pass through an extreme vertex again mid-chain, and that point is still excluded.
|
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(n log n) for n vertices (see contains).
| 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° ≠ ∅).
|
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(n) for n vertices.
Open polygonal chain predicates. The polyline's relative interior is the polyline minus its two extreme points (a self-intersecting polyline may pass through an extreme again mid-chain, and that point is still excluded), so the tests work with closed edges and explicitly discard meeting points that coincide with an excluded extreme or endpoint.
|
nodiscardconstexpr |
Tests whether the interiors of the shapes intersect (A° ∩ B° ≠ ∅).
All-pairs edge test plus the crossing-at-a-non-extreme-vertex checks in both directions.
Complexity: O(n m) for polylines 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° ≠ ∅).
The polyline's relative interior is the polyline minus its extreme vertices, so a polyline 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(n) for n vertices.
| 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 with a monotone chain (A ∩ B), a sequence of points and segments sorted by lexicographic order.
All-pairs edge test, preceded by a bounding-box cull; the pieces are coalesced like intersection(const OtherPolyline&) const.
Complexity: O(n m) for a polyline with n vertices and a chain with m vertices, plus coalescing the resulting pieces.
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 of the two polylines (A ∩ B), a sequence of points and segments sorted by lexicographic order.
Two polylines can overlap along collinear sub-segments, so the result is a vector of point-or-segment variants. Pieces are maximal: collinear touching overlaps are coalesced into single segments — even when they come from non-consecutive edges of a self-intersecting polyline — and points covered by a reported segment or repeated by several edge pairs are dropped. Computed by an all-pairs edge test with a bounding-box cull.
Complexity: O(n m) for polylines with n and m vertices, plus coalescing the resulting pieces (quadratic in their count).
| ResultNumber | Number type of the returned coordinates. |
| OtherPolyline | Type of the other polyline. |
| other | Polyline 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 polyline edges, delegating each edge to the segment-vs-shape intersection, then coalesces the pieces like intersection(const OtherPolyline&) const.
Complexity: O(n) segment intersections for n vertices, plus coalescing the resulting pieces (quadratic in their count).
| 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 ≠ ∅).
Folds the chain's own (pruned) segment test over the polyline edges.
Complexity: O(n (log m + k)) for a polyline with n vertices and a chain with m vertices.
|
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 ≠ ∅).
All-pairs edge test, preceded by a bounding-box cull.
Complexity: O(n m) for polylines with n and m vertices.
| OtherPolyline | Type of the other polyline. |
| other | Polyline 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 ≠ ∅).
Every edge is tested against the segment; a self-intersecting polyline has no monotone structure to prune the scan.
Complexity: O(n) for n vertices.
| 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 ≠ ∅).
|
inlineconstexpr |
Checks if the polyline is degenerate (all vertices are equal, so it covers at most a single point).
An empty or single-vertex polyline is degenerate. Note the contrast with MonotoneChain::isDegenerate: a polyline may repeat one point many times and still be a single geometric point.
Complexity: O(n).
|
inlinenodiscardconstexpr |
Checks whether the polyline covers exactly one point.
Same as isDegenerate except for the empty polyline, which has no defining vertex and so is not a point.
Complexity: O(n), returning at the first differing vertex.
|
inlinenodiscardconstexpr |
Checks whether the polyline covers exactly one segment of positive length.
True when the vertices are collinear but not all equal. The polyline is connected, so collinear vertices make its edges cover the single segment spanning them, however many times they retrace it.
Complexity: O(n), returning at the first non-collinear vertex.
|
nodiscard |
Tests whether the polyline is simple (it does not touch or cross itself).
Tests whether the polyline is simple.
Simple means no two non-adjacent edges share a point and consecutive edges meet only at their shared vertex; in an open chain the first and last edges are not adjacent, so a closed polyline (first vertex equal to the last) is not simple. A zero-length edge (repeated consecutive vertex) also makes the polyline not simple. A polyline with fewer than two vertices is vacuously simple.
Uses a brute-force pairwise edge test in O(n^2) for few edges (n <= 8) or floating-point coordinates, and the Bentley-Ottmann sweep (O(n log n)) for larger exact (integer or rational) polylines.
| Rational | Exact rational type used by the sweep for large polylines. |
Takes the same three paths as Polygon::isSimple, over the chain's edges rather than a ring's: the exact sweep line for integer and rational coordinates, the bounding-box sweep for large floating-point ones, and the pairwise scan for the small ones.
| Rational | Exact rational type used internally by the sweep line. |
|
inlinenodiscardconstexpr |
Checks whether the polyline is degenerate without covering a point or a segment.
True only for the empty polyline, which has no defining vertex: any other degenerate polyline has all vertices equal and is therefore a point.
Complexity: O(1).
|
inlineconstexpr |
Returns the polyline label.
The label is mutable even through a const polyline: it is metadata that does not participate in equality, hashing, or geometric predicates.
|
nodiscard |
Returns the integer points the polyline contains.
The lattice points of the edges, one edge at a time in traversal order, with each point kept the first time the polyline reaches it: a vertex shared by two edges appears once, and so does a point the polyline crosses or retraces. 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::Polyline< PointType, LabelType >::length | ( | ) | const |
Computes the Euclidean length of the polyline (the sum of its edge lengths).
A self-overlapping polyline counts every traversal of a repeated part.
| ApproximateNumber | The floating-point type for the result. |
|
constexpr |
Computes the Manhattan (L1) length of the polyline.
|
constexpr |
Computes the Chebyshev (LInf) length of the polyline.
|
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 polyline 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::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherChain & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two chains (A ⊕ B).
A MonotoneChain operand is a polyline that happens to be sorted, and it sums here exactly as one: its monotonicity buys nothing against a receiver that may bend back on itself. A polyline outranks a chain and so owns the pair, which the chain's own forwarder reaches.
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherConvex & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherOriented & | other | ) | const |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherPolygon & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
The one non-convex summand a chain takes: a Polygon reaches around the chain as readily as the chain bends around it, so here either operand's concavity can strand a cavity, where with a convex summand only the chain's turns can. It is decomposed the way the region-valued sums decompose it — the triangles of its triangulated domain, or its edges when it has no area — while the chain contributes its edges.
Complexity: one convex merge per pair of chain edge and operand triangle, then a constrained triangulation over the arrangement of all of them.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherPolyline< PointType_, TLabel > & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two chains (A ⊕ B).
Two chains, and between them not a scrap of area — and the sum has some anyway, for the reason a segment operand does: an edge of each spans a parallelogram unless the two are parallel. It is the same construction as every other sum here, with both operands contributing their edges as their decomposition, and the same regularized, set-valued contract that minkowskiSum(const OtherSegment&) const has — a segment operand being the one-edge case of this one.
Nothing about a valid pair of chains keeps the answer in one piece, so there is no body here and no precondition to observe: two chains that share a direction sweep out nothing along it, and what is left can be in pieces or empty. Two parallel segments spelled as chains are the smallest example, and they come back empty.
Complexity: one convex merge per pair of edges, then a constrained triangulation over the arrangement of all of them.
| ResultNumber | The number type for the result. |
| other | The chain to sum with. |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherRectangle & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherRegion & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
A region summand brings what it brings to every sum: its holes need no handling, being simply where its decomposition has no piece, while its slits do — a stretch of boundary two of its rings share carries no area beside it and yet sweeps out area along the chain exactly as a triangle does, so it joins the decomposition.
The one case worth knowing is a slit the chain drags along the slit's own direction: that sweep is a segment, so the regularization drops it and the answer is strictly smaller than A ⊕ B. It is the same rule that makes a summand with no area at all come back empty, and it is reachable here from a perfectly ordinary rectilinear region and chain.
That case is also the one that can cost a region its body, which is what this overload's single-region result is contracted on: a slit cutting the operand's interior in two leaves the sum in as many pieces, of which one comes back. A region whose slits leave its interior connected — or that has none — is a body and is on the contract.
Complexity: one convex merge per pair of chain edge and operand piece, then a constrained triangulation over the arrangement of all of them.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherSegment & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
An orientation is not part of a point set, so this is the sum with the underlying segment, vertex for vertex.
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
The one operand here with no area of its own, and the sum still has some: an edge of the chain summed with the segment is the parallelogram they span, which is flat only where the two are parallel. So a chain that bends sweeps a band of material along itself whichever direction the segment points, and that band closes over a cavity exactly as a summand with area does — a closed chain still comes back as a region with a hole.
This is the pair where the regularization is easiest to trip over, because the receiver's own edges are what sweep. An edge parallel to the segment sweeps a segment, which the regularization drops: a straight chain summed along its own direction comes back empty — as does any chain against a summand collapsed to a point — and a closed rectilinear chain summed with an axis-parallel segment comes back as two disjoint regions, the sweeps of the two edges across it, with what joined them dropped. Every one of those is A ⊕ B losing what has no area, not the sum being unsupported.
Complexity: one convex merge per edge of the chain, then a constrained triangulation over the arrangement of all of them.
| PolygonSet< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherSet & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B), as a set of regions.
A PolygonSet operand is the one whose answer needs a set whatever the other operand is: its components are disjoint, and a sum small relative to the gaps between them leaves them so. The set outranks every shape here and owns the pair, so this is the mirror spelling of PolygonSet::minkowskiSum, and the same call.
|
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. |
| PolygonWithHoles< Point< ResultNumber, typename PointType_::LabelType > > pgl::Polyline< PointType_, TLabel >::minkowskiSum | ( | const OtherTriangle & | other | ) | const |
|
nodiscard |
Returns the regularized Minkowski sum of the two shapes (A ⊕ B).
The sum is {p + q : p ∈ A, q ∈ B}, regularized to closure((A ⊕ B)°) and returned as a region with holes. A polyline has no area of its own, but sweeping another shape along it has some: the chain is one-dimensional and may bend back on itself, so the swept material can close over a hole — a closed chain is the plainest example, and an open one whose ends come within the summand's reach of each other does it too — and no other shape in the library can say so.
The operand must be a body — the closure of a connected, non-empty interior — and it is the operand that has to be one, since the receiver never is. A body thickens the whole polyline: the sum covers ⋃_{a ∈ A} (a + B°), which is connected along the chain and open, and the sum is its closure. So the answer is one region. A degenerate operand — a Rectangle collapsed to a segment, say — is not on this contract: the regularization can then leave the sum in pieces, of which one comes back. Sum with a Segment instead for the pair that is contracted for two thin operands and returns every piece. An empty or wholly flat regularized sum is the empty region.
Distinguish this from minkowskiSum(const OtherShape&) const, which sums a Point — a translation, giving back a Polyline — and nothing else: a polyline is not convex, so MinkowskiSummableConcept rejects every other pair. A second Polyline is not an operand.
Complexity: one convex merge per edge of the polyline, then a constrained triangulation over the arrangement of all of them.
| ResultNumber | The number type for the result. |
| other | The shape to sum with. |
ResultNumber only at the end.
|
inlineconstexpr |
Scales the polyline by the given scalar.
Complexity: O(n) for n vertices. The traversal order is preserved, even for a negative factor, which merely reverses the lexicographic order of the extremes.
|
inlineconstexpr |
Translates the polyline by the given point.
Complexity: O(1).
|
inlineconstexpr |
Translates the polyline by the negation of the given point.
Complexity: O(1).
|
inlineconstexpr |
Divides the polyline by the given scalar.
Complexity: O(n) for n vertices; preserves the traversal order like operator*=.
|
inlineconstexpr |
Compares two polylines by their canonical vertex sequences.
The stored direction is irrelevant: each side is read through canonicalAt, so the order is the one induced by the lexicographically smaller of each sequence and its reversal.
Complexity: O(n) for n vertices.
|
inlineconstexpr |
Checks equality of two polylines.
Complexity: O(n) for n vertices.
|
inlineconstexpr |
Accesses a vertex by index (in traversal order).
| index | The index of the vertex. |
|
inlineconstexpr |
Returns the oriented edges of the polyline, each directed from vertex i to vertex i + 1 in traversal order.
|
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 polyline.
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 |
Returns the intersection with a polygon or a region (A ∩ B), a sequence of points and segments sorted by lexicographic order.
The area may be non-convex — and, for a PolygonWithHoles, not simply connected — so its intersection with a single edge can already split into several disjoint pieces; each edge is clipped against the area and the pieces are coalesced like intersection(const OtherPolyline&) const.
Complexity: O(n) area-vs-segment clips for n vertices, plus coalescing the resulting pieces.
| ResultNumber | Number type of the returned coordinates. |
| OtherArea | Type of the polygon or region. |
| other | Polygon or region to intersect with. |
|
inlineconstexpr |
Appends a vertex, extending the polyline by one edge.
Same as insert(size(), point).
Complexity: amortized O(1).
| OtherPoint | Type of the appended point. |
| point | Vertex to append. |
|
inlineconstexpr |
Appends a range of vertices in order.
Same as insert(size(), points).
Complexity: O(m) for m appended points.
| Range | Input range whose elements can be converted to PointType. |
| points | Vertices to append, in traversal order. |
|
constexpr |
Rotates the polyline by 90k degrees around the origin in place.
| k | Number of 90-degree CCW rotations (may be negative). |
|
nodiscardconstexpr |
Returns the polyline rotated by 90k degrees around the origin.
The vertex sequence, including its direction, is preserved (rotation is a rigid motion).
| 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 polyline with its x-coordinates divided by a divisor.
|
constexpr |
|
nodiscardconstexpr |
Returns the polyline with its y-coordinates divided by a divisor.
|
constexpr |
Divides the polyline's x-coordinates by a divisor in place.
|
constexpr |
Divides the polyline's y-coordinates by a divisor in place.
|
constexpr |
|
nodiscardconstexpr |
Returns the polyline with its x-coordinates multiplied by a factor.
|
constexpr |
|
nodiscardconstexpr |
Returns the polyline with its y-coordinates multiplied by a factor.
|
constexpr |
Multiplies the polyline's x-coordinates by a factor in place.
|
constexpr |
Multiplies the polyline'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).
The chain is a 1-dimensional set like the polyline, so its free pieces are joined geometrically (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).
|
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).
|
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).
|
nodiscardconstexpr |
Tests whether removing this shape disconnects the other shape (B∖A is disconnected).
Set semantics: the other polyline's free pieces may reconnect through its own self-intersections, so removing an interior point of a closed polyline does not disconnect it.
Complexity: O((n m)^2) piece tests for polylines with 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).
|
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 the segment minus the polyline has at least two connected components. Because the polyline may self-intersect, the pieces are collected as a set and joined through every shared point that survives the removal (see detail::separates1DSet).
Complexity: O(n^2) exact piece tests 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 |
Replaces the vertex at the given index.
The stored vertices are kept relative to a lazy translation, so the given absolute position has that translation subtracted before it is stored; the rest of the polyline is untouched. Drops the cached bounding box and hash.
Complexity: O(1).
| OtherPoint | Type of the new vertex. |
| index | The index of the vertex to replace. |
| point | The new vertex position. |
|
inlineconstexpr |
Returns the number of vertices in the polyline.
|
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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline edges. The polyline 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 polyline (translation applied).
|
inlineconstexpr |
Returns a lazy view over the vertices, translating each on the fly instead of allocating a vector.
Same traversal-order vertex sequence as vertices(), with no heap allocation. The polyline is itself a vertex range, so this is just begin() and end() packaged as a view for callers that take one.
1.17.0