convex.hpp

Go to the documentation of this file.

#pragma once
 
#include "shape/disk.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 <type_traits>
#include <utility>
 
 
namespace pgl::detail {
template <class RandomIt, class Key = std::identity>
constexpr RandomIt cyclicMax(RandomIt first, RandomIt last, Key key = {}) {
    using diff_t = typename std::iterator_traits<RandomIt>::difference_type;
    const diff_t n = last - first;
 
    if (n == 0)
        return last;
 
    diff_t lo = 0;
    diff_t hi = n - 1;
 
    while (lo < hi) {
        const diff_t mid = lo + (hi - lo) / 2;
        const auto k_lo = key(first[lo]);
        const auto k_hi = key(first[hi]);
        const auto k_mid = key(first[mid]);
        const auto k_next = key(first[mid + 1]);
 
        if (k_mid < k_next) {
            // Ascending at mid: head right, unless the left endpoint dominates both
            // the ongoing ascent and the right endpoint (then the peak is on the left).
            if (k_next > k_lo || k_hi > k_lo)
                lo = mid + 1;
            else
                hi = mid;
        } else {
            // Descending at mid: head left, unless the right endpoint dominates both
            // mid and the left endpoint (then the peak is on the right).
            if (k_mid > k_hi || k_lo > k_hi)
                hi = mid;
            else
                lo = mid + 1;
        }
    }
 
    return first + lo;
}

template <class RandomIt, class Key = std::identity>
constexpr RandomIt cyclicMaxOrPositive(RandomIt first, RandomIt last, Key key = {}) {
    using diff_t = typename std::iterator_traits<RandomIt>::difference_type;
    const diff_t n = last - first;
 
    if (n == 0)
        return last;
 
    diff_t lo = 0;
    diff_t hi = n - 1;
 
    while (lo < hi) {
        const diff_t mid = lo + (hi - lo) / 2;
        const auto k_lo = key(first[lo]);
        if (k_lo > 0) return first + lo;
        const auto k_hi = key(first[hi]);
        if (k_hi > 0) return first + hi;
        const auto k_mid = key(first[mid]);
        if (k_mid > 0) return first + mid;
        const auto k_next = key(first[mid + 1]);
        if (k_next > 0) return first + mid + 1;
 
        if (k_mid < k_next) {
            // Ascending at mid: head right, unless the left endpoint dominates both
            // the ongoing ascent and the right endpoint (then the peak is on the left).
            if (k_next > k_lo || k_hi > k_lo)
                lo = mid + 1;
            else
                hi = mid;
        } else {
            // Descending at mid: head left, unless the right endpoint dominates both
            // mid and the left endpoint (then the peak is on the right).
            if (k_mid > k_hi || k_lo > k_hi)
                hi = mid;
            else
                lo = mid + 1;
        }
    }
 
    return first + lo;
}
 
 
} // namespace pgl::detail
 
 
namespace pgl {
 
template <class PointType = Point<>, class Label>
struct Convex;
 
Convex() -> Convex<Point<>, NoLabel>;
 
template <std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>
Convex(Range&&) -> Convex<std::remove_cvref_t<std::ranges::range_value_t<Range>>, NoLabel>;
 
template <class Number>
requires (!detail::is_point_v<Number>)
Convex(std::initializer_list<Number>) -> Convex<Point<Number>, NoLabel>;
 
template <class Number>
requires (!detail::is_point_v<Number>)
Convex(std::initializer_list<Number>, bool) -> Convex<Point<Number>, NoLabel>;
 
 
template <class PointType_, class TLabel>
struct Convex {
    using PointType = PointType_;
    using NumberType = PointType::NumberType;
    using LabelType = TLabel;
    static_assert(detail::is_point_v<PointType>, "Convex 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 Convex() = 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>
    constexpr explicit Convex(Range&& points, bool trusted = false) {
        if (trusted) {
            points_.reserve(points.size());
            for (const auto &p : points) {
                points_.push_back(p);
            }
        }
        else {
            // Compute the hull in the source point type so the orientation
            // predicates stay exact, then convert the surviving vertices to
            // PointType (a no-op move when the types already match).
            auto hull = grahamScan(points);
            if constexpr (std::is_same_v<std::remove_cvref_t<decltype(hull)>, std::vector<PointType>>) {
                points_ = std::move(hull);
            } else {
                points_.reserve(hull.size());
                for (const auto &p : hull) {
                    points_.push_back(PointType(p));
                }
            }
        }
    }

    constexpr explicit Convex(std::initializer_list<NumberType> coords, bool trusted = false) {
        assert(coords.size() % 2 == 0);
        std::vector<PointType> points;
        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) {
            points_ = std::move(points);
        }
        else {
            points_ = grahamScan(points);
        }
    }

