samepointset.hpp

Go to the documentation of this file.

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

 
#include <algorithm>
#include <compare>
#include <concepts>
#include <cstddef>
#include <optional>
#include <ranges>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
 
namespace pgl::detail {

template <AnyShapeConcept First, AnyShapeConcept Second>
constexpr bool samePointSetAny(const First& first, const Second& second);
 
// ---------------------------------------------------------------------------
// Carriers of collapsed shapes

template <class TShape>
struct shape_point {
    using type = typename TShape::PointType;
};
 
template <class Number, class Label>
struct shape_point<Point<Number, Label>> {
    using type = Point<Number, Label>;
};
 
template <class TShape>
using shape_point_t = typename shape_point<std::remove_cvref_t<TShape>>::type;

template <class TShape>
constexpr auto collapsedPoint(const TShape& shape) {
    using Shape = std::remove_cvref_t<TShape>;
    if constexpr (PolygonWithHolesConcept<Shape>) {
        return shape.outer().getIfPoint();
    } else if constexpr (PolygonSetConcept<Shape>) {
        using Result = std::optional<typename Shape::PointType>;
        if (shape.componentCount() != 1) {
            return Result{};
        }
        return Result(shape.component(0).outer().getIfPoint());
    } else if constexpr (requires { shape.getIfPoint(); }) {
        return shape.getIfPoint();
    } else {
        return std::optional<shape_point_t<Shape>>{};
    }
}

template <class TShape>
constexpr auto collapsedSegment(const TShape& shape) {
    using Shape = std::remove_cvref_t<TShape>;
    if constexpr (PolygonWithHolesConcept<Shape>) {
        return shape.outer().getIfSegment();
    } else if constexpr (PolygonSetConcept<Shape>) {
        using Result = std::optional<Segment<typename Shape::PointType>>;
        if (shape.componentCount() != 1) {
            return Result{};
        }
        return Result(shape.component(0).outer().getIfSegment());
    } else if constexpr (requires { shape.getIfSegment(); }) {
        return shape.getIfSegment();
    } else {
        return std::optional<Segment<shape_point_t<Shape>>>{};
    }
}

template <class TShape>
constexpr bool collapsedBelowArea(const TShape& shape) {
    if constexpr (requires { shape.isPoint(); shape.isSegment(); }) {
        return shape.isPoint() || shape.isSegment();
    } else if constexpr (requires { shape.isPoint(); }) {
        return shape.isPoint();
    } else {
        return false;
    }
}

template <class TShape, class Predicate>
constexpr bool reduceCollapsed(const TShape& shape, Predicate predicate) {
    if (const auto vertex = collapsedPoint(shape)) {
        return predicate(*vertex);
    }
    if (const auto carrier = collapsedSegment(shape)) {
        return predicate(*carrier);
    }
    return false;
}

template <class First, class Second>
constexpr bool collapsedMatches(const First& first, const Second& second) {
    return reduceCollapsed(first, [&second](const auto& carrier) {
        return samePointSetAny(carrier, second);
    });
}

template <HalfplaneIntersectionConcept Region, class Predicate>
constexpr bool reduceRegionCarrier(const Region& region, Predicate predicate) {
    if (const auto vertex = region.getIfPoint()) {
        return predicate(*vertex);
    }
    if (const auto carrier = region.getIfSegment()) {
        return predicate(*carrier);
    }
    if (const auto carrier = region.getIfRay()) {
        return predicate(*carrier);
    }
    if (const auto carrier = region.getIfLine()) {
        return predicate(*carrier);
    }
    return false;
}
 
// ---------------------------------------------------------------------------
// The straight primitives

template <class First, class Second>
constexpr bool sameSegmentPointSet(const First& first, const Second& second) {
    return first.min() == second.min() && first.max() == second.max();
}

template <class First, class Second>
constexpr bool sameLinePointSet(const First& first, const Second& second) {
    return collinear(first.min(), first.max(), second.min()) &&
           collinear(first.min(), first.max(), second.max());
}

template <RayConcept First, RayConcept Second>
constexpr bool sameRayPointSet(const First& first, const Second& second) {
    return first.source() == second.source() &&
           collinear(first.source(), first.target(), second.target()) &&
           dotSign(first.source(), first.target(), second.source(), second.target()) > 0;
}

template <class First, class Second>
constexpr bool sameHalfplanePointSet(const First& first, const Second& second) {
    return collinear(first.source(), first.target(), second.source()) &&
           collinear(first.source(), first.target(), second.target()) &&
           dotSign(first.source(), first.target(), second.source(), second.target()) > 0;
}

