shape.hpp

Go to the documentation of this file.

#pragma once
 
#include "shape/polygonset.hpp"

 
#include <compare>
#include <concepts>
#include <functional>
#include <optional>
#include <ostream>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
 
 
namespace pgl {
 
namespace detail {
 
template <class PointType, class T>
struct is_shape_alternative : std::false_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, EmptyShape<PointType>> : std::true_type {};
 
template <class PointType, class Number, class Label>
struct is_shape_alternative<PointType, Point<Number, Label>> : std::bool_constant<std::same_as<PointType, Point<Number, Label>>> {};
 
template <class PointType, class Label>
struct is_shape_alternative<PointType, Segment<PointType, Label>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, OrientedSegment<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Line<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, OrientedLine<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Ray<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Halfplane<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Rectangle<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Triangle<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Convex<PointType>> : std::true_type {};
 
template <class PointType, class Label>
struct is_shape_alternative<PointType, Disk<PointType, Label>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, MonotoneChain<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Polyline<PointType>> : std::true_type {};
 
template <class PointType>
struct is_shape_alternative<PointType, Polygon<PointType>> : std::true_type {};
 
template <class PointType, class Label>
struct is_shape_alternative<PointType, HalfplaneIntersection<PointType, Label>> : std::true_type {};
 
template <class PointType, class Label>
struct is_shape_alternative<PointType, PolygonWithHoles<PointType, Label>> : std::true_type {};
 
template <class PointType, class Label>
struct is_shape_alternative<PointType, PolygonSet<PointType, Label>> : std::true_type {};
 
template <class PointType, class T>
inline constexpr bool is_shape_alternative_v = is_shape_alternative<PointType, std::remove_cvref_t<T>>::value;
 
template <class PointType, class T>
concept ShapeAlternative = is_shape_alternative_v<PointType, T>;
 
// Minimal shape detectors for the standard wrappers an intersection may return.
template <class T>
struct is_std_optional : std::false_type {};
template <class T>
struct is_std_optional<std::optional<T>> : std::true_type {};
 
template <class T>
struct is_std_vector : std::false_type {};
template <class T, class A>
struct is_std_vector<std::vector<T, A>> : std::true_type {};
 
template <class T>
struct is_std_variant : std::false_type {};
template <class... Ts>
struct is_std_variant<std::variant<Ts...>> : std::true_type {};
 
// True iff T is a std::variant whose every alternative is a supported shape for
// PointType. Gates the variant-unwrapping Shape constructor so a variant that
// could hold a non-shape is rejected at compile time.
template <class PointType, class T>
struct is_shape_variant : std::false_type {};
 
template <class PointType, class... Ts>
struct is_shape_variant<PointType, std::variant<Ts...>>
    : std::bool_constant<(is_shape_alternative_v<PointType, Ts> && ...)> {};
 
template <class PointType, class T>
inline constexpr bool is_shape_variant_v = is_shape_variant<PointType, std::remove_cvref_t<T>>::value;
 
// True iff T is a std::optional wrapping such a shape variant.
template <class PointType, class T>
struct is_shape_optional_variant : std::false_type {};
 
template <class PointType, class V>
struct is_shape_optional_variant<PointType, std::optional<V>>
    : std::bool_constant<is_shape_variant_v<PointType, V>> {};
 
template <class PointType, class T>
inline constexpr bool is_shape_optional_variant_v =
    is_shape_optional_variant<PointType, std::remove_cvref_t<T>>::value;
 
// Point type carried by a shape alternative: a Point is its own point type;
// every other alternative exposes it as a nested PointType. Used by the Shape
// deduction guides to recover the wrapper's point type from a result variant.
template <class T>
struct shape_point_type {
    using type = typename T::PointType;
};
 
template <class Number, class Label>
struct shape_point_type<Point<Number, Label>> {
    using type = Point<Number, Label>;
};
 
template <class T>
using shape_point_type_t = typename shape_point_type<T>::type;
 
}  // namespace detail

template <class PointType = Point<>>
struct Shape {
    using PointType_ = PointType;
    using NumberType = PointType::NumberType;
    using LabelType = PointType::LabelType;
    using Variant = std::variant<
        EmptyShape<PointType>,
        PointType,
        Segment<PointType>,
        OrientedSegment<PointType>,
        Line<PointType>,
        OrientedLine<PointType>,
        Ray<PointType>,
        Halfplane<PointType>,
        Rectangle<PointType>,
        Triangle<PointType>,
        Disk<PointType>,
        Convex<PointType>,
        MonotoneChain<PointType>,
        Polyline<PointType>,
        Polygon<PointType>,
        HalfplaneIntersection<PointType>,
        PolygonWithHoles<PointType>,
        PolygonSet<PointType>>;