    template<PointConcept OtherPointType, class OtherLabelType>
        requires(std::constructible_from<PointType, const OtherPointType&>)
    constexpr Convex(const Convex<OtherPointType, OtherLabelType>& 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 auto begin() const {
        return Iterator(points_.begin(), translation_);
    }

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

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

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

    constexpr auto operator<=>(const Convex& other) const {
        if (auto cmp = points_.size() <=> other.points_.size(); cmp != 0) {
            return cmp;
        }
        for (std::size_t i = 0; i < points_.size(); ++i) {
            if (auto cmp = points_[i] + translation_ <=> other.points_[i] + other.translation_; cmp != 0) {
                return cmp;
            }
        }
        return std::strong_ordering::equal;
    }

    constexpr bool operator==(const Convex& other) const {
        if (points_.size() != other.points_.size()) {
            return false;
        }
        for (std::size_t i = 0; i < points_.size(); ++i) {
            if (points_[i] + translation_ != other.points_[i] + other.translation_) {
                return false;
            }
        }
        return true;
    }

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

    constexpr auto twiceArea() const;

    template <class ResultNumber = division_result_t<NumberType>>
    constexpr auto area() const;

    [[nodiscard]] constexpr bool empty() const {
        return size() == 0;
    }

    constexpr bool isDegenerate() const;

    [[nodiscard]] constexpr bool isPoint() const;

    [[nodiscard]] constexpr std::optional<PointType> getIfPoint() const;

    [[nodiscard]] constexpr bool isSegment() const;

    [[nodiscard]] constexpr std::optional<BoundaryType<false>> getIfSegment() const;

    [[nodiscard]] constexpr bool isUndefined() const;

    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 const std::vector<PointType> vertices() const {
        auto ret = points_;
        for (auto& vertex : ret) {
            vertex += translation_;
        }
        return ret;
    }

    [[nodiscard]] constexpr Convex<PointType> convexHull() const {
        return Convex<PointType>(*this);
    }

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

    constexpr std::vector<OrientedSegment<PointType>> orientedEdges() const {
        std::vector<OrientedSegment<PointType>> result;
        auto translatedVertices = vertices();
        for (std::size_t i = 0; i < translatedVertices.size(); ++i) {
            const auto& p1 = translatedVertices[i];
            const auto& p2 = translatedVertices[(i + 1) % translatedVertices.size()];
            result.emplace_back(p1, p2);
        }
        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, size());
    }

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

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

    [[nodiscard]] constexpr explicit operator Polygon<PointType>() const {
        return Polygon<PointType>(*this, !isDegenerate());
    }

    [[nodiscard]] constexpr Polygon<PointType> asPolygon() const {
        return static_cast<Polygon<PointType>>(*this);
    }

    [[nodiscard]] constexpr PolygonWithHoles<PointType> asPolygonWithHoles() const {
        return PolygonWithHoles<PointType>(asPolygon());
    }

    [[nodiscard]] constexpr PolygonSet<PointType> asPolygonSet() const {
        return PolygonSet<PointType>(asPolygonWithHoles());
    }

    [[nodiscard]] constexpr HalfplaneIntersection<PointType> asHalfplaneIntersection() const {
        return HalfplaneIntersection<PointType>(*this);
    }

    constexpr MonotoneChain<PointType> lowerHull() const {
        if (size() <= 1) {
            return MonotoneChain<PointType>(vertices(), true);
        }
        // Vertices are stored counterclockwise from the lexicographic minimum,
        // so walking up to the lexicographic maximum traverses the lower chain,
        // already in increasing lexicographic order.
        const std::size_t maximum = maxIndex();
        std::vector<PointType> chain;
        chain.reserve(maximum + 1);
        for (std::size_t i = 0; i <= maximum; ++i) {
            chain.push_back((*this)[i]);
        }
        return MonotoneChain<PointType>(chain, true);
    }