 * `tail -> head`, with the region on its left.
 *
 * The half-plane form of @ref sameHalfplanePointSet, for a caller that holds
 * the boundary as two points rather than as a `Halfplane`.
 */
template <class HalfplaneType, class TailPoint, class HeadPoint>
constexpr bool halfplaneBoundedByEdge(const HalfplaneType& halfplane,
                                      const TailPoint& tail,
                                      const HeadPoint& head) {
    return collinear(halfplane.source(), halfplane.target(), tail) &&
           collinear(halfplane.source(), halfplane.target(), head) &&
           dotSign(halfplane.source(), halfplane.target(), tail, head) > 0;
}
 
// ---------------------------------------------------------------------------
// Bounded shapes

template <class First, class Second>
constexpr bool sameBoundingBox(const First& first, const Second& second) {
    const auto& firstBox = first.bbox();
    const auto& secondBox = second.bbox();
    return firstBox.min() == secondBox.min() && firstBox.max() == secondBox.max();
}
 
// ---------------------------------------------------------------------------
// Polygonal rings

template <class First, class Second>
constexpr bool sameRepresentation(const First& first, const Second& second) {
    if constexpr (requires { { first == second } -> std::convertible_to<bool>; }) {
        return first == second;
    } else {
        return false;
    }
}

template <class Ring>
constexpr bool subdividingVertex(const Ring& ring, std::size_t index) {
    const auto position = static_cast<std::ptrdiff_t>(index);
    const auto previous = ring.get(position - 1);
    const auto current = ring[index];
    const auto next = ring.get(position + 1);
    if (!collinear(previous, current, next)) {
        return false;
    }
    return (previous < current && current < next) || (next < current && current < previous);
}

template <class Ring>
constexpr std::size_t nextRingCorner(const Ring& ring, std::size_t index) {
    const std::size_t count = ring.size();
    do {
        index = index + 1 == count ? 0 : index + 1;
    } while (index != 0 && subdividingVertex(ring, index));
    return index;
}

template <class First, class Second>
constexpr bool sameRingPointSet(const First& first, const Second& second) {
    if (first.size() < 3 || second.size() < 3) {
        return false;  // no area to enclose
    }
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (!(first[0] == second[0])) {
        return false;
    }
    if (first.size() == second.size()) {
        std::size_t index = 1;
        while (index < first.size() && first[index] == second[index]) {
            ++index;
        }
        if (index == first.size()) {
            return true;
        }
    }
    std::size_t here = 0;
    std::size_t there = 0;
    for (;;) {
        here = nextRingCorner(first, here);
        there = nextRingCorner(second, there);
        if (here == 0 || there == 0) {
            return here == there;  // one ring ran out of corners before the other
        }
        if (!(first[here] == second[there])) {
            return false;
        }
    }
}

template <class First, class Second>
constexpr bool sameRingShapes(const First& first, const Second& second) {
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (!sameBoundingBox(first, second)) {
        // Four coordinates read straight out of the cached boxes, with no
        // vertex rebuilt and nothing to overflow.
        return false;
    }
    if (!(first[0] == second[0])) {
        // The first vertex is the lexicographically smallest one whether the
        // ring encloses area or has collapsed onto a segment or a point, and
        // the smallest point of a set is a property of the set. That settles
        // the rings a shared box let through, before anything asks how either
        // one is shaped.
        return false;
    }
    if (collapsedBelowArea(first)) {
        return collapsedMatches(first, second);
    }
    if (collapsedBelowArea(second)) {
        return collapsedMatches(second, first);
    }
    return sameRingPointSet(first, second);
}

template <class FirstRange, class SecondRange, class Compare>
constexpr bool sameRingCollection(const FirstRange& first, const SecondRange& second, Compare same) {
    const std::size_t count = first.size();
    bool aligned = true;
    for (std::size_t i = 0; i < count; ++i) {
        if (!same(first[i], second[i])) {
            aligned = false;
            break;
        }
    }
    if (aligned) {
        return true;
    }
    for (const auto& ring : first) {
        bool found = false;
        for (const auto& candidate : second) {
            if (same(ring, candidate)) {
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

template <PolygonWithHolesConcept First, PolygonWithHolesConcept Second>
constexpr bool sameRegionRings(const First& first, const Second& second) {
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (!sameRingPointSet(first.outer(), second.outer())) {
        return false;
    }
    if (first.holeCount() != second.holeCount()) {
        return false;
    }
    return sameRingCollection(first.holes(), second.holes(),
                              [](const auto& one, const auto& other) {
                                  return sameRingPointSet(one, other);
                              });
}
 
// ---------------------------------------------------------------------------
// Boundaries

template <class SegmentType, class EdgeRange>
constexpr bool segmentCoveredByEdges(const SegmentType& segment, const EdgeRange& edges) {
    using EdgeType = std::ranges::range_value_t<EdgeRange>;
    using CommonPoint =
        Point<std::common_type_t<typename SegmentType::PointType::NumberType,
                                 typename EdgeType::PointType::NumberType>>;
 
    const CommonPoint low(segment.min());
    const CommonPoint high(segment.max());
    if (low == high) {
        for (const auto& edge : edges) {
            if (edge.contains(low)) {
                return true;
            }
        }
        return false;
    }
 
    std::vector<std::pair<CommonPoint, CommonPoint>> overlaps;
    for (const auto& edge : edges) {
        if (!collinear(low, high, edge.min()) || !collinear(low, high, edge.max())) {
            continue;  // the edge leaves the segment's supporting line
        }
        const CommonPoint lo = (edge.min() < low) ? low : CommonPoint(edge.min());
        const CommonPoint hi = (high < edge.max()) ? high : CommonPoint(edge.max());
        if (hi < lo) {
            continue;  // collinear but disjoint from the segment
        }
        overlaps.emplace_back(lo, hi);
    }
    std::sort(overlaps.begin(), overlaps.end());
 
    CommonPoint covered = low;
    for (const auto& [lo, hi] : overlaps) {
        if (covered < lo) {
            return false;  // the part between covered and lo is off the edges
        }
        if (covered < hi) {
            covered = hi;
        }
    }
    return !(covered < high);
}

template <class First, class Second>
constexpr bool sameBoundaryPointSet(const First& first, const Second& second) {
    const auto firstEdges = first.edges();
    const auto secondEdges = second.edges();
    for (const auto& edge : firstEdges) {
        if (!segmentCoveredByEdges(edge, secondEdges)) {
            return false;
        }
    }
    for (const auto& edge : secondEdges) {
        if (!segmentCoveredByEdges(edge, firstEdges)) {
            return false;
        }
    }
    return true;
}
 
// ---------------------------------------------------------------------------
// Half-plane intersections

template <HalfplaneIntersectionConcept Region, class Ring>
constexpr bool sameConvexRegionAndRing(const Region& region, const Ring& ring) {
    if (region.isDegenerate()) {
        return reduceRegionCarrier(region, [&ring](const auto& carrier) {
            return samePointSetAny(carrier, ring);
        });
    }
    if (collapsedBelowArea(ring) || !region.isBounded()) {
        // The region has interior and is unbounded or the ring has neither.
        return false;
    }
    const std::size_t constraints = region.size();
    if (constraints < 3) {
        return false;  // fewer constraints than that bound nothing
    }
 
    // Where the two cyclic sequences start relative to each other is the only
    // unknown, and the ring's first corner edge locates it.
    const std::size_t behind = nextRingCorner(ring, 0);
    std::size_t start = constraints;
    for (std::size_t i = 0; i < constraints; ++i) {
        if (halfplaneBoundedByEdge(region[i], ring[0], ring[behind])) {
            start = i;
            break;
        }
    }
    if (start == constraints) {
        return false;
    }
 
    // Walking the corners against the constraints also counts them: the ring
    // has to close after exactly as many corners as there are constraints.
    std::size_t here = 0;
    for (std::size_t i = 0; i < constraints; ++i) {
        const std::size_t next = nextRingCorner(ring, here);
        if (!halfplaneBoundedByEdge(region[(start + i) % constraints], ring[here], ring[next])) {
            return false;
        }
        here = next;
    }
    return here == 0;
}
 
// ---------------------------------------------------------------------------
// Chains

template <class Chain>
constexpr std::size_t nextChainCorner(const Chain& chain, std::size_t index) {
    const std::size_t last = chain.size() - 1;
    do {
        ++index;
    } while (index < last && collinear(chain[index - 1], chain[index], chain[index + 1]));
    return index;
}

template <MonotoneChainConcept First, MonotoneChainConcept Second>
constexpr bool sameChainPointSet(const First& first, const Second& second) {
    if (sameRepresentation(first, second)) {
        return true;
    }
    const std::size_t firstCount = first.size();
    const std::size_t secondCount = second.size();
    if (!(first[0] == second[0])) {
        return false;
    }
    if (firstCount == secondCount) {
        std::size_t index = 1;
        while (index < firstCount && first[index] == second[index]) {
            ++index;
        }
        if (index == firstCount) {
            return true;
        }
    }
    std::size_t i = 0;
    std::size_t j = 0;
    for (;;) {
        if (i + 1 == firstCount || j + 1 == secondCount) {
            return i + 1 == firstCount && j + 1 == secondCount;
        }
        i = nextChainCorner(first, i);
        j = nextChainCorner(second, j);
        if (!(first[i] == second[j])) {
            return false;
        }
    }
}

template <class First, class Second>
constexpr bool samePolylinePointSet(const First& first, const Second& second) {
    if (!sameBoundingBox(first, second)) {
        // Both shapes cache their box, and having no canonical first vertex to
        // compare, this is the O(1) rejection they do have.
        return false;
    }
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (const auto carrier = collapsedSegment(first)) {
        return samePointSetAny(*carrier, second);
    }
    if (const auto carrier = collapsedPoint(first)) {
        return samePointSetAny(*carrier, second);
    }
    if (first.size() == second.size()) {
        const std::size_t count = first.size();
        bool forward = true;
        bool backward = true;
        for (std::size_t i = 0; i < count; ++i) {
            forward = forward && first[i] == second[i];
            backward = backward && first[i] == second[count - 1 - i];
        }
        if (forward || backward) {
            return true;
        }
    }
    return first.contains(second) && second.contains(first);
}
 
// ---------------------------------------------------------------------------


template <PointConcept First, PointConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return first == second;
}

template <PointConcept First, SegmentConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return second.min() == second.max() && first == second.min();
}

template <PointConcept First, OrientedSegmentConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return second.min() == second.max() && first == second.min();
}

template <PointConcept First, LineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <PointConcept First, OrientedLineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <PointConcept First, RayConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <PointConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <PointConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PointConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}


template <SegmentConcept First, SegmentConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameSegmentPointSet(first, second);
}

