intersects.hpp

Go to the documentation of this file.

#pragma once
 
#include "implementation/interiorsintersect.hpp"

 
#include <limits>
#include "implementation/orientation.hpp"
#include "predicates_helpers.hpp"
 
 
namespace pgl {

 
template <class Number, class Label>
template<PointConcept OtherPoint>
constexpr bool Point<Number, Label>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
 
template <class Number, class Label>
constexpr bool Point<Number, Label>::intersects(const Shape<Point<Number, Label>>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Segment<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Segment<PointType, LabelType>::intersects(const OtherSegment& other) const {
    using Coordinate = detail::sign_coordinate_t<NumberType, typename OtherSegment::NumberType>;
 
    // A segment pair needs four orientation signs, but each of its four
    // endpoints occurs in three of them. Filtering the endpoints once has an
    // ERational-to-double conversion happen once per coordinate rather than
    // three times, and every sign the filter proves is one the exact arithmetic
    // below never evaluates. Where the filter would not pay for itself the
    // wrappers carry nothing but the points, and this is the plain sequence of
    // exact orientation tests.
    const auto a = detail::filtered<Coordinate>(min());
    const auto b = detail::filtered<Coordinate>(max());
    const auto c = detail::filtered<Coordinate>(other.min());
    const auto d = detail::filtered<Coordinate>(other.max());
    const auto s1 = detail::orientationSignOf(a, b, c);
    const auto s2 = detail::orientationSignOf(a, b, d);
    const auto s3 = detail::orientationSignOf(c, d, a);
    const auto s4 = detail::orientationSignOf(c, d, b);
 
    // Four proved signs are all nonzero and decide the predicate outright, so
    // they also spare the costly exact rational bounding-box comparisons.
    if (detail::allDecided(s1, s2, s3, s4)) {
        return s1.value() != s2.value() && s3.value() != s4.value();
    }
 
    if constexpr (is_Rational_v<NumberType> || is_Rational_v<typename OtherSegment::NumberType>) {
        const int cross = boundingBoxesCross(other);
        if (cross == 0) {
            return false;
        }
        if (cross == 2) {
            return true;
        }
    }
    else if (!boundingBoxesOverlap(other)) {
        return false;
    }
 
    // A possible zero always reaches here, so the closed-boundary checks stay
    // exact.
    const auto d1 = s1.value();
    if (d1 == 0 && containsCollinear(other.min())) {
        return true;
    }
    const auto d2 = s2.value();
    if (d2 == 0 && containsCollinear(other.max())) {
        return true;
    }
    const auto d3 = s3.value();
    if (d3 == 0 && other.containsCollinear(min())) {
        return true;
    }
    const auto d4 = s4.value();
    if (d4 == 0 && other.containsCollinear(max())) {
        return true;
    }
    if (d1 == 0 || d2 == 0 || d3 == 0 || d4 == 0) {
        return false;
    }
    return d1 != d2 && d3 != d4;
}
 
 
template <class PointType, class LabelType>
constexpr bool Segment<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    // The line meets the closed triangle unless all three vertices lie
    // strictly on one side of it.
    bool positive = false, negative = false;
    for (auto p : *this) {
        auto o = orientationSign(other[0], other[1], p);
        if (o == 0) {
            return true;
        }
        negative = (negative || o < 0);
        positive = (positive || o > 0);
        if (positive && negative) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(static_cast<Line<typename OtherOrientedLine::PointType>>(other));
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherSegment& other) const {
    // Either an endpoint lies in the closed triangle, or the segment crosses
    // one of the triangle's edges.
    if (contains(other.min()) || contains(other.max())) {
        return true;
    }
    for (const auto& edge : edges()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherRay& other) const {
    // Either the source lies in the closed triangle, or the ray crosses an edge.
    if (contains(other.source())) {
        return true;
    }
    for (const auto& edge : edges()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (other.contains(a()) || other.contains(b()) || other.contains(c())) {
        return true;
    }
    for (const auto& edge : edges()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    // Cheapest rejection first: the two bounding boxes must overlap. Without
    // it a rectangle off to one side still pays the corner containment below,
    // which the three edge tests can never short-circuit.
    if (!other.intersects(bbox())) {
        return false;
    }
    // Convex against convex. If no edge of the triangle meets the rectangle
    // then the rectangle, being connected, lies wholly inside the triangle or
    // wholly outside it, and one of its corners settles which. Going through
    // the vertex pairs rather than through 'edges()' keeps the three segments
    // from being built at all.
    return detail::segmentIntersectsRectangle(other, a(), b()) ||
           detail::segmentIntersectsRectangle(other, b(), c()) ||
           detail::segmentIntersectsRectangle(other, c(), a()) ||
           contains(other.min());
}
 
template <class PointType, class LabelType>
template<TriangleConcept OtherTriangle>
constexpr bool Triangle<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    if (contains(other.a()) || contains(other.b()) || contains(other.c()) ||
        other.contains(a()) || other.contains(b()) || other.contains(c())) {
        return true;
    }
    const auto this_edges = edges();
    const auto other_edges = other.edges();
    for (const auto& left : this_edges) {
        for (const auto& right : other_edges) {
            if (left.intersects(right)) {
                return true;
            }
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
constexpr bool Triangle<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool OrientedSegment<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return static_cast<Segment<PointType>>(*this).intersects(other);
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool OrientedSegment<PointType, LabelType>::intersects(const OtherSegment& other) const {
    return static_cast<Segment<PointType>>(*this).intersects(other);
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool OrientedSegment<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return static_cast<Segment<PointType>>(*this).intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
 
template <class PointType, class LabelType>
constexpr bool OrientedSegment<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Line<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Line<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (isDegenerate()) {
        return other.contains(min());
    }
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    return !parallel(other) || contains(other.min());
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Line<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    const auto first = orientationSign(min(), max(), other.min());
    const auto second = orientationSign(min(), max(), other.max());
    return first == std::partial_ordering::equivalent ||
           second == std::partial_ordering::equivalent ||
           first != second;
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Line<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
constexpr bool Line<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const OtherLine& other) const {
    return this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return this->asLine().intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const OtherSegment& other) const {
    return this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
constexpr bool OrientedLine<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    const auto source_side = orientationSign(other.min(), other.max(), source());
    if (source_side == 0) {
        return true;  // source lies on the line
    }
    // As the ray runs to infinity it tends to the side given by its direction.
    // It meets the line exactly when that side is opposite the source's (a
    // forward crossing); parallel (equivalent) or same-side rays never reach it.
    const auto direction_side =
        orientationSign(other.min(), other.max(), other.min() + (target() - source()));
    return direction_side != 0 && direction_side != source_side;
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
 
    // A segment collinear with the ray satisfies both line-vs-line tests below
    // even when it does not overlap the ray, so handle it as a 1D overlap: they
    // meet iff the ray reaches an endpoint of the segment, or the segment covers
    // the ray's source.
    if (orientationSign(source(), target(), other.min()) == 0 &&
        orientationSign(source(), target(), other.max()) == 0) {
        return contains(other.min()) || contains(other.max()) || other.contains(source());
    }
 
    return intersects(other.asLine()) &&
           this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Ray<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    // Collinear rays both satisfy the line-vs-line test below even when they do
    // not overlap, so handle them as a 1D overlap: the rays meet iff one reaches
    // the other's source.
    if (orientationSign(source(), target(), other.source()) == 0 &&
        orientationSign(source(), target(), other.target()) == 0) {
        return contains(other.source()) || other.contains(source());
    }
    // Otherwise the supporting lines meet in at most one point; the rays meet
    // iff that point lies on both (each ray reaches the other's line).
    return intersects(other.asLine()) &&
           this->asLine().intersects(other);
}
 
template <class PointType, class LabelType>
constexpr bool Ray<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherPoint& other) const {
    // The empty set meets nothing, and it needs no case of its own: it contains
    // no point, so the test below is already false for it.
    return contains(other);
}
 
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    // The empty set meets nothing, and the inverted corners of an empty
    // rectangle can pass both interval tests, so emptiness has to be ruled out
    // before answering true. It trails the geometry rather than guarding the
    // function because false is the common answer, and that path then never
    // pays for the check.
    return intervalsOverlap(min().x(), max().x(), other.min().x(), other.max().x()) &&
           intervalsOverlap(min().y(), max().y(), other.min().y(), other.max().y()) &&
           !empty() && !other.empty();
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    return detail::lineIntersectsRectangle(*this, other.min(), other.max());
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    return detail::lineIntersectsRectangle(*this, other.source(), other.target());
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    return detail::segmentIntersectsRectangle(*this, other.min(), other.max());
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    return detail::segmentIntersectsRectangle(*this, other.source(), other.target());
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (contains(other.source())) {
        return true;
    }
    const auto rectangle_edges = edges();
    for (const auto& edge : rectangle_edges) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Rectangle<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    const auto rectangle_vertices = vertices();
    for (const auto& vertex : rectangle_vertices) {
        if (other.contains(vertex)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
constexpr bool Rectangle<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    // Not parallel to the boundary and the line must cross it; the parallel
    // test is the sign of the difference of the two endpoint determinants,
    // which is one cross product of the two directions.
    return crossSign(source(), target(), other.min(), other.max()) != 0 ||
           contains(other.min());
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    return crossSign(source(), target(), other.source(), other.target()) != 0 ||
           contains(other.source());
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    return contains(other.min()) || contains(other.max());
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    return contains(other.source()) || contains(other.target());
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (isDegenerate()) {
        return other.contains(source());
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    return !(orientationSign(source(), target(), other.source()) < 0) ||
           crossSign(source(), target(), other.source(), other.target()) > 0;
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Halfplane<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    // Crossing boundaries leave a wedge in both, and that wedge can lie
    // arbitrarily far from either boundary's two defining points, so the four
    // point tests below decide nothing here. They do decide the parallel case:
    // two parallel half-planes meet exactly when one boundary point lies in the
    // other half-plane, whether they are nested or face each other across a
    // slab.
    if (!isDegenerate() && !other.isDegenerate() && !asLine().parallel(other.asLine())) {
        return true;
    }
    return contains(other.source()) || contains(other.target()) || other.contains(source()) || other.contains(target());
}
 
template <class PointType, class LabelType>
constexpr bool Halfplane<PointType, LabelType>::intersects(const Shape<PointType>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
 
// ---------------------------------------------------------------------------
// Convex
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (size() == 0 || !bbox().intersects(other.bbox())) {
        return false;
    }
    if (contains(other.min()) || contains(other.max())) {
        return true;
    }
    auto translatedOther = other - translation_;
    auto it1 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[0], translatedOther[1], a);
    });
    auto it2 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[1], translatedOther[0], a);
    });
    Segment<PointType> s(*it1, *it2);
    return s.intersects(translatedOther);
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(Segment<typename OtherOrientedSegment::PointType>(other[0], other[1]));
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherLine& other) const {
    auto translatedOther = other - translation_;
    auto it1 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[0], translatedOther[1], a);
    });
    auto it2 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[1], translatedOther[0], a);
    });
    Segment<PointType> s(*it1, *it2);
    return s.intersects(translatedOther);
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(Line<typename OtherOrientedLine::PointType>(other[0], other[1]));
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (contains(other.source())) {
        return true;
    }
 
    auto translatedOther = other - translation_;
    auto it1 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[0], translatedOther[1], a);
    });
    auto it2 = detail::cyclicMaxOrPositive(points_.begin(), points_.end(), [&translatedOther](const PointType& a) {
        return orientationDeterminant(translatedOther[1], translatedOther[0], a);
    });
    Segment<PointType> s(*it1, *it2);
    return s.intersects(translatedOther);
}
 
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (size() == 0 || !bbox().intersects(other)) {
        return false;
    }
    if (bbox().separates(other) || other.separates(bbox())) {
        return true;
    }
 
    if (other.contains(points_[0])) {
        return true;
    }
 
    for (auto &edge : other.edges()) {
        if (intersects(edge)) {
            return true;
        }
    }
 
    return false;
}
 