    constexpr MonotoneChain<PointType> upperHull() const {
        if (size() <= 1) {
            return MonotoneChain<PointType>(vertices(), true);
        }
        // The upper chain is the rest of the boundary: the lexicographic maximum
        // back to vertex 0 (the lexicographic minimum). Reading it backwards —
        // vertex 0, then n-1 down to the maximum — yields increasing
        // lexicographic order, which is the chain's canonical form.
        const std::size_t n = size();
        const std::size_t maximum = maxIndex();
        std::vector<PointType> chain;
        chain.reserve(n - maximum + 1);
        chain.push_back((*this)[0]);
        for (std::size_t i = n; i > maximum; --i) {
            chain.push_back((*this)[i - 1]);
        }
        return MonotoneChain<PointType>(chain, true);
    }

    template <PointConcept OtherPoint>
    constexpr void insert(const OtherPoint& point);

    template <class TShape>
        requires(!detail::is_point_v<TShape> && requires(const TShape& shape) { shape.vertices(); })
    constexpr void insert(const TShape& shape);

    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> &&
                 (!requires(const std::remove_cvref_t<Range>& shape) { shape.vertices(); })
    constexpr void insert(Range&& range) {
        // Defined inline so MSVC can match the constrained overload; the
        // overloaded out-of-line form trips MSVC's C2244.
        std::vector<PointType> points = vertices();
        const std::size_t oldSize = points.size();
        for (const auto& point : range) {
            points.push_back(static_cast<PointType>(point));
        }
        if (points.size() == oldSize) {
            return;
        }
        rebuildHull(points);
    }

    template <class ResultNumber = division_result_t<NumberType>>
    constexpr Point<ResultNumber> centroid() const;

    template <class ResultNumber = division_result_t<NumberType>>
    constexpr Point<ResultNumber> verticesCentroid() const;
 

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

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

    size_t size() const {
        return points_.size();
    }

    constexpr size_t maxIndex() const;

    template<PointConcept OtherPoint>
    constexpr bool verticesContain(const OtherPoint& point) const;

    constexpr std::ptrdiff_t index(const PointType& point) const;

    constexpr std::vector<std::pair<std::size_t, std::size_t>>
    antipodalPairs() const;

    constexpr Segment<PointType> diameter() const;

    [[nodiscard]] constexpr HalfplaneIntersection<PointType> smallestEnclosingRectangle() const;

    [[nodiscard]] constexpr HalfplaneIntersection<PointType> smallestEnclosingSlab() const;

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

    template <class ApproximateNumber = double>
    [[nodiscard]] ApproximateNumber minimumWidth() const;

    template <class UniformRandomBitGenerator>
    [[nodiscard]] Disk<Point<NumberType>>
    smallestEnclosingDisk(UniformRandomBitGenerator&& generator) const;

    [[nodiscard]] Disk<Point<NumberType>> smallestEnclosingDisk() const;
 

    template<PointConcept OtherPoint>
    constexpr bool boundaryContains(const OtherPoint& point) const;