template <SegmentConcept First, OrientedSegmentConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameSegmentPointSet(first, second);
}

template <SegmentConcept First, LineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <SegmentConcept First, OrientedLineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <SegmentConcept First, RayConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <SegmentConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <SegmentConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <SegmentConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}


template <OrientedSegmentConcept First, OrientedSegmentConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameSegmentPointSet(first, second);
}

template <OrientedSegmentConcept First, LineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedSegmentConcept First, OrientedLineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedSegmentConcept First, RayConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedSegmentConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedSegmentConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <OrientedSegmentConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}


template <LineConcept First, LineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameLinePointSet(first, second);
}

template <LineConcept First, OrientedLineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameLinePointSet(first, second);
}

template <LineConcept First, RayConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, DiskConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    const auto carrier = second.getIfLine();
    return carrier && sameLinePointSet(first, *carrier);
}

template <LineConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <LineConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}


template <OrientedLineConcept First, OrientedLineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameLinePointSet(first, second);
}

template <OrientedLineConcept First, RayConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, DiskConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    const auto carrier = second.getIfLine();
    return carrier && sameLinePointSet(first, *carrier);
}

template <OrientedLineConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <OrientedLineConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}


template <RayConcept First, RayConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRayPointSet(first, second);
}

