monotonechain.hpp

Go to the documentation of this file.

#pragma once
 
#include "shape/convex.hpp"
 
#include <algorithm>
#include <vector>
#include <cassert>
#include <compare>
#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <limits>
#include <optional>
#include <ostream>
#include <ranges>
#include <span>
#include <type_traits>
#include <utility>
#include <variant>
 
 
namespace pgl {
 
template <class PointType = Point<>, class Label, class Storage>
struct MonotoneChain;
 
namespace detail {
template <class Storage, class PointType>
concept ownsChainStorage = requires(Storage& s, const PointType& p) {
    s.push_back(p);
};

template <std::ranges::forward_range Range>
constexpr bool allPointsEqual(const Range& points) {
    auto first = std::ranges::begin(points);
    const auto last = std::ranges::end(points);
    if (first == last) {
        return false;
    }
    return std::find_if(std::next(first), last,
                        [&](const auto& p) { return p != *first; }) == last;
}

template <std::ranges::forward_range Range>
constexpr bool pointsSpanSegment(const Range& points) {
    const auto first = std::ranges::begin(points);
    const auto last = std::ranges::end(points);
    if (first == last) {
        return false;
    }
    // Anchor the line on the first point and the first one differing from it.
    const auto second = std::find_if(std::next(first), last,
                                     [&](const auto& p) { return p != *first; });
    if (second == last) {
        return false;  // All equal: a point, not a segment.
    }
    return std::all_of(std::next(second), last,
                       [&](const auto& p) { return collinear(*first, *second, p); });
}

template <class SegmentType, std::ranges::forward_range Range>
constexpr SegmentType spannedSegment(const Range& points) {
    const auto [low, high] = std::ranges::minmax_element(points);
    return SegmentType(*low, *high);
}
}  // namespace detail
 
MonotoneChain() -> MonotoneChain<Point<>, NoLabel>;
 
template <std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>
MonotoneChain(Range&&) -> MonotoneChain<std::remove_cvref_t<std::ranges::range_value_t<Range>>, NoLabel>;
 
template <std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>
MonotoneChain(Range&&, bool) -> MonotoneChain<std::remove_cvref_t<std::ranges::range_value_t<Range>>, NoLabel>;
 
template <class Number>
requires (!detail::is_point_v<Number>)
MonotoneChain(std::initializer_list<Number>) -> MonotoneChain<Point<Number>, NoLabel>;
 
template <class Number>
requires (!detail::is_point_v<Number>)
MonotoneChain(std::initializer_list<Number>, bool) -> MonotoneChain<Point<Number>, NoLabel>;
 

template <class PointType_, class TLabel, class Storage>
struct MonotoneChain {
    using PointType = PointType_;
    using NumberType = PointType::NumberType;
    using LabelType = TLabel;
    using StorageType = Storage;
    // The owning counterpart of this chain: the same vertex and label type
    // backed by an owned vector. Value-returning transformations produce this
    // type so that even a view (which cannot own vertices) yields a real chain.
    using OwningChain = MonotoneChain<PointType_, TLabel, std::vector<PointType_>>;
    static_assert(detail::is_point_v<PointType>, "MonotoneChain requires pgl::Point vertices");
 
    template <bool Oriented>
    using BoundaryType = std::conditional_t<Oriented, OrientedSegment<PointType>, Segment<PointType>>;
 
    template <bool Oriented>
    class BoundaryIterator;
 
    using EdgeIterator = BoundaryIterator<false>;
    using OrientedEdgeIterator = BoundaryIterator<true>;

    constexpr MonotoneChain() = default;

    template<std::ranges::input_range Range = std::initializer_list<PointType>>
    requires std::ranges::common_range<Range> &&
             std::convertible_to<std::ranges::range_value_t<Range>, PointType> &&
             detail::ownsChainStorage<Storage, PointType>
    constexpr explicit MonotoneChain(Range&& points, bool trusted = false) {
        for (const auto& p : points) {
            points_.push_back(p);
        }
        if (!trusted) {
            normalize();
        }
        assert(std::is_sorted(points_.begin(), points_.end()) &&
               std::adjacent_find(points_.begin(), points_.end()) == points_.end());
    }

    template<std::ranges::contiguous_range Range>
    requires (!detail::ownsChainStorage<Storage, PointType>) &&
             std::constructible_from<Storage, Range&&>
    constexpr explicit MonotoneChain(Range&& points, bool /*trusted*/ = true)
        : points_(std::forward<Range>(points)) {
        assert(std::is_sorted(points_.begin(), points_.end()) &&
               std::adjacent_find(points_.begin(), points_.end()) == points_.end());
    }

    constexpr explicit MonotoneChain(std::initializer_list<NumberType> coords, bool trusted = false)
        requires detail::ownsChainStorage<Storage, PointType>
    {
        assert(coords.size() % 2 == 0);
        points_.reserve(coords.size() / 2);
        for (auto it = coords.begin(); it != coords.end(); ) {
            NumberType x = *it++;
            NumberType y = *it++;
            points_.emplace_back(x, y);
        }
        if (!trusted) {
            normalize();
        }
        assert(std::is_sorted(points_.begin(), points_.end()) &&
               std::adjacent_find(points_.begin(), points_.end()) == points_.end());
    }