    template<SegmentConcept OtherSegment>
    constexpr bool boundaryContains(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    constexpr bool boundaryContains(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    constexpr bool boundaryContains(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool boundaryContains(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    constexpr bool boundaryContains(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool boundaryContains(const OtherHalfplane& other) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool boundaryContains(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool boundaryContains(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool boundaryContains(const OtherConvex& other) const;

    template<PolygonConcept OtherPolygon>
    constexpr bool boundaryContains(const OtherPolygon& other) const;

    template<DiskConcept OtherDisk>
    constexpr bool boundaryContains(const OtherDisk& other) const;

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

    template<class OtherNumberType>
    constexpr std::optional<std::array<Segment<PointType>, 2>> edgesAtX(OtherNumberType x) const;

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

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

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

    template<LineConcept OtherLine>
    constexpr bool contains(const OtherLine&) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool contains(const OtherOrientedLine&) const;

    template<RayConcept OtherRay>
    constexpr bool contains(const OtherRay&) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool contains(const OtherHalfplane&) const;

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

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

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

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

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

    template<PointConcept OtherPoint>
    constexpr bool contains(const Shape<OtherPoint>& other) const;
 
    // The empty set is a subset of every shape, so its containment relations are
    // true. separates has no symmetric fallback, so it gets an explicit overload
    // too; the symmetric intersection/crossing predicates instead reach the
    // empty set through the generic OtherShape fallbacks declared below.
    template <class EmptyPoint>
    [[nodiscard]] constexpr bool contains(const EmptyShape<EmptyPoint>&) const {
        return true;
    }

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

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

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

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

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

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

    template<LineConcept OtherLine>
    constexpr bool interiorContains(const OtherLine&) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool interiorContains(const OtherOrientedLine&) const;

    template<RayConcept OtherRay>
    constexpr bool interiorContains(const OtherRay&) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool interiorContains(const OtherHalfplane&) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool interiorContains(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool interiorContains(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool interiorContains(const OtherConvex& other) const;

    template<PolygonConcept OtherPolygon>
    constexpr bool interiorContains(const OtherPolygon& other) const;

    template<DiskConcept OtherDisk>
    constexpr bool interiorContains(const OtherDisk& other) const;

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

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

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

    template<LineConcept OtherLine>
    constexpr bool intersects(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool intersects(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    constexpr bool intersects(const OtherRay& other) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool intersects(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool intersects(const OtherTriangle& other) const;

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

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool intersects(const OtherHalfplane& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool intersects(const OtherConvex& other) const;

    template<DiskConcept OtherDisk>
    constexpr bool intersects(const OtherDisk& other) const;

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

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

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

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

    template<LineConcept OtherLine>
    constexpr bool interiorsIntersect(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool interiorsIntersect(const OtherOrientedLine& other) const;

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

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

    template<RayConcept OtherRay>
    constexpr bool interiorsIntersect(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool interiorsIntersect(const OtherHalfplane& other) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool interiorsIntersect(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool interiorsIntersect(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool interiorsIntersect(const OtherConvex& other) const;

    template<DiskConcept OtherDisk>
    constexpr bool interiorsIntersect(const OtherDisk& other) const;

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

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

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

    template<PointConcept OtherPoint>
    constexpr bool separates(const OtherPoint&) const;

    template<SegmentConcept OtherSegment>
    constexpr bool separates(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    constexpr bool separates(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    constexpr bool separates(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool separates(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    constexpr bool separates(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool separates(const OtherHalfplane&) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool separates(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool separates(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool separates(const OtherConvex& other) const;

    template<PolygonConcept OtherPolygon>
    constexpr bool separates(const OtherPolygon& other) const;

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

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

    template<MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr bool interiorContains(const OtherChain& 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;

    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<DiskConcept OtherDisk>
    constexpr bool separates(const OtherDisk& other) const;

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

    template<PointConcept OtherPoint>
    constexpr bool crosses(const OtherPoint&) const;

    template<SegmentConcept OtherSegment>
    constexpr bool crosses(const OtherSegment& other) const;

    template<OrientedSegmentConcept OtherOrientedSegment>
    constexpr bool crosses(const OtherOrientedSegment& other) const;

    template<LineConcept OtherLine>
    constexpr bool crosses(const OtherLine& other) const;

    template<OrientedLineConcept OtherOrientedLine>
    constexpr bool crosses(const OtherOrientedLine& other) const;

    template<RayConcept OtherRay>
    constexpr bool crosses(const OtherRay& other) const;

    template<HalfplaneConcept OtherHalfplane>
    constexpr bool crosses(const OtherHalfplane&) const;

    template<RectangleConcept OtherRectangle>
    constexpr bool crosses(const OtherRectangle& other) const;

    template<TriangleConcept OtherTriangle>
    constexpr bool crosses(const OtherTriangle& other) const;

    template<ConvexConcept OtherConvex>
    constexpr bool crosses(const OtherConvex& other) const;

    template<DiskConcept OtherDisk>
    constexpr bool crosses(const OtherDisk& other) const;

    template<PointConcept OtherPoint>
    constexpr bool crosses(const Shape<OtherPoint>& other) const;

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

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

    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>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto squaredDistance(const OtherConvex& 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>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto squaredDistance(const OtherRectangle& 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 = double, DiskConcept OtherDisk>
    [[nodiscard]] detail::floating_result_t<ResultNumber> squaredDistance(const OtherDisk& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Convex>)
                  && requires(const OtherShape& o, const Convex& 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<Convex<PointType_, TLabel>, OtherShape>
    [[nodiscard]] constexpr auto closestSegments(const OtherShape& other) const;

    template <class ResultNumber = division_result_t<NumberType>, class OtherShape>
        requires detail::ClosestPointsPairConcept<Convex<PointType_, TLabel>, 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>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto distanceL1(const OtherConvex& 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>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto distanceL1(const OtherRectangle& 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>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Convex>)
                  && requires(const OtherShape& o, const Convex& 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 = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] auto regularizedIntersection(const Shape<OtherPoint>& other) const {
        return other.template regularizedIntersection<ResultNumber>(*this);
    }

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

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

    template <class ResultNumber = division_result_t<NumberType>, PointConcept OtherPoint>
    [[nodiscard]] auto symmetricDifference(const Shape<OtherPoint>& other) const {
        return other.template symmetricDifference<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>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto distanceLInf(const OtherConvex& 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>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto distanceLInf(const OtherRectangle& 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>, typename OtherShape>
        requires ((detail::shapeRank<OtherShape> > detail::shapeRank<Convex>)
                  && requires(const OtherShape& o, const Convex& 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 ResultNumber = NumberType, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherPoint& point) const;

    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherOrientedSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherRectangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto hausdorffDistanceL1(const OtherConvex& other) const;

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

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

    template <class ResultNumber = NumberType, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherPoint& point) const;

    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherOrientedSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherRectangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto hausdorffDistanceLInf(const OtherConvex& other) const;

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

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

    template <class ResultNumber = NumberType, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherPoint& point) const;

    template <class ResultNumber = division_result_t<NumberType>, SegmentConcept OtherSegment>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherOrientedSegment& other) const;

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherRectangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] constexpr auto squaredHausdorffDistance(const OtherConvex& other) const;

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

    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>
    constexpr std::optional<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>
    constexpr std::optional<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>
    constexpr std::optional<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>
    constexpr std::optional<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>
    constexpr std::optional<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>
    constexpr std::optional<std::variant<Point<ResultNumber, typename PointType::LabelType>, Segment<Point<ResultNumber, typename PointType::LabelType>>, Convex<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherHalfplane& other) const;

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

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    constexpr std::optional<std::variant<Point<ResultNumber, typename PointType::LabelType>, Segment<Point<ResultNumber, typename PointType::LabelType>>, Convex<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherRectangle& other) const;
 

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    constexpr std::optional<std::variant<Point<ResultNumber, typename PointType::LabelType>, Segment<Point<ResultNumber, typename PointType::LabelType>>, Convex<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    constexpr std::optional<std::variant<Point<ResultNumber, typename PointType::LabelType>, Segment<Point<ResultNumber, typename PointType::LabelType>>, Convex<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherConvex& other) const;

    template <class ResultNumber = division_result_t<NumberType>, typename OtherShape>
        requires (!PointConcept<OtherShape>
                  && !HalfplaneIntersectionConcept<OtherShape>
                  && (detail::shapeRank<OtherShape> > detail::shapeRank<Convex>)
                  && requires(const OtherShape& o, const Convex& 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>, typename OtherShape>
        requires (!PointConcept<OtherShape>
                  && (detail::shapeRank<OtherShape> > detail::shapeRank<Convex>)
                  && requires(const OtherShape& o, const Convex& self) {
                         o.template regularizedIntersection<ResultNumber>(self);
                     })
    [[nodiscard]] constexpr auto regularizedIntersection(const OtherShape& other) const {
        return other.template regularizedIntersection<ResultNumber>(*this);
    }

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

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

    constexpr void rotate90(int k = 1);

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

    template <class OtherNumber>
    constexpr void scaleUpX(const OtherNumber scalar);

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

    template <class OtherNumber>
    constexpr void scaleUpY(const OtherNumber scalar);

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

    template <class OtherNumber>
    constexpr void scaleDownX(const OtherNumber scalar);

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

    template <class OtherNumber>
    constexpr void scaleDownY(const OtherNumber scalar);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    template<PointConcept OtherPoint>
    constexpr Convex& operator+=(const OtherPoint& translation);

    template<PointConcept OtherPoint>
    constexpr Convex& operator-=(const OtherPoint& translation);

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr Convex& operator*=(const Scalar& scalar);

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr Convex& operator/=(const Scalar& scalar);

    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(convex != nullptr);
            return convex->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 Convex;
 
        constexpr BoundaryIterator(const Convex* convex_arg, std::size_t index_arg)
            : convex(convex_arg), index(index_arg) {}
 
        const Convex* convex = nullptr;
        std::size_t index = 0;
    };
 
  private:
    std::vector<PointType> points_{};
    [[no_unique_address]] mutable LabelType label_{};
    PointType translation_{};
    // Lazily computed caches, invalidated by resetCache() on every mutation.
    // maxIndex_ is -1 until first computed; bbox_ uses the empty rectangle as
    // its "not computed yet", which only a vertexless polygon can also mean,
    // and that case costs one size check to re-derive.
    mutable Rectangle<PointType> bbox_{};
    mutable std::ptrdiff_t maxIndex_ = -1;
 
    // Memoized hash, computed lazily by std::hash<Convex>. 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<Convex>;
 
    // Drops every memoized value; call after any operation that mutates the
    // polygon's vertices. A pure translation does not need to drop bbox_/maxIndex_
    // (maxIndex_ stays valid and the bbox shifts in place, see operator+=), but it
    // must still reset hash_, which depends on the absolute vertex positions.
    constexpr void resetCache() const {
        bbox_ = {};
        maxIndex_ = -1;
        hash_ = hashUnset_;
    }
 
    // Replaces the vertices by the convex hull of `points`, which are absolute
    // coordinates (the translation is already applied), so it is folded away.
    constexpr void rebuildHull(const std::vector<PointType>& points) {
        points_ = grahamScan(points);
        translation_ = {};
        resetCache();
    }
 
    template <bool Oriented>
    constexpr BoundaryType<Oriented> boundaryAt(std::size_t index) const {
        const auto i = static_cast<std::ptrdiff_t>(index);
        return BoundaryType<Oriented>(get(i), get(i + 1));
    }
 
    // Lexicographic less-than that promotes mixed numeric types to their
    // common type before comparing. Lets std::lower_bound / std::binary_search
    // search points_ with a key whose NumberType differs from PointType's.
    struct LexLessCrossType {
        template <class A, class B>
        constexpr bool operator()(const A& a, const B& b) const {
            using AX = std::remove_cvref_t<decltype(a.x())>;
            using BX = std::remove_cvref_t<decltype(b.x())>;
            using C = std::common_type_t<AX, BX>;
            const auto ax = static_cast<C>(a.x());
            const auto bx = static_cast<C>(b.x());
            if (ax < bx) return true;
            if (bx < ax) return false;
            return detail::asNumber<C>(a.y()) < detail::asNumber<C>(b.y());
        }
    };
    static constexpr LexLessCrossType lexLessCrossType{};
 
    class Iterator {
    private:
        std::vector<PointType>::const_iterator 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(std::vector<PointType>::const_iterator 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
        auto operator<=>(const Iterator& other) const {
            return it <=> other.it;
        }
 
        // 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;
        }
    };
}; // class Convex
 
template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto operator-(const Convex<PointType, LabelType>& convex, const Point<TranslationNumber, TranslationLabel>& translation) {
    return convex + (-translation);
}
 
template <class PointType, class LabelType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const Convex<PointType, LabelType>& convex, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() * scalar), typename PointType::LabelType>;
    Convex<ResultPointType, LabelType> result(convex);
    result *= scalar;
    if constexpr (detail::has_label_v<LabelType>) {
        result.label() = LabelType{};
    }
    return result;
}
 
template <class Scalar, class PointType, class LabelType>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const Scalar& scalar, const Convex<PointType, LabelType>& convex) {
    return convex * scalar;
}
 
template <class PointType, class LabelType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator/(const Convex<PointType, LabelType>& convex, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() / scalar), typename PointType::LabelType>;
    Convex<ResultPointType, LabelType> result(convex);
    result /= scalar;
    if constexpr (detail::has_label_v<LabelType>) {
        result.label() = LabelType{};
    }
    return result;
}
 
template <class PointType, class LabelType>
std::ostream& operator<<(std::ostream& stream, const Convex<PointType, LabelType>& convex);
 
}  // namespace pgl