template <RayConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, DiskConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    const auto carrier = second.getIfRay();
    return carrier && sameRayPointSet(first, *carrier);
}

template <RayConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <RayConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}


template <HalfplaneConcept First, HalfplaneConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameHalfplanePointSet(first, second);
}

template <HalfplaneConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, DiskConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    const auto carrier = second.getIfHalfplane();
    return carrier && sameHalfplanePointSet(first, *carrier);
}

template <HalfplaneConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}

template <HalfplaneConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First&, const Second&) {
    return false;
}


template <RectangleConcept First, RectangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return first.min() == second.min() && first.max() == second.max();
}

template <RectangleConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <RectangleConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <RectangleConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <RectangleConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <RectangleConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <RectangleConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <RectangleConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameConvexRegionAndRing(second, first);
}

template <RectangleConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.hasHoles()) {
        return false;
    }
    return sameRingShapes(first, second.outer());
}

template <RectangleConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() != 1) {
        return false;
    }
    return samePointSetAny(first, second.component(0));
}


template <TriangleConcept First, TriangleConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (first.isDegenerate() || second.isDegenerate()) {
        return sameRingShapes(first, second);
    }
    return first[0] == second[0] && first[1] == second[1] && first[2] == second[2];
}