    constexpr Shape() = default;

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr Shape(T&& value)
        : value_(std::forward<T>(value)) {}

    template <class Result>
        requires(detail::is_shape_variant_v<PointType, Result> ||
                 detail::is_shape_optional_variant_v<PointType, Result>)
    constexpr Shape(const Result& result) {
        if constexpr (detail::is_shape_optional_variant_v<PointType, Result>) {
            if (result) {
                *this = Shape(*result);
            }
        } else {
            std::visit(
                [this](const auto& alternative) { *this = Shape(alternative); }, result);
        }
    }

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr Shape& operator=(T&& value) {
        value_ = std::forward<T>(value);
        return *this;
    }

    constexpr bool operator==(const Shape&) const = default;

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

    constexpr auto operator<=>(const Shape&) const = default;

    constexpr const Variant& variant() const {
        return value_;
    }

    constexpr Variant& variant() {
        return value_;
    }

    [[nodiscard]] constexpr bool empty() const {
        return std::visit([](const auto& value) { return detail::coversNoPoint(value); },
                          value_);
    }

    [[nodiscard]] constexpr bool isDegenerate() const {
        return std::visit(
            [](const auto& value) {
                if constexpr (requires { value.isDegenerate(); }) {
                    return value.isDegenerate();
                } else {
                    return false;
                }
            },
            value_);
    }

    [[nodiscard]] constexpr Rectangle<PointType> bbox() const {
        return std::visit(
            [](const auto& value) -> Rectangle<PointType> {
                if constexpr (requires { value.template bbox<NumberType>(); }) {
                    return value.template bbox<NumberType>();
                } else if constexpr (requires { value.bbox(); }) {
                    return value.bbox();
                } else {
                    throw std::logic_error("Shape::bbox is not defined for this unbounded alternative");
                }
            },
            value_);
    }

    [[nodiscard]] constexpr std::size_t size() const {
        return std::visit(
            [](const auto& value) -> std::size_t {
                using S = std::decay_t<decltype(value)>;
                if constexpr (detail::is_polygon_with_holes_v<S>) {
                    throw std::logic_error("Shape::size is not defined for the PolygonWithHoles alternative");
                } else if constexpr (detail::is_polygon_set_v<S>) {
                    throw std::logic_error("Shape::size is not defined for the PolygonSet alternative");
                } else {
                    return value.size();
                }
            },
            value_);
    }

    [[nodiscard]] constexpr PointType_ get(std::ptrdiff_t index) const {
        return std::visit(
            [index](const auto& value) -> PointType_ {
                using S = std::decay_t<decltype(value)>;
                if constexpr (std::same_as<S, PointType_>) {
                    throw std::logic_error("Shape::get is not defined for the Point alternative");
                } else if constexpr (detail::is_halfplane_intersection_v<S>) {
                    throw std::logic_error("Shape::get is not defined for the HalfplaneIntersection alternative");
                } else if constexpr (detail::is_polygon_with_holes_v<S>) {
                    throw std::logic_error("Shape::get is not defined for the PolygonWithHoles alternative");
                } else if constexpr (detail::is_polygon_set_v<S>) {
                    throw std::logic_error("Shape::get is not defined for the PolygonSet alternative");
                } else {
                    return value.get(index);
                }
            },
            value_);
    }

