polygonwithholes.hpp

Go to the documentation of this file.

#pragma once
 
#include "shape/halfplaneintersection.hpp"
 
#include <algorithm>
#include <cassert>
#include <compare>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <optional>
#include <ostream>
#include <ranges>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
 
 
namespace pgl {
 
template <class PointType = Point<>, class Label>
struct PolygonWithHoles;
 
PolygonWithHoles() -> PolygonWithHoles<Point<>, NoLabel>;
 
template <PolygonConcept OuterPolygon>
PolygonWithHoles(OuterPolygon&&) -> PolygonWithHoles<typename std::remove_cvref_t<OuterPolygon>::PointType, NoLabel>;
 
template <PolygonConcept OuterPolygon>
PolygonWithHoles(OuterPolygon&&, bool) -> PolygonWithHoles<typename std::remove_cvref_t<OuterPolygon>::PointType, NoLabel>;
 
template <PolygonConcept OuterPolygon, std::ranges::input_range HoleRange>
    requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>
PolygonWithHoles(OuterPolygon&&, HoleRange&&) -> PolygonWithHoles<typename std::remove_cvref_t<OuterPolygon>::PointType, NoLabel>;
 
template <PolygonConcept OuterPolygon, std::ranges::input_range HoleRange>
    requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>
PolygonWithHoles(OuterPolygon&&, HoleRange&&, bool) -> PolygonWithHoles<typename std::remove_cvref_t<OuterPolygon>::PointType, NoLabel>;
 

template <class PointType_, class TLabel>
struct PolygonWithHoles {
    using PointType = PointType_;
    using NumberType = typename PointType::NumberType;
    using LabelType = TLabel;
    using PolygonType = Polygon<PointType>;
    using EdgeType = Segment<PointType>;
    static_assert(detail::is_point_v<PointType>, "PolygonWithHoles requires pgl::Point vertices");
 
    class VertexIterator;

    constexpr PolygonWithHoles() = default;

    constexpr explicit PolygonWithHoles(PolygonType outer)
        : outer_(std::move(outer)) {}

    template <std::ranges::input_range HoleRange>
        requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>
    constexpr PolygonWithHoles(PolygonType outer, HoleRange&& holes, bool trusted = false)
        : outer_(std::move(outer)) {
        for (const auto& hole : holes) {
            holes_.emplace_back(hole);
        }
        if (!trusted) {
            normalize();
        }
    }

    template <PointConcept OtherPointType, class OtherLabelType>
        requires(std::constructible_from<PointType, const OtherPointType&>)
    constexpr PolygonWithHoles(const PolygonWithHoles<OtherPointType, OtherLabelType>& other)
        : outer_(other.outer()) {
        holes_.reserve(other.holeCount());
        for (const auto& hole : other.holes()) {
            holes_.emplace_back(hole);
        }
    }

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

    [[nodiscard]] constexpr const PolygonType& outer() const {
        return outer_;
    }

    [[nodiscard]] constexpr std::size_t holeCount() const {
        return holes_.size();
    }

    [[nodiscard]] constexpr bool hasHoles() const {
        return !holes_.empty();
    }

    [[nodiscard]] constexpr const PolygonType& hole(std::size_t index) const {
        assert(index < holes_.size());
        return holes_[index];
    }

    [[nodiscard]] constexpr const std::vector<PolygonType>& holes() const {
        return holes_;
    }

    [[nodiscard]] constexpr auto begin() const { return holes_.begin(); }

    [[nodiscard]] constexpr auto cbegin() const { return holes_.cbegin(); }

    [[nodiscard]] constexpr auto end() const { return holes_.end(); }

    [[nodiscard]] constexpr auto cend() const { return holes_.cend(); }

    constexpr void addHole(PolygonType hole) {
        if (hole.isDegenerate()) {
            return;
        }
        const auto position = std::lower_bound(holes_.begin(), holes_.end(), hole);
        holes_.insert(position, std::move(hole));
        resetCache();
    }