template <TriangleConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <TriangleConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <TriangleConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <TriangleConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <TriangleConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <TriangleConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameConvexRegionAndRing(second, first);
}

template <TriangleConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.hasHoles()) {
        return false;
    }
    return sameRingShapes(first, second.outer());
}

template <TriangleConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() != 1) {
        return false;
    }
    return samePointSetAny(first, second.component(0));
}


template <DiskConcept First, DiskConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (first.isPoint() || second.isPoint()) {
        return first.isPoint() && second.isPoint() && first.a() == second.a();
    }
    return inCircleSign(first.a(), first.b(), first.c(), second.a()) == 0 &&
           inCircleSign(first.a(), first.b(), first.c(), second.b()) == 0 &&
           inCircleSign(first.a(), first.b(), first.c(), second.c()) == 0;
}

template <DiskConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <DiskConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}


template <ConvexConcept First, ConvexConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <ConvexConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <ConvexConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(first, second);
}

template <ConvexConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <ConvexConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameConvexRegionAndRing(second, first);
}

template <ConvexConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.hasHoles()) {
        return false;
    }
    return sameRingShapes(first, second.outer());
}

template <ConvexConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() != 1) {
        return false;
    }
    return samePointSetAny(first, second.component(0));
}


template <MonotoneChainConcept First, MonotoneChainConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameChainPointSet(first, second);
}

template <MonotoneChainConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return samePolylinePointSet(second, first);
}

template <MonotoneChainConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <MonotoneChainConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <MonotoneChainConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <MonotoneChainConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}


template <PolylineConcept First, PolylineConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return samePolylinePointSet(first, second);
}

template <PolylineConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PolylineConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PolylineConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}

template <PolylineConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return collapsedMatches(second, first);
}


template <PolygonConcept First, PolygonConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameRingShapes(first, second);
}

template <PolygonConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    return sameConvexRegionAndRing(second, first);
}

template <PolygonConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.hasHoles()) {
        return false;
    }
    return sameRingShapes(first, second.outer());
}

template <PolygonConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() != 1) {
        return false;
    }
    return samePointSetAny(first, second.component(0));
}


template <HalfplaneIntersectionConcept First, HalfplaneIntersectionConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (first.isDegenerate() || second.isDegenerate()) {
        return reduceRegionCarrier(first, [&second](const auto& carrier) {
            return samePointSetAny(carrier, second);
        });
    }
    if (first.size() != second.size()) {
        return false;
    }
    for (std::size_t i = 0; i < first.size(); ++i) {
        if (!sameHalfplanePointSet(first[i], second[i])) {
            return false;
        }
    }
    return true;
}