    [[nodiscard]] constexpr PointType_ operator[](std::size_t index) const {
        return std::visit(
            [index](const auto& value) -> PointType_ {
                using S = std::decay_t<decltype(value)>;
                if constexpr (std::same_as<S, PointType_>) {
                    throw std::logic_error("Shape::operator[] is not defined for the Point alternative");
                } else if constexpr (detail::is_halfplane_intersection_v<S>) {
                    throw std::logic_error("Shape::operator[] is not defined for the HalfplaneIntersection alternative");
                } else if constexpr (detail::is_polygon_with_holes_v<S>) {
                    throw std::logic_error("Shape::operator[] is not defined for the PolygonWithHoles alternative");
                } else if constexpr (detail::is_polygon_set_v<S>) {
                    throw std::logic_error("Shape::operator[] is not defined for the PolygonSet alternative");
                } else {
                    return value[index];
                }
            },
            value_);
    }

    [[nodiscard]] constexpr std::ptrdiff_t index(const PointType_& point) const {
        return std::visit(
            [&point](const auto& value) -> std::ptrdiff_t {
                using S = std::decay_t<decltype(value)>;
                if constexpr (std::same_as<S, PointType_>) {
                    throw std::logic_error("Shape::index(Point) is not defined for the Point alternative");
                } else if constexpr (detail::is_halfplane_intersection_v<S>) {
                    throw std::logic_error("Shape::index(Point) is not defined for the HalfplaneIntersection alternative");
                } else if constexpr (detail::is_polygon_with_holes_v<S>) {
                    throw std::logic_error("Shape::index(Point) is not defined for the PolygonWithHoles alternative");
                } else if constexpr (detail::is_polygon_set_v<S>) {
                    throw std::logic_error("Shape::index(Point) is not defined for the PolygonSet alternative");
                } else {
                    return value.index(point);
                }
            },
            value_);
    }

    [[nodiscard]] constexpr std::ptrdiff_t index(const NumberType& value) const {
        return std::visit(
            [&value](const auto& shape) -> std::ptrdiff_t {
                using S = std::decay_t<decltype(shape)>;
                if constexpr (std::same_as<S, PointType_>) {
                    return shape.index(value);
                } else {
                    throw std::logic_error("Shape::index(NumberType) is only defined for the Point alternative");
                }
            },
            value_);
    }

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr bool holdsAlternative() const {
        return std::holds_alternative<std::remove_cvref_t<T>>(value_);
    }

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr const std::remove_cvref_t<T>* getIf() const {
        return std::get_if<std::remove_cvref_t<T>>(&value_);
    }

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr std::remove_cvref_t<T>* getIf() {
        return std::get_if<std::remove_cvref_t<T>>(&value_);
    }

// The doc comments below are part of the expansion on purpose: a description on
// the enclosing @name group documents the group, not its members, which would
// leave all 51 generated methods without a @brief of their own.
#define PGL_SHAPE_ALTERNATIVE(Name, Type)                        \
  \
    [[nodiscard]] constexpr bool is##Name() const {              \
        return std::holds_alternative<Type>(value_);             \
    }                                                            \
                   \
    [[nodiscard]] constexpr const Type* getIf##Name() const {    \
        return std::get_if<Type>(&value_);                       \
    }                                                            \
                   \
    [[nodiscard]] constexpr Type* getIf##Name() {                \
        return std::get_if<Type>(&value_);                       \
    }
 
    PGL_SHAPE_ALTERNATIVE(Point, PointType)
    PGL_SHAPE_ALTERNATIVE(Segment, Segment<PointType>)
    PGL_SHAPE_ALTERNATIVE(OrientedSegment, OrientedSegment<PointType>)
    PGL_SHAPE_ALTERNATIVE(Line, Line<PointType>)
    PGL_SHAPE_ALTERNATIVE(OrientedLine, OrientedLine<PointType>)
    PGL_SHAPE_ALTERNATIVE(Ray, Ray<PointType>)
    PGL_SHAPE_ALTERNATIVE(Halfplane, Halfplane<PointType>)
    PGL_SHAPE_ALTERNATIVE(Rectangle, Rectangle<PointType>)
    PGL_SHAPE_ALTERNATIVE(Triangle, Triangle<PointType>)
    PGL_SHAPE_ALTERNATIVE(Disk, Disk<PointType>)
    PGL_SHAPE_ALTERNATIVE(Convex, Convex<PointType>)
    PGL_SHAPE_ALTERNATIVE(MonotoneChain, MonotoneChain<PointType>)
    PGL_SHAPE_ALTERNATIVE(Polyline, Polyline<PointType>)
    PGL_SHAPE_ALTERNATIVE(Polygon, Polygon<PointType>)
    PGL_SHAPE_ALTERNATIVE(HalfplaneIntersection, HalfplaneIntersection<PointType>)
    PGL_SHAPE_ALTERNATIVE(PolygonWithHoles, PolygonWithHoles<PointType>)
    PGL_SHAPE_ALTERNATIVE(PolygonSet, PolygonSet<PointType>)
 