template <class PointType, class LabelType>
template<TriangleConcept OtherTriangle>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    if (size() == 0 || !bbox().intersects(other)) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(bbox())) {
        return true;
    }
    if (other.contains(points_[0])) {
        return true;
    }
 
    for (auto &edge : other.edges()) {
        if (intersects(edge)) {
            return true;
        }
    }
 
    return false;
}
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherPoint& other) const {
    if (size() == 0) {
        return false;
    }
    return bbox().contains(other) && contains(other);
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (points_.empty()) {
        return false;
    }
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    // The vertex maximizing the inward orientation is the deepest into
    // the half-plane; if it is not in the closed half-plane, no other
    // vertex is either. The orientation determinant is unimodal along
    // the convex polygon's vertex sequence.
    const auto it = detail::cyclicMaxOrPositive(points_.begin(), points_.end(),
        [&other, this](const PointType& a) {
            return orientationDeterminant(other.source(), other.target(), a + translation_);
        });
    return other.contains(*it + translation_);
}
 
template <class PointType, class LabelType>
template<ConvexConcept OtherConvex>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherConvex& other) const {
    if (size() > other.size()) {
        return other.intersects(*this);
    }
    if (size() == 0 || other.size() == 0) {
        return false;
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(this->bbox())) {
        return true;
    }
 
    if (contains(other[0]) || other.contains((*this)[0])) {
        return true;
    }
 
    for (const auto& edge : edgesView()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
 
    return false;
}
 
template <class PointType, class LabelType>
template<DiskConcept OtherDisk>
constexpr bool Convex<PointType, LabelType>::intersects(const OtherDisk& other) const {
    if (contains(other[0])) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
// ---------------------------------------------------------------------------
// Disk
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (const auto point = getIfPoint()) {
        // A radius-zero disk is its centre; the in-circle formulation below
        // needs three non-collinear boundary points to be meaningful, and on
        // three equal ones every determinant vanishes and both of its tests
        // come out true.
        return other.contains(*point);
    }
    if (contains(other.min()) || contains(other.max())) {
        return true;
    }
 
    // Both endpoints lie strictly outside the closed disk, so the segment meets
    // the disk exactly when the perpendicular foot from the centre falls on the
    // segment *and* reaches inside it. This is decided exactly and without any
    // division (no centre/radius needed): writing power(p) = |p-center|^2 - r^2
    // for the in-circle determinant inCircleDeterminant(a,b,c,p) = -A*power(p),
    // with A = 2*signedArea(a,b,c), the quadratic power along the segment is
    // pinned by its endpoint values, so the centre never appears.
    //
    //   A  = orientation determinant of the three boundary points
    //   J0 = inCircleDeterminant(a,b,c, min), J1 = ... (a,b,c, max)
    //   L  = |max - min|^2,   M = L * A
    // Foot on the segment (t* in [0,1]): |(J0 - J1)*A| <= M*A   (M*A >= 0).
    // Foot reaches the disk (f(t*) <= 0): (J0 + J1 + M)^2 >= 4*J0*J1.
    // Reordering a,b,c flips A and every J together, leaving both tests intact.
    using W = detail::promoted_number_t<
        decltype(inCircleDeterminant(a(), b(), c(), other.min()))>;
 
    const W det = static_cast<W>(orientationDeterminant(a(), b(), c()));
    const W j0 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other.min()));
    const W j1 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other.max()));
    const W squared_length = other.min().template squaredDistance<W>(other.max());
    if (squared_length == W{}) {
        return false;  // Degenerate (point) segment whose sole point is outside.
    }
    const W m = squared_length * det;
 
    const W projection = (j0 - j1) * det;          // (J0 - J1) * A
    const W half_span = m * det;                   // M * A = L * A^2 >= 0
    const W discriminant_base = j0 + j1 + m;       // J0 + J1 + M
 
    const bool foot_on_segment = projection >= -half_span && projection <= half_span;
    const bool reaches_disk = discriminant_base * discriminant_base >= W{4} * j0 * j1;
 
    return foot_on_segment && reaches_disk;
}
 