template <HalfplaneIntersectionConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.hasHoles()) {
        return false;
    }
    return sameConvexRegionAndRing(first, second.outer());
}

template <HalfplaneIntersectionConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() != 1) {
        return false;
    }
    return samePointSetAny(first, second.component(0));
}


template <PolygonWithHolesConcept First, PolygonWithHolesConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (!sameBoundingBox(first, second) || !(first.outer()[0] == second.outer()[0])) {
        // A region's box and smallest vertex are its outer ring's, and reject
        // it for the same reasons a ring is rejected.
        return false;
    }
    if (collapsedBelowArea(first)) {
        return collapsedMatches(first, second);
    }
    if (collapsedBelowArea(second)) {
        return collapsedMatches(second, first);
    }
    return sameRegionRings(first, second);
}

template <PolygonWithHolesConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (second.componentCount() == 1) {
        return samePointSetAny(first, second.component(0));
    }
    if (collapsedBelowArea(first)) {
        return false;  // several components with area against no area at all
    }
    return sameBoundingBox(first, second) && sameBoundaryPointSet(first, second);
}


template <PolygonSetConcept First, PolygonSetConcept Second>
constexpr bool samePointSet(const First& first, const Second& second) {
    if (sameRepresentation(first, second)) {
        return true;
    }
    if (first.componentCount() == second.componentCount() &&
        sameRingCollection(first.components(), second.components(),
                           [](const auto& one, const auto& other) {
                               return sameRegionRings(one, other);
                           })) {
        return true;
    }
    if (collapsedBelowArea(first) || collapsedBelowArea(second)) {
        return collapsedMatches(first, second) || collapsedMatches(second, first);
    }
    return sameBoundingBox(first, second) && sameBoundaryPointSet(first, second);
}
 
// ---------------------------------------------------------------------------

template <AnyShapeConcept First, AnyShapeConcept Second>
constexpr bool samePointSetAny(const First& first, const Second& second) {
    if constexpr (ShapeConcept<First>) {
        return std::visit(
            [&second](const auto& value) { return samePointSetAny(value, second); },
            first.variant());
    } else if constexpr (ShapeConcept<Second>) {
        return std::visit(
            [&first](const auto& value) { return samePointSetAny(first, value); },
            second.variant());
    } else if constexpr (EmptyShapeConcept<First> || EmptyShapeConcept<Second>) {
        return coversNoPoint(first) && coversNoPoint(second);
    } else {
        const bool firstEmpty = coversNoPoint(first);
        const bool secondEmpty = coversNoPoint(second);
        if (firstEmpty || secondEmpty) {
            return firstEmpty && secondEmpty;
        }
        if constexpr (shapeRank<std::remove_cvref_t<First>> >
                      shapeRank<std::remove_cvref_t<Second>>) {
            return samePointSet(second, first);
        } else {
            return samePointSet(first, second);
        }
    }
}
 
}  // namespace pgl::detail
 
namespace pgl {
 
template <class Number, class Label>
template <AnyShapeConcept OtherShape>
constexpr bool Point<Number, Label>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType>
template <AnyShapeConcept OtherShape>
constexpr bool EmptyShape<PointType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Segment<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool OrientedSegment<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Line<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool OrientedLine<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Ray<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Halfplane<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Rectangle<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Triangle<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Disk<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Convex<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType, class Storage>
template <AnyShapeConcept OtherShape>
constexpr bool MonotoneChain<PointType, LabelType, Storage>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Polyline<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool Polygon<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool HalfplaneIntersection<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool PolygonWithHoles<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType, class LabelType>
template <AnyShapeConcept OtherShape>
constexpr bool PolygonSet<PointType, LabelType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
template <class PointType>
template <AnyShapeConcept OtherShape>
constexpr bool Shape<PointType>::samePointSet(const OtherShape& other) const {
    return detail::samePointSetAny(*this, other);
}
 
}  // namespace pgl