    template<PointConcept OtherPointType, class OtherLabelType, class OtherStorage>
        requires(std::constructible_from<PointType, const OtherPointType&> &&
                 detail::ownsChainStorage<Storage, PointType>)
    constexpr MonotoneChain(const MonotoneChain<OtherPointType, OtherLabelType, OtherStorage>& other)
        : points_(other.begin(), other.end()), label_(detail::copyLabel<LabelType>(other)) {}

    template <class A = LabelType>
        requires(detail::has_label_v<A>)
    constexpr A& label() const {
        return label_;
    }

    constexpr const PointType operator[](std::size_t index) const {
        assert(index < size());
        return points_[index] + translation_;
    }

    constexpr PointType get(std::ptrdiff_t index) const {
        const std::ptrdiff_t n = static_cast<std::ptrdiff_t>(size());
        return (*this)[static_cast<std::size_t>(((index % n) + n) % n)];
    }

    constexpr std::ptrdiff_t index(const PointType& point) const {
        const PointType query = point - translation_;
        const auto it = std::lower_bound(points_.begin(), points_.end(), query);
        if (it != points_.end() && *it == query) {
            return it - points_.begin();
        }
        return -1;
    }

    constexpr auto begin() const {
        return Iterator(points_.begin(), translation_);
    }

    constexpr auto cbegin() const {
        return Iterator(std::ranges::begin(points_), translation_);
    }

    constexpr auto end() const {
        return Iterator(points_.end(), translation_);
    }

    constexpr auto cend() const {
        return Iterator(std::ranges::end(points_), translation_);
    }

    template <class OtherStorage>
    constexpr auto operator<=>(const MonotoneChain<PointType_, TLabel, OtherStorage>& other) const {
        if (auto cmp = size() <=> other.size(); cmp != 0) {
            return cmp;
        }
        for (std::size_t i = 0; i < size(); ++i) {
            if (auto cmp = (*this)[i] <=> other[i]; cmp != 0) {
                return cmp;
            }
        }
        return std::strong_ordering::equal;
    }

    template <class OtherStorage>
    constexpr bool operator==(const MonotoneChain<PointType_, TLabel, OtherStorage>& other) const {
        if (size() != other.size()) {
            return false;
        }
        for (std::size_t i = 0; i < size(); ++i) {
            if ((*this)[i] != other[i]) {
                return false;
            }
        }
        return true;
    }

    template<AnyShapeConcept OtherShape>
    [[nodiscard]] constexpr bool samePointSet(const OtherShape& other) const;

    constexpr std::size_t size() const {
        return points_.size();
    }

    constexpr bool empty() const {
        return points_.empty();
    }

    constexpr bool isDegenerate() const {
        return points_.size() < 2;
    }

    [[nodiscard]] constexpr bool isPoint() const {
        return detail::allPointsEqual(points_);
    }

    [[nodiscard]] constexpr std::optional<PointType> getIfPoint() const {
        if (!isPoint()) {
            return std::nullopt;
        }
        return points_.front() + translation_;
    }

    [[nodiscard]] constexpr bool isSegment() const {
        return detail::pointsSpanSegment(points_);
    }

    [[nodiscard]] constexpr std::optional<BoundaryType<false>> getIfSegment() const {
        if (!isSegment()) {
            return std::nullopt;
        }
        return detail::spannedSegment<BoundaryType<false>>(points_) + translation_;
    }

    [[nodiscard]] constexpr bool isUndefined() const {
        return empty();
    }

    [[nodiscard]] constexpr bool isStrictlyMonotone() const {
        for (std::size_t i = 1; i < points_.size(); ++i) {
            if (points_[i - 1].x() == points_[i].x()) {
                return false;
            }
        }
        return true;
    }

    constexpr Segment<PointType> diameter() const {
        return Convex<PointType>(vertices()).diameter();
    }

    constexpr Convex<PointType> convexHull() const {
        return Convex<PointType>(vertices());
    }

    constexpr const Rectangle<PointType>& bbox() const;

    template <class ResultNumber = grid_number_t<typename PointType_::NumberType>>
        requires(detail::extended_integral<ResultNumber> || std::same_as<ResultNumber, BigInt>)
    [[nodiscard]] std::vector<Point<ResultNumber, typename PointType::LabelType>>
    latticePoints() const;

    template <std::floating_point ResultNumber = double>
    constexpr Rectangle<Point<ResultNumber>> fbox() const;

    constexpr std::vector<PointType> vertices() const {
        std::vector<PointType> ret(points_.begin(), points_.end());
        for (auto& vertex : ret) {
            vertex += translation_;
        }
        return ret;
    }

    [[nodiscard]] constexpr Polyline<PointType> asPolyline() const;

    constexpr std::vector<Segment<PointType>> edges() const {
        std::vector<Segment<PointType>> result;
        const auto translatedVertices = vertices();
        for (std::size_t i = 0; i + 1 < translatedVertices.size(); ++i) {
            result.emplace_back(translatedVertices[i], translatedVertices[i + 1]);
        }
        return result;
    }