template <class PointType, class LabelType>
template<DiskConcept OtherDisk>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherDisk& other) const {
    using R = std::conditional_t<
        std::is_floating_point_v<NumberType> ||
            std::is_floating_point_v<typename OtherDisk::NumberType>,
        long double,
        Rational<BigInt>>;
 
    const R d2 = center<R>().template squaredDistance<R>(other.template center<R>());
    const R r1_sq = squaredRadius<R>();
    const R r2_sq = other.template squaredRadius<R>();
 
    const R A = d2 - r1_sq - r2_sq;
    return A <= R{} || A * A <= R{4} * r1_sq * r2_sq;
}
 
template <class PointType, class LabelType>
template <PointConcept OtherPoint>
constexpr bool Convex<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
 
// ---------------------------------------------------------------------------
// Polygon
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherSegment& other) const {
    // Either an endpoint lies in the closed polygon, or the segment crosses
    // a boundary edge.
    if (contains(other.min()) || contains(other.max())) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    // The line meets the closed polygon unless every vertex is strictly on one
    // side: the boundary is connected, so vertices straddling the line force an
    // edge crossing (and a vertex on the line is itself an intersection).
    bool positive = false, negative = false;
    for (const auto& vertex : vertices()) {
        const auto o = orientationSign(other.min(), other.max(), vertex);
        if (o == 0) {
            return true;
        }
        negative = negative || o < 0;
        positive = positive || o > 0;
        if (positive && negative) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(static_cast<Line<typename OtherOrientedLine::PointType>>(other));
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (contains(other.source())) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    // The half-plane is convex, so it meets the polygon iff some vertex lies in
    // it; if every vertex is strictly outside, the whole polygon is too.
    for (const auto& vertex : vertices()) {
        if (other.contains(vertex)) {
            return true;
        }
    }
    return false;
}
 
// Two filled simple polygons meet iff a vertex of one lies in the other or a
// pair of their edges cross. The region overloads below all share this shape.
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (size() == 0) {
        return false;
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(bbox())) {
        return true;
    }
    if (other.contains((*this)[0]) || contains(other[0])) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<TriangleConcept OtherTriangle>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    if (size() == 0) {
        return false;
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(bbox())) {
        return true;
    }
    if (other.contains((*this)[0]) || contains(other[0])) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<ConvexConcept OtherConvex>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherConvex& other) const {
    if (size() == 0 || other.size() == 0) {
        return false;
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(this->bbox())) {
        return true;
    }
    if (other.contains((*this)[0]) || contains(other[0])) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<PolygonConcept OtherPolygon>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherPolygon& other) const {
    if (size() == 0 || other.size() == 0) {
        return false;
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    if (bbox().separates(other.bbox()) || other.bbox().separates(bbox())) {
        return true;
    }
 
    // The boundaries touching or crossing settles the closed intersection.
    if (boundariesIntersect(other)) {
        return true;
    }
 
    // Disjoint boundaries: the polygons are either separate or one lies wholly
    // inside the other, so a single point-in-polygon test each way settles it
    // (every vertex of the inner polygon is contained in the outer one).
    return contains(other.get(0)) || other.contains(get(0));
}
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Polygon<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherPoint& point) const {
    return contains(point);
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(other.asSegment());
}
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (const auto point = getIfPoint()) {
        // A radius-zero disk is its centre, which the in-circle formulation
        // below cannot see (see intersects(Segment)).
        return other.contains(*point);
    }
    // A line has no endpoints, so there is no containment shortcut: it meets the
    // closed disk exactly when the centre lies within one radius of the line,
    // i.e. when the power quadratic along the line has real roots (discriminant
    // >= 0). Same exact, division-free in-circle formulation as
    // intersects(Segment), evaluated on the two points that define the line and
    // without the [0,1] parameter restriction.
    //
    //   A  = orientation determinant of the three boundary points
    //   J0 = inCircleDeterminant(a,b,c, other[0]), J1 = ... (a,b,c, other[1])
    //   L  = |other[1] - other[0]|^2,   M = L * A
    // Line reaches the closed disk: (J0 + J1 + M)^2 >= 4*J0*J1.
    using W = detail::promoted_number_t<
        decltype(inCircleDeterminant(a(), b(), c(), other[0]))>;
 
    const W det = static_cast<W>(orientationDeterminant(a(), b(), c()));
    const W j0 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other[0]));
    const W j1 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other[1]));
    const W squared_length = other[0].template squaredDistance<W>(other[1]);
    if (squared_length == W{}) {
        return false;  // Degenerate line.
    }
    const W discriminant_base = j0 + j1 + squared_length * det;  // J0 + J1 + M
 
    return discriminant_base * discriminant_base >= W{4} * j0 * j1;
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (const auto center = getIfPoint()) {
        // A radius-zero disk is its center; the in-circle formulation below
        // needs three non-collinear boundary points to be meaningful.
        return other.contains(*center);
    }
    // The source in the closed disk settles it. Otherwise the ray meets the
    // closed disk exactly when its supporting line does (discriminant >= 0) and
    // the contact lies ahead of the source (the perpendicular foot has positive
    // parameter). Same division-free in-circle formulation as
    // intersects(Segment); the source is parameter 0 and the target parameter 1.
    if (contains(other.source())) {
        return true;
    }
 
    //   A  = orientation determinant of the three boundary points
    //   J0 = inCircleDeterminant(a,b,c, source), J1 = ... (a,b,c, target)
    //   L  = |target - source|^2,   M = L * A
    // Supporting line reaches the closed disk: (J0 + J1 + M)^2 >= 4*J0*J1.
    // Contact ahead of the source (foot parameter t* > 0): (J0 - J1)*A < M*A.
    using W = detail::promoted_number_t<
        decltype(inCircleDeterminant(a(), b(), c(), other.source()))>;
 
    const W det = static_cast<W>(orientationDeterminant(a(), b(), c()));
    const W j0 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other.source()));
    const W j1 = static_cast<W>(inCircleDeterminant(a(), b(), c(), other.target()));
    const W squared_length = other.source().template squaredDistance<W>(other.target());
    const W m = squared_length * det;
 
    const W projection = (j0 - j1) * det;          // (J0 - J1) * A
    const W half_span = m * det;                   // M * A = L * A^2 >= 0
    const W discriminant_base = j0 + j1 + m;       // J0 + J1 + M
 
    const bool reaches_disk = discriminant_base * discriminant_base >= W{4} * j0 * j1;
    const bool contact_ahead = projection < half_span;  // foot parameter t* > 0
 
    return reaches_disk && contact_ahead;
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    return other.contains((*this)[0]) || intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    // A rectangle edge meeting the closed disk covers every case except the disk
    // lying entirely inside the rectangle: an edge meets the disk whenever it
    // crosses it or has an endpoint in it, so a rectangle corner inside the disk
    // is already caught by its incident edges. The remaining case is detected by
    // a disk boundary point lying inside the rectangle.
    for (const auto& edge : other.edges()) {
        if (intersects(edge)) {
            return true;
        }
    }
    return other.contains((*this)[0]);
}
 