    constexpr void eraseHole(std::size_t index) {
        assert(index < holes_.size());
        holes_.erase(holes_.begin() + static_cast<std::ptrdiff_t>(index));
        resetCache();
    }

    constexpr bool eraseHole(const PolygonType& hole) {
        const auto position = std::lower_bound(holes_.begin(), holes_.end(), hole);
        if (position == holes_.end() || !(*position == hole)) {
            return false;
        }
        holes_.erase(position);
        resetCache();
        return true;
    }

    [[nodiscard]] constexpr std::size_t vertexCount() const {
        std::size_t total = outer_.size();
        for (const auto& hole : holes_) {
            total += hole.size();
        }
        return total;
    }

    [[nodiscard]] constexpr std::size_t chainCount() const {
        std::size_t total = outer_.chainCount();
        for (const auto& hole : holes_) {
            total += hole.chainCount();
        }
        return total;
    }

    [[nodiscard]] constexpr std::vector<PointType> vertices() const {
        std::vector<PointType> result;
        result.reserve(vertexCount());
        for (const auto& vertex : outer_) {
            result.push_back(vertex);
        }
        for (const auto& hole : holes_) {
            for (const auto& vertex : hole) {
                result.push_back(vertex);
            }
        }
        return result;
    }

    [[nodiscard]] constexpr auto verticesView() const {
        return std::ranges::subrange(verticesBegin(), verticesEnd());
    }

    [[nodiscard]] constexpr VertexIterator verticesBegin() const {
        return VertexIterator(this, 0);
    }

    [[nodiscard]] constexpr VertexIterator verticesEnd() const {
        return VertexIterator(this, 1 + holes_.size());
    }

    [[nodiscard]] constexpr std::vector<EdgeType> edges() const {
        std::vector<EdgeType> result;
        result.reserve(vertexCount());
        for (const auto& edge : outer_.edgesView()) {
            result.push_back(edge);
        }
        for (const auto& hole : holes_) {
            for (const auto& edge : hole.edgesView()) {
                result.push_back(edge);
            }
        }
        return result;
    }

    [[nodiscard]] constexpr std::vector<OrientedSegment<PointType>> orientedEdges() const {
        std::vector<OrientedSegment<PointType>> result;
        result.reserve(vertexCount());
        for (const auto& edge : outer_.orientedEdgesView()) {
            result.push_back(edge);
        }
        for (const auto& hole : holes_) {
            for (const auto& edge : hole.orientedEdgesView()) {
                result.emplace_back(edge.target(), edge.source());
            }
        }
        return result;
    }

    [[nodiscard]] constexpr PolygonSet<PointType> asPolygonSet() const {
        return PolygonSet<PointType>(*this);
    }
 
    // -------------------------------------------------------------------------
    // Value semantics

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

    [[nodiscard]] constexpr bool operator==(const PolygonWithHoles& other) const {
        if (!(outer_ == other.outer_) || holes_.size() != other.holes_.size()) {
            return false;
        }
        for (std::size_t i = 0; i < holes_.size(); ++i) {
            if (!(holes_[i] == other.holes_[i])) {
                return false;
            }
        }
        return true;
    }

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

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

    [[nodiscard]] constexpr bool isDegenerate() const {
        using Exact = detail::promoted_number_t<NumberType>;
        return twiceArea<Exact>() == Exact(0);
    }

    [[nodiscard]] constexpr bool isPoint() const {
        return outer_.isPoint();
    }

    [[nodiscard]] constexpr bool isSegment() const {
        return outer_.isSegment();
    }

    [[nodiscard]] constexpr bool isUndefined() const {
        return !isPoint() && !isSegment() && isDegenerate();
    }

    template <class Rational = pgl::Rational<pgl::BigInt>>
    [[nodiscard]] bool isSimple() const {
        if (!outer_.template isSimple<Rational>()) {
            return false;
        }
        for (const auto& hole : holes_) {
            if (!hole.template isSimple<Rational>()) {
                return false;
            }
        }
        return true;
    }