    constexpr std::vector<OrientedSegment<PointType>> orientedEdges() const {
        std::vector<OrientedSegment<PointType>> result;
        const auto translatedVertices = vertices();
        for (std::size_t i = 0; i + 1 < translatedVertices.size(); ++i) {
            result.emplace_back(translatedVertices[i], translatedVertices[i + 1]);
        }
        return result;
    }

    constexpr auto verticesView() const {
        return std::ranges::subrange(begin(), end());
    }

    constexpr auto edgesView() const {
        return std::ranges::subrange(edgesBegin(), edgesEnd());
    }

    constexpr auto orientedEdgesView() const {
        return std::ranges::subrange(orientedEdgesBegin(), orientedEdgesEnd());
    }

    constexpr EdgeIterator edgesBegin() const {
        return EdgeIterator(this, 0);
    }

    constexpr EdgeIterator edgesEnd() const {
        return EdgeIterator(this, edgeCount());
    }

    constexpr OrientedEdgeIterator orientedEdgesBegin() const {
        return OrientedEdgeIterator(this, 0);
    }

    constexpr OrientedEdgeIterator orientedEdgesEnd() const {
        return OrientedEdgeIterator(this, edgeCount());
    }

    constexpr void insert(const PointType& point)
        requires detail::ownsChainStorage<Storage, PointType>
    {
        const PointType query = point - translation_;
        const auto it = std::lower_bound(points_.begin(), points_.end(), query);
        if (it != points_.end() && *it == query) {
            return;
        }
        points_.insert(it, query);
        resetCache();
    }

    template<std::ranges::input_range Range>
    requires std::ranges::common_range<Range> &&
             std::convertible_to<std::ranges::range_value_t<Range>, PointType> &&
             detail::ownsChainStorage<Storage, PointType>
    constexpr void insert(Range&& points) {
        const std::size_t oldSize = points_.size();
        for (const auto& p : points) {
            points_.push_back(PointType(p) - translation_);
        }
        if (points_.size() == oldSize) {
            return;
        }
        std::sort(points_.begin() + static_cast<std::ptrdiff_t>(oldSize), points_.end());
        std::inplace_merge(points_.begin(), points_.begin() + static_cast<std::ptrdiff_t>(oldSize), points_.end());
        points_.erase(std::unique(points_.begin(), points_.end()), points_.end());
        resetCache();
    }

    constexpr void erase(std::size_t index)
        requires detail::ownsChainStorage<Storage, PointType>
    {
        assert(index < size());
        points_.erase(points_.begin() + static_cast<std::ptrdiff_t>(index));
        resetCache();
    }

    constexpr bool erase(const PointType& point)
        requires detail::ownsChainStorage<Storage, PointType>
    {
        const PointType query = point - translation_;
        const auto it = std::lower_bound(points_.begin(), points_.end(), query);
        if (it == points_.end() || *it != query) {
            return false;
        }
        points_.erase(it);
        resetCache();
        return true;
    }

    template <class OtherNumber>
    [[nodiscard]] constexpr std::optional<std::size_t> indexAtX(const OtherNumber& x) const;

    template <class ResultNumber = division_result_t<NumberType>, class OtherNumber>
    [[nodiscard]] constexpr std::optional<ResultNumber> yAtX(const OtherNumber& x) const;

    template <PointConcept OtherPoint>
    [[nodiscard]] constexpr std::optional<std::size_t> isStrictlyBelow(const OtherPoint& point) const;

    template <PointConcept OtherPoint>
    [[nodiscard]] constexpr std::optional<std::size_t> isStrictlyAbove(const OtherPoint& point) const;
 

    template <PointConcept OtherPoint>
    [[nodiscard]] constexpr std::optional<std::size_t> isBelow(const OtherPoint& point) const;