template <class PointType, class LabelType>
template<TriangleConcept OtherTriangle>
constexpr bool Disk<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    // A triangle edge meeting the closed disk covers every case except the disk
    // lying entirely inside the triangle: an edge meets the disk whenever it
    // crosses it or has an endpoint in it, so a triangle vertex inside the disk
    // is already caught by its incident edges. The remaining case is detected by
    // a disk boundary point lying inside the triangle.
    for (const auto& edge : other.edges()) {
        if (intersects(edge)) {
            return true;
        }
    }
    return other.contains((*this)[0]);
}
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Disk<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
 
template <class PointType, class LabelType>
template<DiskConcept OtherDisk>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherDisk& other) const {
    // If the disk meets the polygon without crossing its boundary, the disk lies
    // wholly inside the polygon, so a boundary point of the disk is contained.
    // Every other configuration -- a boundary crossing, or the polygon sitting
    // inside the disk -- is witnessed by some edge meeting the closed disk.
    if (contains(other.a())) {
        return true;
    }
    for (const auto& edge : edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}

 
template <class PointType, class LabelType, class Storage>
template<PointConcept OtherPoint>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType, class Storage>
template<SegmentConcept OtherSegment>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherSegment& other) const {
    if (points_.empty()) {
        return false;
    }
    if (points_.size() == 1) {
        return other.contains((*this)[0]);
    }
    const auto window = edgeWindow(other.min().x(), other.max().x());
    if (!window) {
        return false;
    }
    for (std::size_t i = window->first; i <= window->second; ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType, class Storage>
template<LineConcept OtherLine>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherLine& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherOrientedLine& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<RayConcept OtherRay>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherRay& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<HalfplaneConcept OtherHalfplane>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherHalfplane& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<RectangleConcept OtherRectangle>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    // A rectangle's x-extent is available directly, so only the chain edges in
    // that window can meet it.
    const auto window = edgeWindow(other.min().x(), other.max().x());
    if (!window) {
        return false;
    }
    for (std::size_t i = window->first; i <= window->second; ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<TriangleConcept OtherTriangle>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherTriangle& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<ConvexConcept OtherConvex>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherConvex& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<DiskConcept OtherDisk>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherDisk& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (std::size_t i = 0; i + 1 < size(); ++i) {
        if (this->template boundaryAt<false>(i).intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType, class Storage>
template<PointConcept OtherPoint>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
template <class PointType, class LabelType, class Storage>
template<MonotoneChainConcept OtherChain>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::intersects(const OtherChain& other) const {
    if (empty() || other.empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    if (other.size() == 1) {
        return contains(other[0]);
    }
    if ((*this)[size() - 1].x() < other[0].x() || other[other.size() - 1].x() < (*this)[0].x()) {
        return false;
    }
    // Merge sweep: both edge sequences are sorted by x-interval, so advancing
    // the edge with the lexicographically smaller right endpoint visits every
    // pair whose x-ranges overlap. On a tie both advance: the skipped pairs
    // could only meet at that shared right endpoint, which belongs to the pair
    // just tested, so nothing is missed.
    const std::size_t iEnd = size() - 1;
    const std::size_t jEnd = other.size() - 1;
    // Seed past the leading edges left of the shared x-window: an edge whose
    // x-range ends before max(minX) cannot overlap the other chain. indexAtX
    // locates the first candidate edge in O(log n) instead of advancing the
    // sweep one edge at a time; a disengaged result means the chains' x-ranges
    // are disjoint, so there is no overlapping pair to test.
    using XType = std::common_type_t<NumberType, typename OtherChain::PointType::NumberType>;
    const XType xlo = std::max<XType>((*this)[0].x(), other[0].x());
    const auto iSeed = indexAtX(xlo);
    const auto jSeed = other.indexAtX(xlo);
    // Back up one edge: the edge whose right endpoint sits exactly on xlo can
    // still meet the other chain there (e.g. a vertical edge at xlo), yet
    // indexAtX returns the vertex at xlo, i.e. the following edge.
    std::size_t i = (iSeed && jSeed) ? (*iSeed > 0 ? *iSeed - 1 : 0) : iEnd;
    std::size_t j = (iSeed && jSeed) ? (*jSeed > 0 ? *jSeed - 1 : 0) : jEnd;
    while (i < iEnd && j < jEnd) {
        const Segment<PointType> mine((*this)[i], (*this)[i + 1]);
        const Segment<typename OtherChain::PointType> theirs(other[j], other[j + 1]);
        if (!(mine.max().x() < theirs.min().x() || theirs.max().x() < mine.min().x()) &&
            mine.intersects(theirs)) {
            return true;
        }
        const auto order = mine.max() <=> theirs.max();
        if (order <= 0) {
            ++i;
        }
        if (order >= 0) {
            ++j;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<MonotoneChainConcept OtherChain>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherChain& other) const {
    if (other.empty()) {
        return false;
    }
    if (other.size() == 1) {
        return intersects(other[0]);
    }
    for (std::size_t i = 0; i + 1 < other.size(); ++i) {
        if (intersects(Segment<typename OtherChain::PointType>(other[i], other[i + 1]))) {
            return true;
        }
    }
    return false;
}

 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template<SegmentConcept OtherSegment>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    for (const auto& edge : edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<OrientedSegmentConcept OtherOrientedSegment>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
namespace detail {
 
// Shared body of Polyline::intersects against a shape with a
// `contains(point)` test and a segment intersection test: the polyline meets
// it iff some edge does (or its single vertex lies inside it).
template <class PolylineType, class OtherShape>
constexpr bool polylineIntersects(const PolylineType& polyline, const OtherShape& other) {
    if (polyline.empty()) {
        return false;
    }
    if (polyline.size() == 1) {
        return other.contains(polyline[0]);
    }
    for (const auto& edge : polyline.edgesView()) {
        if (edge.intersects(other)) {
            return true;
        }
    }
    return false;
}
 
}  // namespace detail
 
template <class PointType, class LabelType>
template<LineConcept OtherLine>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherLine& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<OrientedLineConcept OtherOrientedLine>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<RayConcept OtherRay>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherRay& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<HalfplaneConcept OtherHalfplane>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<RectangleConcept OtherRectangle>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    if (size() > 1 && !bbox().intersects(other)) {
        return false;
    }
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<TriangleConcept OtherTriangle>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<ConvexConcept OtherConvex>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherConvex& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<DiskConcept OtherDisk>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherDisk& other) const {
    return detail::polylineIntersects(*this, other);
}
 
template <class PointType, class LabelType>
template<MonotoneChainConcept OtherChain>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherChain& other) const {
    if (empty() || other.empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    if (other.size() == 1) {
        return contains(other[0]);
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    // The chain's own segment test prunes by x-range, so fold it over the
    // polyline edges.
    for (const auto& edge : edgesView()) {
        if (other.intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<PolylineConcept OtherPolyline>
constexpr bool Polyline<PointType, LabelType>::intersects(const OtherPolyline& other) const {
    if (empty() || other.empty()) {
        return false;
    }
    if (size() == 1) {
        return other.contains((*this)[0]);
    }
    if (other.size() == 1) {
        return contains(other[0]);
    }
    if (!bbox().intersects(other.bbox())) {
        return false;
    }
    for (const auto& mine : edgesView()) {
        for (const auto& theirs : other.edgesView()) {
            if (mine.intersects(theirs)) {
                return true;
            }
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template<PointConcept OtherPoint>
constexpr bool Polyline<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
template <class PointType, class LabelType>
template<PolylineConcept OtherPolyline>
constexpr bool Polygon<PointType, LabelType>::intersects(const OtherPolyline& other) const {
    if (other.empty()) {
        return false;
    }
    if (other.size() == 1) {
        return intersects(other[0]);
    }
    for (std::size_t i = 0; i + 1 < other.size(); ++i) {
        if (intersects(Segment<typename OtherPolyline::PointType>(other[i], other[i + 1]))) {
            return true;
        }
    }
    return false;
}
 
 
// ---------------------------------------------------------------------------
// HalfplaneIntersection
 
template <class PointType, class LabelType>
template <PointConcept OtherPoint>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherPoint& other) const {
    return contains(other);
}
 
template <class PointType, class LabelType>
template <SegmentConcept OtherSegment>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (empty()) {
        return false;
    }
    if (halfplanes_.empty()) {
        return true;
    }
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    // Clip the supporting line and intersect the parameter interval with
    // [0, 1]; the interval endpoints compare against the segment endpoints
    // through plain point-side tests.
    const Halfplane<typename OtherSegment::PointType> along(other.min(), other.max());
    const auto clip = clipLine(along);
    if (clip.empty) {
        return false;
    }
    if (clip.entry >= 0 && constraintSide(static_cast<std::size_t>(clip.entry), other.max()) < 0) {
        return false;  // the line enters the region only after the segment ends
    }
    if (clip.exit >= 0 && constraintSide(static_cast<std::size_t>(clip.exit), other.min()) < 0) {
        return false;  // the line leaves the region before the segment starts
    }
    return true;
}
 
template <class PointType, class LabelType>
template <OrientedSegmentConcept OtherOrientedSegment>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(Segment<typename OtherOrientedSegment::PointType>(other[0], other[1]));
}
 
template <class PointType, class LabelType>
template <LineConcept OtherLine>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (empty()) {
        return false;
    }
    if (halfplanes_.empty()) {
        return true;
    }
    const Halfplane<typename OtherLine::PointType> along(other[0], other[1]);
    return !clipLine(along).empty;
}
 
template <class PointType, class LabelType>
template <OrientedLineConcept OtherOrientedLine>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template <RayConcept OtherRay>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (empty()) {
        return false;
    }
    if (halfplanes_.empty()) {
        return true;
    }
    const Halfplane<typename OtherRay::PointType> along(other.source(), other.target());
    const auto clip = clipLine(along);
    if (clip.empty) {
        return false;
    }
    // The interval must reach forward parameters: the line may not leave the
    // region before the ray's source.
    return clip.exit < 0 || constraintSide(static_cast<std::size_t>(clip.exit), other.source()) >= 0;
}
 
template <class PointType, class LabelType>
template <HalfplaneConcept OtherHalfplane>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (empty()) {
        return false;
    }
    if (halfplanes_.empty()) {
        return true;
    }
    // Nonempty intersection means the infimum of the half-plane's normal
    // functional over the region does not exceed its boundary value.
    return supStatus(other.opposite()) != SupStatus::below;
}
 
template <class PointType, class LabelType>
template <RectangleConcept OtherRectangle>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    // The intersection with a convex region is itself a half-plane
    // intersection; the two shapes meet exactly when it is nonempty.
    return !this->template intersection<NumberType>(other).empty();
}
 
template <class PointType, class LabelType>
template <TriangleConcept OtherTriangle>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    return !this->template intersection<NumberType>(other).empty();
}
 
template <class PointType, class LabelType>
template <ConvexConcept OtherConvex>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherConvex& other) const {
    if (other.size() == 0) {
        return false;
    }
    return !this->template intersection<NumberType>(other).empty();
}
 
template <class PointType, class LabelType>
template <DiskConcept OtherDisk>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherDisk& other) const {
    if (empty()) {
        return false;
    }
    if (halfplanes_.empty()) {
        return true;
    }
    // The disk is bounded, so only the part of the region near it matters:
    // clip to a box enclosing the disk and test the resulting bounded region.
    using E = detail::region_exact_number_t<NumberType>;
    const auto clipped = detail::regionClippedToBox(*this, other.bbox());
    if (clipped.empty()) {
        return false;
    }
    return clipped.template asConvex<E>().intersects(other);
}
 
template <class PointType, class LabelType>
template <MonotoneChainConcept OtherChain>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherChain& other) const {
    if (empty() || other.size() == 0) {
        return false;
    }
    if (other.size() == 1) {
        return contains(other[0]);
    }
    for (const auto& edge : other.edgesView()) {
        if (intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template <PolylineConcept OtherPolyline>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherPolyline& other) const {
    if (empty() || other.size() == 0) {
        return false;
    }
    if (other.size() == 1) {
        return contains(other[0]);
    }
    for (const auto& edge : other.edgesView()) {
        if (intersects(edge)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template <PolygonConcept OtherPolygon>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherPolygon& other) const {
    if (empty() || other.size() == 0) {
        return false;
    }
    // The shapes meet when the region reaches the polygon's boundary or holds
    // an interior witness of the polygon (the region is fully inside it).
    for (std::size_t i = 0; i < other.size(); ++i) {
        if (contains(other[i])) {
            return true;
        }
    }
    for (const auto& edge : other.edgesView()) {
        if (intersects(edge)) {
            return true;
        }
    }
    using E = detail::region_exact_number_t<NumberType>;
    return other.contains(pointInside<E>());
}
 
template <class PointType, class LabelType>
template <HalfplaneIntersectionConcept OtherRegion>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const OtherRegion& other) const {
    // The intersection of two half-plane intersections is itself one; the
    // regions meet exactly when it is nonempty.
    if (empty() || other.empty()) {
        return false;
    }
    return !this->template intersection<NumberType>(other).empty();
}
 
template <class PointType, class LabelType>
template <PointConcept OtherPoint>
constexpr bool HalfplaneIntersection<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
 
// ---------------------------------------------------------------------------
// PolygonWithHoles
 
template <class PointType, class LabelType>
template <SegmentConcept OtherSegment>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherSegment& other) const {
    if (!outer_.intersects(other)) {
        return false;
    }
    if (holes_.empty()) {
        return true;
    }
    // Every point of every ring belongs to the region: holes remove only their
    // interiors, and a hole interior never reaches the outer boundary. So a
    // segment touching any ring edge already meets the region.
    if (anyBoundaryEdge([&other](const auto& edge) { return edge.intersects(other); })) {
        return true;
    }
    // The segment misses ∂A altogether, so — being connected — it lies wholly
    // in the open region or wholly outside the closed one, and either endpoint
    // says which.
    return contains(other.min());
}
 
template <class PointType, class LabelType>
template <OrientedSegmentConcept OtherOrientedSegment>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherOrientedSegment& other) const {
    return intersects(other.asSegment());
}
 
// An unbounded connected operand that reaches the bounded outer polygon has to
// leave it again, so it meets ∂outer — and every point of ∂outer is in the
// region, hole interiors never reaching it. The holes therefore cost nothing
// here; only a collapsed operand, which is a point that a hole can swallow,
// needs the region's own point test.
template <class PointType, class LabelType>
template <LineConcept OtherLine>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherLine& other) const {
    if (other.isDegenerate()) {
        return contains(other.min());
    }
    return outer_.intersects(other);
}
 
template <class PointType, class LabelType>
template <OrientedLineConcept OtherOrientedLine>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherOrientedLine& other) const {
    return intersects(other.asLine());
}
 
template <class PointType, class LabelType>
template <RayConcept OtherRay>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherRay& other) const {
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    return outer_.intersects(other);
}
 
template <class PointType, class LabelType>
template <HalfplaneConcept OtherHalfplane>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherHalfplane& other) const {
    if (other.isDegenerate()) {
        return contains(other.source());
    }
    return outer_.intersects(other);
}
 
// The bounded operands with area follow the segment overload exactly: every
// point of every ring belongs to the region, so touching a ring settles it, and
// an operand missing ∂A altogether is — being connected — wholly in A° or
// wholly outside A, which one of its own vertices reports.
template <class PointType, class LabelType>
template <class OtherArea>
constexpr bool PolygonWithHoles<PointType, LabelType>::areaIntersects(const OtherArea& other) const {
    if (!other.intersects(outer_)) {
        return false;
    }
    if (holes_.empty()) {
        return true;
    }
    if (anyBoundaryEdge([&other](const auto& edge) { return edge.intersects(other); })) {
        return true;
    }
    const auto edges = other.edges();
    return !edges.empty() && contains(edges.front().min());
}
 
template <class PointType, class LabelType>
template <RectangleConcept OtherRectangle>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherRectangle& other) const {
    if (other.empty()) {
        // The empty set meets nothing and disconnects nothing.
        return false;
    }
    return areaIntersects(other);
}
 