#undef PGL_SHAPE_ALTERNATIVE

    template <class T>
        requires(detail::ShapeAlternative<PointType, T>)
    constexpr explicit operator T() const {
        return std::get<std::remove_cvref_t<T>>(value_);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool contains(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.contains(right); }) {
                    return left.contains(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool boundaryContains(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.boundaryContains(right); }) {
                    return left.boundaryContains(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool interiorContains(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.interiorContains(right); }) {
                    return left.interiorContains(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool intersects(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.intersects(right); }) {
                    return left.intersects(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool interiorsIntersect(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.interiorsIntersect(right); }) {
                    return left.interiorsIntersect(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool separates(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.separates(right); }) {
                    return left.separates(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr bool crosses(const Other& other) const {
        return applyPredicate(
            [](const auto& left, const auto& right) {
                if constexpr (requires { left.crosses(right); }) {
                    return left.crosses(right);
                } else {
                    return false;
                }
            },
            other);
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr Shape<Point<ResultNumber, LabelType>> intersection(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return intersectionOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return intersectionOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    [[nodiscard]] PolygonSet<Point<ResultNumber, LabelType>> regularizedIntersection(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return regularizedIntersectionOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return regularizedIntersectionOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    [[nodiscard]] PolygonSet<Point<ResultNumber, LabelType>> regularizedUnion(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return regularizedUnionOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return regularizedUnionOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    [[nodiscard]] PolygonSet<Point<ResultNumber, LabelType>> difference(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return differenceOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return differenceOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    [[nodiscard]] PolygonSet<Point<ResultNumber, LabelType>> symmetricDifference(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return symmetricDifferenceOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return symmetricDifferenceOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = double, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber squaredDistance(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return squaredDistanceOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return squaredDistanceOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber squaredHausdorffDistance(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return squaredHausdorffDistanceOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return squaredHausdorffDistanceOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = double, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber distanceL1(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return distanceL1Of<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return distanceL1Of<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = double, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber distanceLInf(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return distanceLInfOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return distanceLInfOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber hausdorffDistanceL1(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return hausdorffDistanceL1Of<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return hausdorffDistanceL1Of<ResultNumber>(left, other);
                },
                value_);
        }
    }

    template <class ResultNumber = division_result_t<NumberType>, class Other>
        requires(std::same_as<std::remove_cvref_t<Other>, Shape> || detail::ShapeAlternative<PointType, Other>)
    constexpr ResultNumber hausdorffDistanceLInf(const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [](const auto& left, const auto& right) {
                    return hausdorffDistanceLInfOf<ResultNumber>(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&other](const auto& left) {
                    return hausdorffDistanceLInfOf<ResultNumber>(left, other);
                },
                value_);
        }
    }

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

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

     */
    template <PointConcept OtherPoint>
    constexpr Shape& operator+=(const OtherPoint& translation) {
        std::visit([&translation](auto& alternative) { alternative += translation; }, value_);
        return *this;
    }

     */
    template <PointConcept OtherPoint>
    constexpr Shape& operator-=(const OtherPoint& translation) {
        std::visit([&translation](auto& alternative) { alternative -= translation; }, value_);
        return *this;
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr Shape& operator*=(const Scalar& scalar) {
        std::visit([&scalar](auto& alternative) { alternative *= scalar; }, value_);
        return *this;
    }

    template <class Scalar>
        requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
    constexpr Shape& operator/=(const Scalar& scalar) {
        std::visit([&scalar](auto& alternative) { alternative /= scalar; }, value_);
        return *this;
    }

     * @return Rotated shape, preserving the stored alternative type.
     */
    [[nodiscard]] constexpr Shape rotated90(int k = 1) const {
        return std::visit(
            [k](const auto& value) -> Shape { return Shape(value.rotated90(k)); },
            value_);
    }

     * @param k Number of 90-degree CCW rotations (may be negative).
     */
    constexpr void rotate90(int k = 1) {
        std::visit([k](auto& value) { value.rotate90(k); }, value_);
    }

     */
    template <class OtherNumber>
    [[nodiscard]] constexpr Shape scaledUpX(const OtherNumber scalar) const {
        return std::visit(
            [scalar](const auto& value) -> Shape {
                if constexpr (requires { value.scaledUpX(scalar); }) {
                    return Shape(value.scaledUpX(scalar));
                } else {
                    throw std::logic_error("Shape::scaledUpX is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    constexpr void scaleUpX(const OtherNumber scalar) {
        std::visit(
            [scalar](auto& value) {
                if constexpr (requires { value.scaleUpX(scalar); }) {
                    value.scaleUpX(scalar);
                } else {
                    throw std::logic_error("Shape::scaleUpX is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    [[nodiscard]] constexpr Shape scaledUpY(const OtherNumber scalar) const {
        return std::visit(
            [scalar](const auto& value) -> Shape {
                if constexpr (requires { value.scaledUpY(scalar); }) {
                    return Shape(value.scaledUpY(scalar));
                } else {
                    throw std::logic_error("Shape::scaledUpY is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    constexpr void scaleUpY(const OtherNumber scalar) {
        std::visit(
            [scalar](auto& value) {
                if constexpr (requires { value.scaleUpY(scalar); }) {
                    value.scaleUpY(scalar);
                } else {
                    throw std::logic_error("Shape::scaleUpY is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    [[nodiscard]] constexpr Shape scaledDownX(const OtherNumber scalar) const {
        return std::visit(
            [scalar](const auto& value) -> Shape {
                if constexpr (requires { value.scaledDownX(scalar); }) {
                    return Shape(value.scaledDownX(scalar));
                } else {
                    throw std::logic_error("Shape::scaledDownX is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    constexpr void scaleDownX(const OtherNumber scalar) {
        std::visit(
            [scalar](auto& value) {
                if constexpr (requires { value.scaleDownX(scalar); }) {
                    value.scaleDownX(scalar);
                } else {
                    throw std::logic_error("Shape::scaleDownX is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    [[nodiscard]] constexpr Shape scaledDownY(const OtherNumber scalar) const {
        return std::visit(
            [scalar](const auto& value) -> Shape {
                if constexpr (requires { value.scaledDownY(scalar); }) {
                    return Shape(value.scaledDownY(scalar));
                } else {
                    throw std::logic_error("Shape::scaledDownY is not defined for the Disk alternative");
                }
            },
            value_);
    }

     */
    template <class OtherNumber>
    constexpr void scaleDownY(const OtherNumber scalar) {
        std::visit(
            [scalar](auto& value) {
                if constexpr (requires { value.scaleDownY(scalar); }) {
                    value.scaleDownY(scalar);
                } else {
                    throw std::logic_error("Shape::scaleDownY is not defined for the Disk alternative");
                }
            },
            value_);
    }
 
  private:
    template <class Dispatch, class Other>
    constexpr bool applyPredicate(Dispatch dispatch, const Other& other) const {
        if constexpr (detail::is_shape_v<Other>) {
            return std::visit(
                [&dispatch](const auto& left, const auto& right) {
                    return dispatch(left, right);
                },
                value_,
                other.variant());
        } else {
            return std::visit(
                [&dispatch, &other](const auto& self) {
                    return dispatch(self, other);
                },
                value_);
        }
    }
 
    // Intersect two unwrapped alternatives and wrap the result as a Shape over
    // the result point type. The empty set on either side gives the empty shape;
    // otherwise the pair is dispatched to the concrete `intersection` when one
    // exists. Thanks to the rank-constrained fallbacks, the `requires` probe is
    // SFINAE-safe and self-maintaining: a pair with no intersection (Disk, or
    // two shapes neither of which implements the other) simply takes the throw.
    template <class ResultNumber, class Left, class Right>
    static constexpr Shape<Point<ResultNumber, LabelType>> intersectionOf(const Left& left, const Right& right) {
        using ResultPoint = Point<ResultNumber, LabelType>;
        if constexpr (std::same_as<Left, EmptyShape<PointType>> ||
                      std::same_as<Right, EmptyShape<PointType>>) {
            return Shape<ResultPoint>{EmptyShape<ResultPoint>{}};
        } else if constexpr (requires { left.template intersection<ResultNumber>(right); }) {
            return resultToShape<ResultNumber>(left.template intersection<ResultNumber>(right));
        } else {
            throw std::logic_error("Shape::intersection is not defined for this shape pair");
        }
    }
 
    // Compute a regularized region intersection. Unlike literal intersection,
    // the empty shape is not a specially supported operand: this dispatcher
    // mirrors the concrete regularizedIntersection overload grid exactly.
    template <class ResultNumber, class Left, class Right>
    static PolygonSet<Point<ResultNumber, LabelType>> regularizedIntersectionOf(
        const Left& left, const Right& right) {
        if constexpr (requires { left.template regularizedIntersection<ResultNumber>(right); }) {
            return left.template regularizedIntersection<ResultNumber>(right);
        } else {
            throw std::logic_error(
                "Shape::regularizedIntersection is not defined for this shape pair");
        }
    }
 
    // Unite two unwrapped alternatives. The probe is SFINAE-safe and
    // self-maintaining in the same way intersectionOf's is, and here it lands
    // exactly on the pairs of bounded polygonal regions: those define
    // regularizedUnion for every ordered pair between them, each on the
    // higher-ranked operand with the lower-ranked one forwarding, and nothing
    // else defines it at all.
    //
    // There is no EmptyShape short circuit as there is above. The empty set is
    // the identity of a union rather than its absorber, so `empty ∪ A` would have
    // to answer with A itself — which is only a PolygonSet when A is a region,
    // and would then be a special case reachable no other way. It takes the
    // throw with everything else instead.
    template <class ResultNumber, class Left, class Right>
    static PolygonSet<Point<ResultNumber, LabelType>> regularizedUnionOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template regularizedUnion<ResultNumber>(right); }) {
            return left.template regularizedUnion<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::regularizedUnion is not defined for this shape pair");
        }
    }
 
    // Remove one unwrapped alternative from another, and take the same
    // regularized parts as the two above. The probe lands on the same grid of
    // bounded polygonal regions regularizedUnionOf's does, but by a different
    // route: a difference is not symmetric, so nothing forwards, and every one
    // of the thirty-six ordered pairs is stated on its own receiver.
    //
    // The empty set is no more a special case here than it is above, and for a
    // sharper reason: `A ∖ empty` is A, which is a PolygonSet only when A is a
    // region, and `empty ∖ A` is the empty shape rather than the empty set of
    // regions. Both take the throw.
    template <class ResultNumber, class Left, class Right>
    static PolygonSet<Point<ResultNumber, LabelType>> differenceOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template difference<ResultNumber>(right); }) {
            return left.template difference<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::difference is not defined for this shape pair");
        }
    }
 
    // The symmetric difference of two unwrapped alternatives, probed as above.
    template <class ResultNumber, class Left, class Right>
    static PolygonSet<Point<ResultNumber, LabelType>> symmetricDifferenceOf(const Left& left,
                                                                            const Right& right) {
        if constexpr (requires { left.template symmetricDifference<ResultNumber>(right); }) {
            return left.template symmetricDifference<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::symmetricDifference is not defined for this shape pair");
        }
    }
 
    // Measure the squared distance between two unwrapped alternatives. A pair with
    // no defined squaredDistance (anything against an EmptyShape) takes the throw.
    // The requires probes are SFINAE-safe and self-maintaining: a pair gains
    // support here as soon as either side implements squaredDistance for the
    // other (directly or via forwarding).
    //
    // Both probes convert explicitly, because a pair involving a Disk answers in
    // detail::floating_result_t<ResultNumber> rather than in ResultNumber itself
    // — an exact request cannot be honoured for a distance realized on a circle.
    // That conversion is the point at which an exact caller learns it is getting
    // a rounded answer, and it is why the cast cannot be left implicit: Rational
    // is only explicitly constructible from a floating-point value.
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber squaredDistanceOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template squaredDistance<ResultNumber>(right); }) {
            return static_cast<ResultNumber>(left.template squaredDistance<ResultNumber>(right));
        } else if constexpr (requires { left.squaredDistance(right); }) {
            return static_cast<ResultNumber>(left.squaredDistance(right));
        } else {
            throw std::logic_error("Shape::squaredDistance is not defined for this shape pair");
        }
    }
 
    // Measure the squared Hausdorff distance between two unwrapped alternatives.
    // Defined only for Point, Segment, OrientedSegment, Rectangle, Triangle, and
    // Convex, so any other pair (including anything against Line, OrientedLine,
    // Ray, Halfplane, Disk, MonotoneChain, Polyline, Polygon, or EmptyShape)
    // takes the throw. Unlike
    // squaredDistance there is no untemplated double-returning overload to probe
    // for: Disk has no squaredHausdorffDistance at all.
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber squaredHausdorffDistanceOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template squaredHausdorffDistance<ResultNumber>(right); }) {
            return left.template squaredHausdorffDistance<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::squaredHausdorffDistance is not defined for this shape pair");
        }
    }
 
    // Measure the L1 distance between two unwrapped alternatives. Every
    // supported concrete overload accepts ResultNumber; an EmptyShape or a Disk
    // paired with anything but a Point takes the throw. Convert explicitly for
    // the reason given on squaredDistanceOf: a Disk pair answers in a floating
    // type.
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber distanceL1Of(const Left& left, const Right& right) {
        if constexpr (requires { left.template distanceL1<ResultNumber>(right); }) {
            return static_cast<ResultNumber>(left.template distanceL1<ResultNumber>(right));
        } else {
            throw std::logic_error("Shape::distanceL1 is not defined for this shape pair");
        }
    }
 
    // LInf counterpart of distanceL1Of.
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber distanceLInfOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template distanceLInf<ResultNumber>(right); }) {
            return static_cast<ResultNumber>(left.template distanceLInf<ResultNumber>(right));
        } else {
            throw std::logic_error("Shape::distanceLInf is not defined for this shape pair");
        }
    }
 
    // Measure the L1 Hausdorff distance between two unwrapped alternatives.
    // Defined only for Point, Segment, OrientedSegment, Rectangle, Triangle, and
    // Convex (same coverage as squaredHausdorffDistanceOf, and for the same
    // reason: Disk has no hausdorffDistanceL1 overload to probe for either).
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber hausdorffDistanceL1Of(const Left& left, const Right& right) {
        if constexpr (requires { left.template hausdorffDistanceL1<ResultNumber>(right); }) {
            return left.template hausdorffDistanceL1<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::hausdorffDistanceL1 is not defined for this shape pair");
        }
    }
 
    // LInf counterpart of hausdorffDistanceL1Of; see there for the coverage.
    template <class ResultNumber, class Left, class Right>
    static constexpr ResultNumber hausdorffDistanceLInfOf(const Left& left, const Right& right) {
        if constexpr (requires { left.template hausdorffDistanceLInf<ResultNumber>(right); }) {
            return left.template hausdorffDistanceLInf<ResultNumber>(right);
        } else {
            throw std::logic_error("Shape::hausdorffDistanceLInf is not defined for this shape pair");
        }
    }
 
    // Unwrap a concrete intersection result (optional<T> or vector<T>, where T is
    // a single alternative or a variant over alternatives) into a Shape. An
    // absent/empty result is the empty shape; a disconnected result (more than
    // one component) cannot be a single Shape and throws. The actual wrapping of
    // a value or variant is handled by the Shape constructors.
    template <class ResultNumber, class Result>
    static constexpr Shape<Point<ResultNumber, LabelType>> resultToShape(const Result& result) {
        using ResultShape = Shape<Point<ResultNumber, LabelType>>;
        if constexpr (detail::is_std_optional<Result>::value) {
            return result ? ResultShape(*result) : ResultShape{};
        } else if constexpr (detail::is_std_vector<Result>::value) {
            if (result.size() > 1) {
                throw std::logic_error(
                    "Shape::intersection: disconnected result cannot be a single Shape");
            }
            return result.empty() ? ResultShape{} : ResultShape(result.front());
        } else if constexpr (detail::is_polygon_set_v<Result>) {
            // A set of regions is an alternative of its own, so unlike a vector
            // it survives coming apart. A single component is still unwrapped to
            // the tighter `PolygonWithHoles` alternative, which is the answer
            // this pair has always given when the intersection stayed in one
            // piece.
            if (result.empty()) {
                return ResultShape{};
            }
            return result.componentCount() == 1 ? ResultShape(result.component(0))
                                                : ResultShape(result);
        } else {
            return ResultShape(result);
        }
    }
 
    Variant value_{};
};
 
// Deduce the wrapper's point type from the alternatives of a result variant (or
// an optional thereof), so `Shape s = a.intersection<N>(b);` names the right
// type. The point type is taken from the variant's first alternative; every
// alternative shares it.
template <class T, class... Ts>
Shape(const std::variant<T, Ts...>&) -> Shape<detail::shape_point_type_t<T>>;
 
template <class T, class... Ts>
Shape(const std::optional<std::variant<T, Ts...>>&) -> Shape<detail::shape_point_type_t<T>>;

 */
template <class PointType, class TranslationNumber, class TranslationLabel>
constexpr auto operator-(const Shape<PointType>& shape,
                         const Point<TranslationNumber, TranslationLabel>& translation) {
    using ResultPoint = std::decay_t<decltype(std::declval<const PointType&>() - translation)>;
    return std::visit(
        [&translation](const auto& alternative) {
            return Shape<ResultPoint>(alternative - translation);
        },
        shape.variant());
}

template <class PointType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const Shape<PointType>& shape, const Scalar& scalar) {
    using ResultPoint = std::decay_t<decltype(std::declval<const PointType&>() * scalar)>;
    return std::visit(
        [&scalar](const auto& alternative) {
            return Shape<ResultPoint>(alternative * scalar);
        },
        shape.variant());
}

template <class Scalar, class PointType>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator*(const Scalar& scalar, const Shape<PointType>& shape) {
    return shape * scalar;
}

template <class PointType, class Scalar>
    requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto operator/(const Shape<PointType>& shape, const Scalar& scalar) {
    using ResultPoint = std::decay_t<decltype(std::declval<const PointType&>() / scalar)>;
    return std::visit(
        [&scalar](const auto& alternative) {
            return Shape<ResultPoint>(alternative / scalar);
        },
        shape.variant());
}

 */
template <class PointType>
std::ostream& operator<<(std::ostream& stream, const Shape<PointType>& shape) {
    std::visit(
        [&stream](const auto& value) {
            stream << value;
        },
        shape.variant());
    return stream;
}
 
}  // namespace pgl