    template <PointConcept OtherPoint>
    [[nodiscard]] constexpr std::optional<std::size_t> isAbove(const OtherPoint& point) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool contains(const OtherPoint& point) const;

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool contains(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool contains(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool contains(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool contains(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool contains(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool contains(const OtherHalfplane& other) const;

    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool contains(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool contains(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool contains(const OtherConvex& other) const;

    template<PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr bool contains(const OtherPolygon& other) const;

    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool contains(const OtherDisk& other) const;

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool contains(const EmptyShape<EmptyPoint>&) const {
        return true;
    }

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool contains(const OtherChain& other) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool contains(const Shape<OtherPoint>& other) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool boundaryContains(const OtherPoint& point) const;
 
    // The boundary of a chain is exactly its two extreme vertices, a finite
    // point set, so it contains no positive-length or two-dimensional shape.
    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool boundaryContains(const OtherSegment& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool boundaryContains(const OtherOrientedSegment& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool boundaryContains(const OtherLine&) const { return false; }
    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool boundaryContains(const OtherOrientedLine&) const { return false; }
    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool boundaryContains(const OtherRay&) const { return false; }
    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool boundaryContains(const OtherHalfplane&) const { return false; }
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool boundaryContains(const OtherRectangle& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool boundaryContains(const OtherTriangle& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool boundaryContains(const OtherConvex& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr bool boundaryContains(const OtherPolygon& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool boundaryContains(const OtherDisk& other) const {
        return detail::reduceDegenerateToPoint(
            other, [this](const auto& vertex) { return this->boundaryContains(vertex); });
    }

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool boundaryContains(const OtherChain& other) const {
        // The boundary is the two extreme vertices, so only a chain without an
        // edge fits inside it.
        return other.empty() || (other.size() == 1 && boundaryContains(other[0]));
    }

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool boundaryContains(const EmptyShape<EmptyPoint>&) const {
        return true;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool boundaryContains(const Shape<OtherPoint>& other) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool interiorContains(const OtherPoint& point) const;

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool interiorContains(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool interiorContains(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool interiorContains(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool interiorContains(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool interiorContains(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool interiorContains(const OtherHalfplane& other) const;

    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool interiorContains(const OtherTriangle& other) const;
 
    // A chain is one-dimensional: its relative interior cannot contain any
    // unbounded or two-dimensional shape.
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool interiorContains(const OtherRectangle& other) const {
        return detail::reduceDegenerateGuarded(
            other, [this](const auto& carrier) { return this->interiorContains(carrier); });
    }

    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool interiorContains(const OtherConvex& other) const {
        return detail::reduceDegenerateGuarded(
            other, [this](const auto& carrier) { return this->interiorContains(carrier); });
    }

    template<PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr bool interiorContains(const OtherPolygon& other) const {
        return detail::reduceDegenerate(
            other, [this](const auto& carrier) { return this->interiorContains(carrier); });
    }

    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool interiorContains(const OtherDisk& other) const {
        return detail::reduceDegenerate(
            other, [this](const auto& carrier) { return this->interiorContains(carrier); });
    }

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool interiorContains(const OtherChain& other) const;
    template <class EmptyPoint>
    [[nodiscard]] constexpr bool interiorContains(const EmptyShape<EmptyPoint>&) const {
        return true;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool interiorContains(const Shape<OtherPoint>& other) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool intersects(const OtherPoint& other) const;

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool intersects(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool intersects(const OtherOrientedSegment& other) const;

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool intersects(const OtherChain& other) const;

    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool intersects(const OtherLine& other) const;
    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool intersects(const OtherOrientedLine& other) const;
    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool intersects(const OtherRay& other) const;
    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool intersects(const OtherHalfplane& other) const;
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool intersects(const OtherRectangle& other) const;
    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool intersects(const OtherTriangle& other) const;
    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool intersects(const OtherConvex& other) const;
    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool intersects(const OtherDisk& other) const;

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool intersects(const EmptyShape<EmptyPoint>&) const {
        return false;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool intersects(const Shape<OtherPoint>& other) const;

    template<typename OtherShape>
        requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
    [[nodiscard]] constexpr bool intersects(const OtherShape& other) const {
        return other.intersects(*this);
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherPoint& other) const;

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherLine& other) const;
    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherOrientedLine& other) const;
    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherRay& other) const;
    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherHalfplane& other) const;
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherRectangle& other) const;
    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherTriangle& other) const;
    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherConvex& other) const;
    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherDisk& other) const;
    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherChain& other) const;

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool interiorsIntersect(const EmptyShape<EmptyPoint>&) const {
        return false;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool interiorsIntersect(const Shape<OtherPoint>& other) const;

    template<typename OtherShape>
        requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherShape& other) const {
        return other.interiorsIntersect(*this);
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool separates(const OtherPoint&) const {
        return false;
    }

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool separates(const OtherSegment& other) const;
    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool separates(const OtherOrientedSegment& other) const;
    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool separates(const OtherLine& other) const;
    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool separates(const OtherOrientedLine& other) const;
    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool separates(const OtherRay& other) const;
 
    // --- 2-dimensional targets: the crosscut scan of separatesTwoDimensional
    // (an edge disconnects the region by itself, or the chain runs
    // outside-interior-outside) ---
    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool separates(const OtherHalfplane& other) const;
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool separates(const OtherRectangle& other) const;
    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool separates(const OtherTriangle& other) const;
    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool separates(const OtherDisk& other) const;
    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool separates(const OtherConvex& other) const;
    template<PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr bool separates(const OtherPolygon& other) const;
    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool separates(const OtherChain& other) const;

    template<PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr bool contains(const OtherPolyline& other) const;

    template<PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr bool boundaryContains(const OtherPolyline& other) const {
        // The boundary is the two extreme vertices, so only a polyline
        // covering at most one point fits inside it.
        return other.empty() || (other.isDegenerate() && boundaryContains(other[0]));
    }

    template<PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr bool interiorContains(const OtherPolyline& other) const;

    template<PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr bool separates(const OtherPolyline& other) const;

    template<HalfplaneIntersectionConcept OtherRegion>
    [[nodiscard]] constexpr bool contains(const OtherRegion& other) const;

    template<HalfplaneIntersectionConcept OtherRegion>
    [[nodiscard]] constexpr bool boundaryContains(const OtherRegion& other) const;

    template<HalfplaneIntersectionConcept OtherRegion>
    [[nodiscard]] constexpr bool interiorContains(const OtherRegion& other) const;

    template<HalfplaneIntersectionConcept OtherRegion>
    [[nodiscard]] constexpr bool separates(const OtherRegion& other) const;

    template<PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr bool contains(const OtherRegion& other) const;

    template<PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr bool boundaryContains(const OtherRegion& other) const;

    template<PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr bool interiorContains(const OtherRegion& other) const;

    template<PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] bool separates(const OtherRegion& other) const;
 
    // -------------------------------------------------------------------------
    // A set of regions
    //
    // It outranks every other shape, so the symmetric relations reach it through
    // the rank-based forwarders and only the asymmetric ones are answered here.
    // A set is the union of its components, so it is contained exactly when
    // every component is — no matter what this shape is.

    template<PolygonSetConcept OtherSet>
    [[nodiscard]] constexpr bool contains(const OtherSet& other) const {
        for (const auto& component : other) {
            if (!contains(component)) {
                return false;
            }
        }
        return true;
    }

    template<PolygonSetConcept OtherSet>
    [[nodiscard]] constexpr bool boundaryContains(const OtherSet& other) const {
        for (const auto& component : other) {
            if (!boundaryContains(component)) {
                return false;
            }
        }
        return true;
    }

    template<PolygonSetConcept OtherSet>
    [[nodiscard]] constexpr bool interiorContains(const OtherSet& other) const {
        for (const auto& component : other) {
            if (!interiorContains(component)) {
                return false;
            }
        }
        return true;
    }

    template<PolygonSetConcept OtherSet>
    [[nodiscard]] bool separates(const OtherSet& other) const;

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool separates(const EmptyShape<EmptyPoint>&) const {
        return false;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool separates(const Shape<OtherPoint>& other) const;

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool crosses(const OtherPoint&) const {
        return false;
    }

    template<SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool crosses(const OtherSegment& other) const;
    template<OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool crosses(const OtherOrientedSegment& other) const;
    template<LineConcept OtherLine>
    [[nodiscard]] constexpr bool crosses(const OtherLine& other) const;
    template<OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr bool crosses(const OtherOrientedLine& other) const;
    template<RayConcept OtherRay>
    [[nodiscard]] constexpr bool crosses(const OtherRay& other) const;
    template<HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool crosses(const OtherHalfplane& other) const;
    template<RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr bool crosses(const OtherRectangle& other) const;
    template<TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr bool crosses(const OtherTriangle& other) const;
    template<DiskConcept OtherDisk>
    [[nodiscard]] constexpr bool crosses(const OtherDisk& other) const;
    template<ConvexConcept OtherConvex>
    [[nodiscard]] constexpr bool crosses(const OtherConvex& other) const;
    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool crosses(const OtherChain& other) const;
    template <class EmptyPoint>
    [[nodiscard]] constexpr bool crosses(const EmptyShape<EmptyPoint>&) const {
        return false;
    }

    template<PointConcept OtherPoint>
    [[nodiscard]] constexpr bool crosses(const Shape<OtherPoint>& other) const;
    template<typename OtherShape>
        requires (!PointConcept<OtherShape> && detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
    [[nodiscard]] constexpr bool crosses(const OtherShape& other) const {
        return other.crosses(*this);
    }

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool edgesCross(const OtherChain& other) const;

    template <class ResultNumber = NumberType, PointConcept OtherPoint>
    [[nodiscard]] constexpr std::optional<Point<ResultNumber, typename PointType::LabelType>>
    intersection(const OtherPoint& other) const;

    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherOrientedSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherOrientedLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherRay& other) const;
    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherHalfplane& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherRectangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherTriangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherConvex& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires (!PointConcept<OtherShape>
                  && (detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
                  && requires(const OtherShape& o, const MonotoneChain& self) {
                         o.template intersection<ResultNumber>(self);
                     })
    [[nodiscard]] constexpr auto intersection(const OtherShape& other) const {
        return other.template intersection<ResultNumber>(*this);
    }

    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                                     Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherChain& other) const;

    template <class ResultNumber = NumberType, class EmptyPoint>
    [[nodiscard]] constexpr EmptyShape<EmptyPoint> intersection(const EmptyShape<EmptyPoint>&) const {
        return {};
    }

    template <class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto squaredDistance(const OtherPoint& point) const;
    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto squaredDistance(const OtherSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto squaredDistance(const OtherOrientedSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
    [[nodiscard]] constexpr auto squaredDistance(const OtherLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr auto squaredDistance(const OtherOrientedLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
    [[nodiscard]] constexpr auto squaredDistance(const OtherRay& other) const;
    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr auto squaredDistance(const OtherHalfplane& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto squaredDistance(const OtherRectangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto squaredDistance(const OtherTriangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto squaredDistance(const OtherConvex& other) const;
    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr auto squaredDistance(const OtherChain& other) const;

    template <class ResultNumber = double, class DiskPointType, class DiskLabel>
    [[nodiscard]] detail::floating_result_t<ResultNumber> squaredDistance(
        const Disk<DiskPointType, DiskLabel>& disk) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
                  && requires(const OtherShape& o, const MonotoneChain& self) {
                         o.template squaredDistance<ResultNumber>(self);
                     })
    [[nodiscard]] constexpr auto squaredDistance(const OtherShape& other) const {
        return other.template squaredDistance<ResultNumber>(*this);
    }

    template <class ResultNumber = NumberType, BoundedPolygonalConcept OtherShape>
        requires detail::ClosestPairConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape>
    [[nodiscard]] constexpr auto closestSegments(const OtherShape& other) const;

    template <class ResultNumber = division_result_t<NumberType>, class OtherShape>
        requires detail::ClosestPointsPairConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape>
    [[nodiscard]] constexpr auto closestPoints(const OtherShape& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto distanceL1(const OtherPoint& point) const;
    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto distanceL1(const OtherSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto distanceL1(const OtherOrientedSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
    [[nodiscard]] constexpr auto distanceL1(const OtherLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr auto distanceL1(const OtherOrientedLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
    [[nodiscard]] constexpr auto distanceL1(const OtherRay& other) const;
    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr auto distanceL1(const OtherHalfplane& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto distanceL1(const OtherRectangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto distanceL1(const OtherTriangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto distanceL1(const OtherConvex& other) const;
    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr auto distanceL1(const OtherChain& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
                  && requires(const OtherShape& o, const MonotoneChain& self) {
                         o.template distanceL1<ResultNumber>(self);
                     })
    [[nodiscard]] constexpr auto distanceL1(const OtherShape& other) const {
        return other.template distanceL1<ResultNumber>(*this);
    }

    template <class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto intersection(const Shape<OtherPoint>& other) const {
        return other.template intersection<ResultNumber>(*this);
    }

    template <class ResultNumber = double, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto distanceL1(const Shape<OtherPoint>& other) const {
        return other.template distanceL1<ResultNumber>(*this);
    }

    template <class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto distanceLInf(const OtherPoint& point) const;
    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto distanceLInf(const OtherSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto distanceLInf(const OtherOrientedSegment& other) const;
    template <class ResultNumber = division_result_t<NumberType>, LineConcept OtherLine>
    [[nodiscard]] constexpr auto distanceLInf(const OtherLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, OrientedLineConcept OtherOrientedLine>
    [[nodiscard]] constexpr auto distanceLInf(const OtherOrientedLine& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RayConcept OtherRay>
    [[nodiscard]] constexpr auto distanceLInf(const OtherRay& other) const;
    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr auto distanceLInf(const OtherHalfplane& other) const;
    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto distanceLInf(const OtherRectangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto distanceLInf(const OtherTriangle& other) const;
    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto distanceLInf(const OtherConvex& other) const;
    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr auto distanceLInf(const OtherChain& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<MonotoneChain>)
                  && requires(const OtherShape& o, const MonotoneChain& self) {
                         o.template distanceLInf<ResultNumber>(self);
                     })
    [[nodiscard]] constexpr auto distanceLInf(const OtherShape& other) const {
        return other.template distanceLInf<ResultNumber>(*this);
    }

    template <class ResultNumber = double, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto distanceLInf(const Shape<OtherPoint>& other) const {
        return other.template distanceLInf<ResultNumber>(*this);
    }

    template <class ApproximateNumber = double>
    ApproximateNumber length() const;

    constexpr auto lengthL1() const;

    constexpr auto lengthLInf() const;

    template <class ResultNumber = division_result_t<NumberType>>
    [[nodiscard]] constexpr Point<ResultNumber> pointInside() const;

    template <class OtherShape>
    [[nodiscard]] constexpr bool pointInsideInteriorContainedIn(const OtherShape& shape) const;

    [[nodiscard]] constexpr OwningChain rotated90(int k = 1) const;

    constexpr void rotate90(int k = 1)
        requires detail::ownsChainStorage<Storage, PointType>;

    template <class OtherNumber>
    [[nodiscard]] constexpr OwningChain scaledUpX(const OtherNumber scalar) const;

    template <class OtherNumber>
    constexpr void scaleUpX(const OtherNumber scalar)
        requires detail::ownsChainStorage<Storage, PointType>;

    template <class OtherNumber>
    [[nodiscard]] constexpr OwningChain scaledUpY(const OtherNumber scalar) const;

    template <class OtherNumber>
    constexpr void scaleUpY(const OtherNumber scalar)
        requires detail::ownsChainStorage<Storage, PointType>;

    template <class OtherNumber>
    [[nodiscard]] constexpr OwningChain scaledDownX(const OtherNumber scalar) const;

    template <class OtherNumber>
    constexpr void scaleDownX(const OtherNumber scalar)
        requires detail::ownsChainStorage<Storage, PointType>;

    template <class OtherNumber>
    [[nodiscard]] constexpr OwningChain scaledDownY(const OtherNumber scalar) const;

    template <class OtherNumber>
    constexpr void scaleDownY(const OtherNumber scalar)
        requires detail::ownsChainStorage<Storage, PointType>;

    template <class OtherShape>
        requires MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape>
    [[nodiscard]] constexpr auto minkowskiSum(const OtherShape& other) const;

    template <class OtherShape>
        requires MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape>
    [[nodiscard]] constexpr auto minkowskiErosion(const OtherShape& other) const;

    template <class ResultNumber = division_result_t<NumberType>, class OtherShape>
        requires (!MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape> &&
                  BoundedPolygonalConcept<OtherShape>)
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>
    minkowskiErosion(const OtherShape& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] Polygon<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherConvex& other) const;

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] Polygon<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] Polygon<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherRectangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOriented>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherOriented& other) const;

    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    minkowskiSum(const OtherChain& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires(!MinkowskiSummableConcept<MonotoneChain<PointType_, TLabel, Storage>, OtherShape>
                 && (detail::shapeRank<OtherShape> >
                     detail::shapeRank<MonotoneChain<PointType_, TLabel, Storage>>)
                 && requires(const OtherShape& o, const MonotoneChain& self) {
                        o.template minkowskiSum<ResultNumber>(self);
                    })
    [[nodiscard]] auto minkowskiSum(const OtherShape& other) const {
        return other.template minkowskiSum<ResultNumber>(*this);
    }

    template<PointConcept OtherPoint>
    constexpr MonotoneChain& operator+=(const OtherPoint& translation) {
        translation_ += translation;
        // A pure translation merely shifts the bounding box, so update the
        // cached bbox in place rather than discarding it. The hash, however,
        // depends on the absolute vertex positions, so it must be invalidated.
        if (!bbox_.empty()) {
            bbox_ += translation;
        }
        hash_ = hashUnset_;
        return *this;
    }

    template<PointConcept OtherPoint>
    constexpr MonotoneChain& operator-=(const OtherPoint& translation) {
        translation_ -= translation;
        if (!bbox_.empty()) {
            bbox_ -= translation;
        }
        hash_ = hashUnset_;
        return *this;
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar> &&
                 detail::ownsChainStorage<Storage, PointType>)
    constexpr MonotoneChain& operator*=(const Scalar& scalar) {
        for (auto& vertex : points_) {
            vertex *= scalar;
        }
        translation_ *= scalar;
        normalize();
        resetCache();
        return *this;
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar> &&
                 detail::ownsChainStorage<Storage, PointType>)
    constexpr MonotoneChain& operator/=(const Scalar& scalar) {
        for (auto& vertex : points_) {
            vertex /= scalar;
        }
        translation_ /= scalar;
        normalize();
        resetCache();
        return *this;
    }

    template <bool Oriented>
    class BoundaryIterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using iterator_concept = std::forward_iterator_tag;
        using value_type = BoundaryType<Oriented>;
        using difference_type = std::ptrdiff_t;
        using reference = value_type;
 
        constexpr BoundaryIterator() = default;
 
        constexpr value_type operator*() const {
            assert(chain != nullptr);
            return chain->template boundaryAt<Oriented>(index);
        }
 
        constexpr BoundaryIterator& operator++() {
            ++index;
            return *this;
        }
 
        constexpr BoundaryIterator operator++(int) {
            BoundaryIterator copy(*this);
            ++(*this);
            return copy;
        }
 
        constexpr bool operator==(const BoundaryIterator& other) const = default;
 
      private:
        friend struct MonotoneChain;
 
        constexpr BoundaryIterator(const MonotoneChain* chain_arg, std::size_t index_arg)
            : chain(chain_arg), index(index_arg) {}
 
        const MonotoneChain* chain = nullptr;
        std::size_t index = 0;
    };
 
  private:
    Storage points_{};
    [[no_unique_address]] mutable LabelType label_{};
    PointType translation_{};
    // Lazily computed bounding box, invalidated by resetCache() on every
    // mutation. The empty rectangle doubles as "not computed yet": a shape
    // whose box is genuinely empty has no vertices, so bbox() re-derives it
    // with one size check rather than any real work.
    mutable Rectangle<PointType> bbox_{};
 
    // Memoized hash, computed lazily by std::hash<MonotoneChain>. hashUnset_
    // means "not yet computed"; SIZE_MAX is chosen as the sentinel because it
    // is a rare hash output, and the one true hash that would collide with it
    // is remapped to hashUnset_ - 1 so the sentinel is never stored as a real
    // value. Unlike the bbox, the hash is not translation-invariant, so
    // operator+=/-= reset it.
    static constexpr std::size_t hashUnset_ = pgl::detail::numeric_limits<std::size_t>::max();
    mutable std::size_t hash_ = hashUnset_;
    friend struct std::hash<MonotoneChain>;
 
    // Drops the memoized caches; call after any operation that mutates the
    // chain's vertices. A pure translation does not need to drop bbox_ (it
    // shifts in place, see operator+=), but it must still reset hash_, which
    // depends on the absolute vertex positions.
    constexpr void resetCache() const {
        bbox_ = {};
        hash_ = hashUnset_;
    }
 
    constexpr std::size_t edgeCount() const {
        return points_.empty() ? 0 : points_.size() - 1;
    }

    template <class LowNumber, class HighNumber>
    [[nodiscard]] constexpr std::optional<std::pair<std::size_t, std::size_t>>
    edgeWindow(const LowNumber& xlo, const HighNumber& xhi) const;

    template <class ResultNumber, class OtherShape>
    constexpr ResultNumber edgeMinSquaredDistance(const OtherShape& other) const;

    template <class ResultNumber, class OtherShape>
    constexpr ResultNumber edgeMinDistanceL1(const OtherShape& other) const;

    template <class ResultNumber, class OtherShape>
    constexpr ResultNumber edgeMinDistanceLInf(const OtherShape& other) const;

    template <class ResultNumber, class OtherShape>
    constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                       Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    edgeFoldIntersection(const OtherShape& other) const;

    template <class ResultNumber>
    static constexpr std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                              Segment<Point<ResultNumber, typename PointType::LabelType>>>>
    coalescePieces(std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                            Segment<Point<ResultNumber, typename PointType::LabelType>>>> pieces);

    template <class OtherShape, class TouchesBoundary>
    constexpr bool separatesOneDimensional(const OtherShape& other, TouchesBoundary touchesBoundary) const;

    template <bool OtherIsConvex = true, class OtherShape>
    constexpr bool separatesTwoDimensional(const OtherShape& other) const;
 
    template <bool Oriented>
    constexpr BoundaryType<Oriented> boundaryAt(std::size_t index) const {
        assert(index + 1 < size());
        return BoundaryType<Oriented>((*this)[index], (*this)[index + 1]);
    }

    constexpr void normalize() {
        std::sort(points_.begin(), points_.end());
        points_.erase(std::unique(points_.begin(), points_.end()), points_.end());
    }
 
    class Iterator {
    private:
        using BaseIterator = std::ranges::iterator_t<const Storage>;
        BaseIterator it;
        PointType x;
 
    public:
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = PointType;
        using pointer = PointType*;
        using reference = PointType&;
 
        Iterator() = default;
        Iterator(BaseIterator it, PointType x) : it(it), x(x) {}
 
        // Dereference returns value + x
        PointType operator*() const {
            return *it + x;
        }
 
        // Pre-increment
        Iterator& operator++() {
            ++it;
            return *this;
        }
 
        // Post-increment
        Iterator operator++(int) {
            Iterator tmp = *this;
            ++it;
            return tmp;
        }
 
        // Pre-decrement
        Iterator& operator--() {
            --it;
            return *this;
        }
 
        // Post-decrement
        Iterator operator--(int) {
            Iterator tmp = *this;
            --it;
            return tmp;
        }
 
        // Equality comparison
        bool operator==(const Iterator& other) const {
            return it == other.it;
        }
 
        // Other comparisons
        std::strong_ordering operator<=>(const Iterator& other) const {
            if (it < other.it) {
                return std::strong_ordering::less;
            }
            if (it > other.it) {
                return std::strong_ordering::greater;
            }
            return std::strong_ordering::equal;
        }
 
        // Addition
        Iterator operator+(difference_type n) const {
            return Iterator(it + n, x);
        }
 
        // Subtraction
        Iterator operator-(difference_type n) const {
            return Iterator(it - n, x);
        }
 
        // Difference
        difference_type operator-(const Iterator& other) const {
            return it - other.it;
        }
 
        // Array subscript operator
        PointType operator[](difference_type n) const {
            return *(it + n) + x;
        }
    };
}; // struct MonotoneChain

template <class PointType = Point<>, class Label = NoLabel>
using MonotoneChainView = MonotoneChain<PointType, Label, std::span<const PointType>>;
 
template <class PointType, class LabelType, class Storage, class TranslationNumber, class TranslationLabel>
constexpr auto operator-(const MonotoneChain<PointType, LabelType, Storage>& chain, const Point<TranslationNumber, TranslationLabel>& translation) {
    return chain + (-translation);
}
 
template <class PointType, class LabelType, class Storage, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const MonotoneChain<PointType, LabelType, Storage>& chain, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() * scalar), typename PointType::LabelType>;
    MonotoneChain<ResultPointType, LabelType> result(chain);
    result *= scalar;
    if constexpr (detail::has_label_v<LabelType>) {
        result.label() = LabelType{};
    }
    return result;
}
 
template <class Scalar, class PointType, class LabelType, class Storage>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const Scalar& scalar, const MonotoneChain<PointType, LabelType, Storage>& chain) {
    return chain * scalar;
}
 
template <class PointType, class LabelType, class Storage, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator/(const MonotoneChain<PointType, LabelType, Storage>& chain, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() / scalar), typename PointType::LabelType>;
    MonotoneChain<ResultPointType, LabelType> result(chain);
    result /= scalar;
    if constexpr (detail::has_label_v<LabelType>) {
        result.label() = LabelType{};
    }
    return result;
}
 
template <class PointType, class LabelType, class Storage>
std::ostream& operator<<(std::ostream& stream, const MonotoneChain<PointType, LabelType, Storage>& chain);
 
}  // namespace pgl