template <class PointType, class LabelType>
template <TriangleConcept OtherTriangle>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherTriangle& other) const {
    return areaIntersects(other);
}
 
template <class PointType, class LabelType>
template <ConvexConcept OtherConvex>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherConvex& other) const {
    return areaIntersects(other);
}
 
template <class PointType, class LabelType>
template <PolygonConcept OtherPolygon>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherPolygon& other) const {
    return areaIntersects(other);
}
 
template <class PointType, class LabelType>
template <PolygonWithHolesConcept OtherRegion>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherRegion& other) const {
    return areaIntersects(other);
}
 
// A chain is the union of its edges, so it meets the region exactly when some
// edge does (see @ref chainRelation).
template <class PointType, class LabelType>
template <MonotoneChainConcept OtherChain>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherChain& other) const {
    return chainRelation(other, false, [this](const auto& edge) { return this->intersects(edge); });
}
 
template <class PointType, class LabelType>
template <PolylineConcept OtherPolyline>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherPolyline& other) const {
    return chainRelation(other, false, [this](const auto& edge) { return this->intersects(edge); });
}
 
// The disk follows the area operands exactly: every point of every ring belongs
// to the region, so touching a ring settles it, and a disk missing ∂A altogether
// is — being connected — wholly in A° or wholly outside A, which any one of its
// own points reports.
template <class PointType, class LabelType>
template <DiskConcept OtherDisk>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherDisk& other) const {
    if (other.isDegenerate()) {
        // Radius zero, or undefined; either way a() carries the answer, and the
        // point overload is cheaper than the scan below.
        return intersects(other.a());
    }
    if (!other.intersects(outer_)) {
        return false;
    }
    if (holes_.empty()) {
        return true;
    }
    if (anyBoundaryEdge([&other](const auto& edge) { return other.intersects(edge); })) {
        return true;
    }
    return contains(other.a());
}
 