    template <class Rational = pgl::Rational<pgl::BigInt>>
    [[nodiscard]] bool isValid() const;

    [[nodiscard]] bool isRegular() const;

    template <class ResultNumber = division_result_t<NumberType>>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    regularized() const;
 
    // -------------------------------------------------------------------------
    // Measures

    template <class ResultNumber = NumberType>
    [[nodiscard]] constexpr ResultNumber twiceArea() const {
        ResultNumber total = outer_.template twiceArea<ResultNumber>();
        for (const auto& hole : holes_) {
            total -= hole.template twiceArea<ResultNumber>();
        }
        return total;
    }

    template <class ResultNumber = division_result_t<NumberType>>
    [[nodiscard]] constexpr auto area() const {
        ResultNumber result = static_cast<ResultNumber>(twiceArea());
        return result / ResultNumber(2);
    }

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

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

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

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

    auto triangulation() const;

    template <class SegmentRange>
    auto triangulation(const SegmentRange& segments) const;

    [[nodiscard]] Graph<PointType> visibilityGraph() const;

    [[nodiscard]] Graph<PointType> clearVisibilityGraph() const;

    [[nodiscard]] Graph<PointType> reducedVisibilityGraph() const;

    [[nodiscard]] std::vector<PointType> visibleVertices(const PointType& query) const;

    [[nodiscard]] std::vector<PointType> clearlyVisibleVertices(const PointType& query) const;

    template <class ResultNumber = division_result_t<NumberType>>
    [[nodiscard]] Polygon<Point<ResultNumber>> regularizedVisiblePolygon(
        const PointType& query) const;

    [[nodiscard]] std::vector<Convex<PointType>> convexPartition() const;

    [[nodiscard]] std::vector<Convex<PointType>> convexCovering() const;

    template <class ResultNumber = grid_number_t<typename PointType_::NumberType>>
        requires(std::signed_integral<ResultNumber>)
    [[nodiscard]] auto asBitMatrix() const;

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

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

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

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

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