// Same argument once more, and it survives an unbounded operand: a half-plane
// intersection is connected, so one that misses ∂A lies wholly in A° — which a
// bounded region rules out for anything unbounded — or wholly outside A.
template <class PointType, class LabelType>
template <HalfplaneIntersectionConcept OtherIntersection>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const OtherIntersection& other) const {
    if (other.empty()) {
        return false;
    }
    if (!other.intersects(outer_)) {
        return false;
    }
    if (holes_.empty()) {
        return true;
    }
    if (anyBoundaryEdge([&other](const auto& edge) { return other.intersects(edge); })) {
        return true;
    }
    using E = detail::region_exact_number_t<typename OtherIntersection::NumberType>;
    return contains(other.template pointInside<E>());
}
 
 
// ---------------------------------------------------------------------------
// Reverse direction: intersects is symmetric, so the lower-ranked shapes'
// generic rank-guarded forwarders already dispatch these here — no per-shape
// definitions are needed.
 
// ---------------------------------------------------------------------------
// Runtime Shape argument: unwrap the stored alternative and re-dispatch. Every
// alternative has a per-shape overload above, so no fallback is needed.
 
template <class PointType, class LabelType>
template <PointConcept OtherPoint>
constexpr bool PolygonWithHoles<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit(
        [this](const auto& value) {
            return this->intersects(value);
        },
        other.variant());
}
 
 
// ---------------------------------------------------------------------------
// PolygonSet
//
// `A ∩ x ≠ ∅` iff some `Aᵢ ∩ x ≠ ∅`: the union of the components is the set, and
// that is the whole argument, for every operand and with no exception.
 
template <class PointType, class LabelType>
template <detail::SetOperandConcept OtherShape>
bool PolygonSet<PointType, LabelType>::intersects(const OtherShape& other) const {
    return anyComponent([&](const ComponentType& component) { return component.intersects(other); });
}
 
template <class PointType, class LabelType>
template <PolygonSetConcept OtherSet>
bool PolygonSet<PointType, LabelType>::intersects(const OtherSet& other) const {
    for (const auto& component : other) {
        if (intersects(component)) {
            return true;
        }
    }
    return false;
}
 
template <class PointType, class LabelType>
template <PointConcept OtherPoint>
bool PolygonSet<PointType, LabelType>::intersects(const Shape<OtherPoint>& other) const {
    return std::visit([this](const auto& value) { return this->intersects(value); },
                      other.variant());
}
 
}  // namespace pgl