    template <class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    difference(const OtherSet& 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>, PolygonConcept OtherPolygon>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    regularizedUnion(const OtherPolygon& other) const;

    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>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    regularizedUnion(const OtherRegion& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
    [[nodiscard]] auto regularizedUnion(const OtherSet& other) const {
        return other.template regularizedUnion<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>
    [[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>, PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr auto intersection(const OtherPolyline& other) const;

    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr auto intersection(const OtherChain& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonConcept OtherPolygon>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherPolygon& other) const;

    template <class ResultNumber = division_result_t<NumberType>, ConvexConcept OtherConvex>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherConvex& other) const;

    template <class ResultNumber = division_result_t<NumberType>, TriangleConcept OtherTriangle>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherTriangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, RectangleConcept OtherRectangle>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherRectangle& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherRegion& other) const;

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherIntersection& other) const;

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] std::vector<std::variant<Point<ResultNumber, typename PointType::LabelType>,
                                           Polyline<Point<ResultNumber, typename PointType::LabelType>>,
                                           PolygonWithHoles<Point<ResultNumber, typename PointType::LabelType>>>>
    intersection(const OtherHalfplane& other) const;

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

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

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

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

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

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

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneConcept OtherHalfplane>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    regularizedIntersection(const OtherHalfplane& 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>, PolygonConcept OtherPolygon>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    symmetricDifference(const OtherPolygon& 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>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] PolygonSet<Point<ResultNumber, typename PointType::LabelType>>
    symmetricDifference(const OtherRegion& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonSetConcept OtherSet>
    [[nodiscard]] auto symmetricDifference(const OtherSet& other) const {
        return other.template symmetricDifference<ResultNumber>(*this);
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

    [[nodiscard]] constexpr Segment<PointType> diameter() const {
        return outer_.diameter();
    }

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

    [[nodiscard]] constexpr const Rectangle<PointType>& bbox() const {
        return outer_.bbox();
    }

    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>
    [[nodiscard]] constexpr Rectangle<Point<ResultNumber>> fbox() const {
        return outer_.template fbox<ResultNumber>();
    }
 
    // -------------------------------------------------------------------------
    // Predicates against a point
    //
    // Direct rewritings of A = outer \ ⋃ hole°:
    //   contains(p)         outer contains p, and no hole contains p strictly
    //   interiorContains(p) outer contains p strictly, and no hole contains p
    //   boundaryContains(p) p lies on the outer ring or on some hole ring

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

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

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

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

    template <PointConcept OtherPoint>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherPoint&) const {
        return false;
    }
 
    // -------------------------------------------------------------------------
    // Predicates against a segment
    //
    // Rewritings of A = outer \ ⋃ hole°, using the fact that a segment is
    // connected and that every point of every ring boundary belongs to A:
    //   contains(S)         S ⊆ outer, and no hole interior meets S
    //   interiorContains(S) S ⊆ outer°, and no hole meets S at all
    //   intersects(S)       S meets a ring boundary, or an endpoint decides
    //   boundaryContains(S) S ⊆ A with no piece reaching the interior

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

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

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

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

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

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

    template <OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool boundaryContains(const OtherOrientedSegment& 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 <SegmentConcept OtherSegment>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherSegment& other) const;

    template <OrientedSegmentConcept OtherOrientedSegment>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherOrientedSegment& other) const;
 
    // -------------------------------------------------------------------------
    // Predicates against a line, an oriented line, a ray, and a half-plane
    //
    // All four operands are unbounded, which decides two of the five relations
    // outright:
    //   contains/interiorContains/boundaryContains  only a degenerate operand
    //   intersects(B)                               outer.intersects(B)
    //
    // The second line needs no hole bookkeeping: an unbounded connected shape
    // that reaches the bounded outer polygon has to leave it again, so it meets
    // ∂outer, and every point of ∂outer belongs to the region because hole
    // interiors never reach it.

    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 <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 <LineConcept OtherLine>
    [[nodiscard]] constexpr bool boundaryContains(const OtherLine& other) const;

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

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

    template <HalfplaneConcept OtherHalfplane>
    [[nodiscard]] constexpr bool boundaryContains(const OtherHalfplane& 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 <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;
 
    // -------------------------------------------------------------------------
    // Predicates against a bounded shape with area: a rectangle, a triangle, a
    // convex polygon, a simple polygon, and another region with holes.
    //
    // All five are closed, connected, and — when they have any area — the
    // closure of their own interior, which is what lets the rewritings of
    // A = outer ∖ ⋃ hole° stay in terms of the operand itself:
    //   contains(B)         B ⊆ outer, and no hole interior meets B
    //   interiorContains(B) B ⊆ outer°, and no hole meets B at all
    //   boundaryContains(B) only a B without area, edge by edge
    //   intersects(B)       B meets a ring, or one point of B decides
    //   interiorsIntersect(B) an edge of B reaches A°, or a domain triangle
    //                       of A meets B°
    //
    // The last one is the only one that cannot be read off the rings: A° is
    // neither simply connected nor even connected, so the witness arguments the
    // simply connected shapes use do not carry over. See @ref
    // areaInteriorsIntersect.

    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 <PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr bool contains(const OtherRegion& other) const;

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

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

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

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

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

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

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

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

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

    template <PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr bool boundaryContains(const OtherRegion& 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 <PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr bool intersects(const OtherPolygon& other) const;

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

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

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

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

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

    template <PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] bool interiorsIntersect(const OtherRegion& other) const;
 
    // -------------------------------------------------------------------------
    // Predicates against a polygonal chain: a monotone chain and a polyline.
    //
    // Both are one-dimensional and are exactly the union of their edges, so the
    // four set-level relations are settled edge by edge with no hole bookkeeping
    // of their own — the segment overloads already carry it. Only
    // interiorsIntersect needs the chain's own convention: its relative interior
    // is the chain minus its two extreme points, i.e. the open edges together
    // with the vertices between them.

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

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

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

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

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

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

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

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

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

    template <PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr bool interiorsIntersect(const OtherPolyline& other) const;
 
    // -------------------------------------------------------------------------
    // Predicates against a disk
    //
    // A disk is closed, bounded, connected, and — unless it has degenerated —
    // the closure of its own interior. That last property is what the area
    // operands of §3 could not assume, and having it back brings the direct
    // per-hole rewriting of A = outer ∖ ⋃ hole° with it:
    //   contains(D)         outer contains D, and no hole interior meets D
    //   interiorContains(D) outer° contains D, and no hole meets D at all
    // The disk has no edges, though, so interiorsIntersect has no boundary scan
    // to fall back on and goes to the triangulated domain directly.

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

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

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

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

    template <DiskConcept OtherDisk>
    [[nodiscard]] bool interiorsIntersect(const OtherDisk& other) const;
 
    // -------------------------------------------------------------------------
    // Predicates against a half-plane intersection
    //
    // The operand is convex and closed but need not be bounded, which splits the
    // work in two. The three containment relations want a bounded operand — the
    // region is bounded — and a bounded, non-degenerate half-plane intersection
    // is a convex polygon, so they hand it to the area path as one. A degenerate
    // one is a point, a segment, a ray, or a line, and goes to the overload for
    // that carrier. intersects and interiorsIntersect keep the unbounded case:
    // the first by the ring-contact argument the other operands use, the second
    // by clipping the operand to the region's bounding box first, which changes
    // no answer because the region interior lies strictly inside that box.

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

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

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

    template <HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] constexpr bool intersects(const OtherIntersection& other) const;

    template <HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] bool interiorsIntersect(const OtherIntersection& other) const;
 
    // -------------------------------------------------------------------------
    // Cut predicates
    //
    // `A.separates(B)` asks whether `B ∖ A` is disconnected, and
    // `A.crosses(B)` whether each shape separates the other. Both are collected
    // here rather than split per operand family because a region settles every
    // one of them the same way — the cell engine of implementation/
    // separates.hpp, which assumes nothing about either operand — while a
    // region without holes forwards to its outer polygon throughout.
    //
    // A region is connected however its rings meet — its complement is a
    // disjoint union of simply connected open sets, which encloses nothing —
    // so `B ∖ A` comes apart only when the removal genuinely severs it. What
    // does change against the simply connected operands is what suffices to
    // sever: a region is cut by a single point at a pinch, or by a segment run
    // from one hole to another, neither of which can cut a polygon.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    template <HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] bool crosses(const OtherIntersection& other) const;
 
    // -------------------------------------------------------------------------
    // Distances
    //
    // The region is closed, so whenever it misses the other shape the nearest
    // pair is realized on ∂A — the minimum over the edges of every ring.

    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>, PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr auto squaredDistance(const OtherPolygon& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr auto squaredDistance(const OtherRegion& other) const;

    template <class ResultNumber = division_result_t<NumberType>, MonotoneChainConcept OtherChain>
    [[nodiscard]] constexpr auto squaredDistance(const OtherChain& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr auto squaredDistance(const OtherPolyline& other) const;

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] constexpr auto squaredDistance(const OtherIntersection& other) const;

    template <class ResultNumber = double, DiskConcept OtherDisk>
    [[nodiscard]] detail::floating_result_t<ResultNumber> squaredDistance(const OtherDisk& other) const;

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

    template <class ResultNumber = division_result_t<NumberType>, class OtherShape>
        requires detail::ClosestPointsPairConcept<PolygonWithHoles<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>, 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>, PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr auto distanceL1(const OtherPolygon& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr auto distanceL1(const OtherRegion& 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>, PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr auto distanceL1(const OtherPolyline& other) const;

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] constexpr auto distanceL1(const OtherIntersection& other) const;

    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>, PolygonConcept OtherPolygon>
    [[nodiscard]] constexpr auto distanceLInf(const OtherPolygon& other) const;

    template <class ResultNumber = division_result_t<NumberType>, PolygonWithHolesConcept OtherRegion>
    [[nodiscard]] constexpr auto distanceLInf(const OtherRegion& 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>, PolylineConcept OtherPolyline>
    [[nodiscard]] constexpr auto distanceLInf(const OtherPolyline& other) const;

    template <class ResultNumber = division_result_t<NumberType>, HalfplaneIntersectionConcept OtherIntersection>
    [[nodiscard]] constexpr auto distanceLInf(const OtherIntersection& other) const;
 
    // -------------------------------------------------------------------------
    // A set of regions
    //
    // The first shape to outrank a region, and so the first operand a region
    // forwards the symmetric relations to rather than answering itself. The
    // asymmetric ones are answered here: a set is the union of its components,
    // so a region holds it exactly when it holds every one of them.

    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 OtherShape>
        requires(!PointConcept<OtherShape> &&
                 detail::shapeRank<OtherShape> > detail::shapeRank<PolygonWithHoles>)
    [[nodiscard]] constexpr bool intersects(const OtherShape& other) const {
        return other.intersects(*this);
    }

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

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

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

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

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

    template <class ResultNumber = division_result_t<NumberType>, class OtherShape>
        requires((detail::shapeRank<OtherShape> > detail::shapeRank<PolygonWithHoles>) &&
                 requires(const OtherShape& o, const PolygonWithHoles& 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>, class OtherShape>
        requires((detail::shapeRank<OtherShape> > detail::shapeRank<PolygonWithHoles>) &&
                 requires(const OtherShape& o, const PolygonWithHoles& self) {
                     o.template distanceLInf<ResultNumber>(self);
                 })
    [[nodiscard]] constexpr auto distanceLInf(const OtherShape& other) const {
        return other.template distanceLInf<ResultNumber>(*this);
    }
 
    // -------------------------------------------------------------------------
    // The empty set is a subset of every shape, so its containment relations
    // are true and its intersection relations are false.

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool contains(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 boundaryContains(const EmptyShape<EmptyPoint>&) const {
        return true;
    }

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

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

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

    template <class EmptyPoint>
    [[nodiscard]] constexpr bool crosses(const EmptyShape<EmptyPoint>&) const {
        return false;
    }
 
    // -------------------------------------------------------------------------
    // Runtime Shape argument: visit the wrapped alternative and re-dispatch to
    // the matching per-shape overload (defined in the implementation layer).

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

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

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

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

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

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

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

    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 = double, PointConcept OtherPoint>
    [[nodiscard]] constexpr auto distanceLInf(const Shape<OtherPoint>& other) const {
        return other.template distanceLInf<ResultNumber>(*this);
    }
 
    // -------------------------------------------------------------------------
    // Transformations

    template <class TranslationNumber, class TranslationLabel>
    constexpr PolygonWithHoles& operator+=(const Point<TranslationNumber, TranslationLabel>& translation) {
        outer_ += translation;
        for (auto& hole : holes_) {
            hole += translation;
        }
        resetCache();
        return *this;
    }

    template <class TranslationNumber, class TranslationLabel>
    constexpr PolygonWithHoles& operator-=(const Point<TranslationNumber, TranslationLabel>& translation) {
        return *this += (-translation);
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr PolygonWithHoles& operator*=(const Scalar& scalar) {
        outer_ *= scalar;
        for (auto& hole : holes_) {
            hole *= scalar;
        }
        normalize();
        return *this;
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr PolygonWithHoles& operator/=(const Scalar& scalar) {
        outer_ /= scalar;
        for (auto& hole : holes_) {
            hole /= scalar;
        }
        normalize();
        return *this;
    }

    [[nodiscard]] constexpr PolygonWithHoles rotated90(int k) const {
        PolygonWithHoles result;
        result.outer_ = outer_.rotated90(k);
        result.holes_.reserve(holes_.size());
        for (const auto& hole : holes_) {
            result.holes_.push_back(hole.rotated90(k));
        }
        result.normalize();
        return result;
    }

    constexpr void rotate90(int k) {
        auto saved = label_;
        *this = rotated90(k);
        label_ = std::move(saved);
    }

    template <class OtherNumber>
    [[nodiscard]] constexpr PolygonWithHoles scaledUpX(const OtherNumber scalar) const {
        return scaledRings([scalar](const PolygonType& ring) { return ring.scaledUpX(scalar); });
    }

    template <class OtherNumber>
    constexpr void scaleUpX(const OtherNumber scalar) {
        auto saved = label_;
        *this = scaledUpX(scalar);
        label_ = std::move(saved);
    }

    template <class OtherNumber>
    [[nodiscard]] constexpr PolygonWithHoles scaledUpY(const OtherNumber scalar) const {
        return scaledRings([scalar](const PolygonType& ring) { return ring.scaledUpY(scalar); });
    }

    template <class OtherNumber>
    constexpr void scaleUpY(const OtherNumber scalar) {
        auto saved = label_;
        *this = scaledUpY(scalar);
        label_ = std::move(saved);
    }

    template <class OtherNumber>
    [[nodiscard]] constexpr PolygonWithHoles scaledDownX(const OtherNumber scalar) const {
        return scaledRings([scalar](const PolygonType& ring) { return ring.scaledDownX(scalar); });
    }

    template <class OtherNumber>
    constexpr void scaleDownX(const OtherNumber scalar) {
        auto saved = label_;
        *this = scaledDownX(scalar);
        label_ = std::move(saved);
    }

    template <class OtherNumber>
    [[nodiscard]] constexpr PolygonWithHoles scaledDownY(const OtherNumber scalar) const {
        return scaledRings([scalar](const PolygonType& ring) { return ring.scaledDownY(scalar); });
    }

    template <class OtherNumber>
    constexpr void scaleDownY(const OtherNumber scalar) {
        auto saved = label_;
        *this = scaledDownY(scalar);
        label_ = std::move(saved);
    }

    class VertexIterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using iterator_concept = std::forward_iterator_tag;
        using value_type = PointType;
        using difference_type = std::ptrdiff_t;
        using reference = value_type;
 
        constexpr VertexIterator() = default;
 
        constexpr value_type operator*() const {
            assert(region != nullptr);
            return currentRing()[index];
        }
 
        constexpr VertexIterator& operator++() {
            ++index;
            skipExhausted();
            return *this;
        }
 
        constexpr VertexIterator operator++(int) {
            VertexIterator copy(*this);
            ++(*this);
            return copy;
        }
 
        constexpr bool operator==(const VertexIterator& other) const = default;
 
      private:
        friend struct PolygonWithHoles;
 
        constexpr VertexIterator(const PolygonWithHoles* region_arg, std::size_t ring_arg)
            : region(region_arg), ring(ring_arg) {
            skipExhausted();
        }
 
        constexpr const PolygonType& currentRing() const {
            return ring == 0 ? region->outer_ : region->holes_[ring - 1];
        }
 
        // Steps over rings with no vertices, so `index` always addresses a real
        // vertex and the past-the-end state is exactly `ring == 1 + holes`.
        // Only an empty outer boundary can trigger this — addHole() drops
        // degenerate rings — but the guard costs nothing and keeps begin() and
        // end() comparing equal for a region with no vertices at all.
        constexpr void skipExhausted() {
            const std::size_t rings = region == nullptr ? 0 : 1 + region->holes_.size();
            while (ring < rings && index == currentRing().size()) {
                ++ring;
                index = 0;
            }
        }
 
        const PolygonWithHoles* region = nullptr;
        std::size_t ring = 0;
        std::size_t index = 0;
    };
 
  private:
    template <class RingTransform>
    constexpr PolygonWithHoles scaledRings(RingTransform&& transform) const {
        PolygonWithHoles result;
        result.outer_ = transform(outer_);
        result.holes_.reserve(holes_.size());
        for (const auto& hole : holes_) {
            result.holes_.push_back(transform(hole));
        }
        result.normalize();
        return result;
    }

    template <class EdgePredicate>
    constexpr bool anyBoundaryEdge(EdgePredicate&& predicate) const {
        for (const auto& edge : outer_.edgesView()) {
            if (predicate(edge)) {
                return true;
            }
        }
        for (const auto& hole : holes_) {
            for (const auto& edge : hole.edgesView()) {
                if (predicate(edge)) {
                    return true;
                }
            }
        }
        return false;
    }

    template <class OtherLinear, class ContactNumber>
    constexpr bool linearInteriorsIntersect(const OtherLinear& other,
                                            std::vector<Point<ContactNumber>> contacts,
                                            const Point<ContactNumber>& tail,
                                            const Point<ContactNumber>& head) const;

    constexpr bool isSolidVertex(const PointType& vertex) const;

    template <class OtherArea>
    constexpr bool outerInteriorContains(const OtherArea& other) const;

    template <class OtherArea>
    constexpr bool areaContains(const OtherArea& other) const;

    template <class OtherArea>
    constexpr bool areaInteriorContains(const OtherArea& other) const;

    template <class OtherArea>
    constexpr bool areaBoundaryContains(const OtherArea& other) const;

    template <class OtherArea>
    constexpr bool areaIntersects(const OtherArea& other) const;

    template <class OtherArea>
    bool areaInteriorsIntersect(const OtherArea& other) const;

    template <class OtherChain, class EdgeRelation>
    constexpr bool chainRelation(const OtherChain& other, bool all, EdgeRelation&& relation) const;

    template <class OtherIntersection>
    static constexpr auto asConvexOperand(const OtherIntersection& other);

    template <class OtherIntersection, class Relation>
    constexpr bool degenerateIntersectionRelation(const OtherIntersection& other,
                                                  Relation&& relation) 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;
 
    PolygonType outer_{};
    std::vector<PolygonType> holes_{};
    [[no_unique_address]] mutable LabelType label_{};
 
    // Memoized hash, computed lazily by std::hash<PolygonWithHoles>, with the
    // same sentinel scheme as Polygon: hashUnset_ means "not yet computed", and
    // the one true hash colliding with it is remapped so the sentinel is never
    // stored as a real value.
    static constexpr std::size_t hashUnset_ = pgl::detail::numeric_limits<std::size_t>::max();
    mutable std::size_t hash_ = hashUnset_;
    friend struct std::hash<PolygonWithHoles>;
 
    template <class OtherPointType, class OtherLabelType>
    friend struct PolygonWithHoles;
 
    constexpr void resetCache() const {
        hash_ = hashUnset_;
    }

    constexpr void normalize() {
        std::erase_if(holes_, [](const PolygonType& hole) { return hole.isDegenerate(); });
        std::sort(holes_.begin(), holes_.end());
        resetCache();
    }
};
 
// `region + point` is the translating Minkowski sum, spelled by the generic
// operator+ in implementation/minkowski.hpp like every other shape's: writing a
// second one here would shadow it and, holding the region's own point type,
// would silently truncate a translation that does not fit it.

template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto operator-(const PolygonWithHoles<PointType, LabelType>& region,
                         const Point<TranslationNumber, TranslationLabel>& translation) {
    return region + (-translation);
}
 
template <class PointType, class LabelType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const PolygonWithHoles<PointType, LabelType>& region, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() * scalar), typename PointType::LabelType>;
    PolygonWithHoles<ResultPointType, LabelType> result(region);
    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 PolygonWithHoles<PointType, LabelType>& region) {
    return region * scalar;
}
 
template <class PointType, class LabelType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator/(const PolygonWithHoles<PointType, LabelType>& region, const Scalar& scalar) {
    using ResultPointType = Point<decltype(std::declval<PointType>().x() / scalar), typename PointType::LabelType>;
    PolygonWithHoles<ResultPointType, LabelType> result(region);
    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 PolygonWithHoles<PointType, LabelType>& region);
 
}  // namespace pgl