distancel1.hpp

Go to the documentation of this file.

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

 
#include <cmath>
#include <numbers>
 
namespace pgl {
 
namespace detail {

template <class ResultNumber>
constexpr ResultNumber segmentLikeDistanceL1(const Point<ResultNumber>& a, const Point<ResultNumber>& b,
                                              const Point<ResultNumber>& q, bool boundedLow, bool boundedHigh) {
    const ResultNumber dx = b.x() - a.x();
    const ResultNumber dy = b.y() - a.y();
    const ResultNumber px = q.x() - a.x();
    const ResultNumber py = q.y() - a.y();
 
    if (dx == 0 && dy == 0) {
        return pgl::detail::abs(px) + pgl::detail::abs(py);
    }
 
    bool haveBest = false;
    ResultNumber best{};
    const auto consider = [&](const ResultNumber& value) {
        if (!haveBest || value < best) {
            best = value;
            haveBest = true;
        }
    };
 
    if (boundedLow) {
        consider(pgl::detail::abs(px) + pgl::detail::abs(py));
    }
    if (boundedHigh) {
        consider(pgl::detail::abs(px - dx) + pgl::detail::abs(py - dy));
    }
 
    const ResultNumber cross = dx * py - dy * px;
    const auto considerCrossing = [&](const ResultNumber& n, const ResultNumber& d) {
        if (d == 0) {
            return;
        }
        // The low bound rejects t = n/d < 0, i.e. n and d of opposite signs.
        // Read off the two signs rather than forming n*d: for an exact rational
        // the product is a multiplication plus a normalization, while comparing
        // against the literal 0 is the sign of a numerator. d is nonzero here,
        // so d > 0 splits the cases exhaustively, and n == 0 correctly fails
        // both branches.
        if (boundedLow && (d > 0 ? n < 0 : n > 0)) {
            return;
        }
        if (boundedHigh && n * d > d * d) {
            return;
        }
        consider(pgl::detail::abs(cross) / pgl::detail::abs(d));
    };
    considerCrossing(px, dx);
    considerCrossing(py, dy);
 
    return best;
}

template <class ResultNumber, class Self, class OtherShape>
constexpr ResultNumber maxVertexDistanceL1(const Self& self, const OtherShape& other) {
    const auto self_vertices = self.vertices();
    const auto distanceToVertex = [&other](const auto& vertex) -> ResultNumber {
        return other.template distanceL1<ResultNumber>(vertex);
    };
    ResultNumber worst = distanceToVertex(self_vertices[0]);
    for (std::size_t index = 1; index < self_vertices.size(); ++index) {
        const ResultNumber current = distanceToVertex(self_vertices[index]);
        if (worst < current) {
            worst = current;
        }
    }
    return worst;
}

template <class Float = double>
Float diskPointDistanceL1(Float a, Float b, Float r) {
    const auto h = [&](Float theta) {
        return std::abs(a + r * std::cos(theta)) + std::abs(b + r * std::sin(theta));
    };
 
    constexpr int coarseSteps = 720;
    Float bestTheta{0};
    Float bestValue = h(Float{0});
    for (int i = 1; i < coarseSteps; ++i) {
        const Float theta = Float{2} * std::numbers::pi_v<Float> * i / coarseSteps;
        const Float value = h(theta);
        if (value < bestValue) {
            bestValue = value;
            bestTheta = theta;
        }
    }
 
    const Float step = Float{2} * std::numbers::pi_v<Float> / coarseSteps;
    Float lo = bestTheta - step;
    Float hi = bestTheta + step;
    constexpr Float invPhi = 0.6180339887498949;
    Float c1 = hi - invPhi * (hi - lo);
    Float c2 = lo + invPhi * (hi - lo);
    Float hc1 = h(c1);
    Float hc2 = h(c2);
    for (int i = 0; i < 100; ++i) {
        if (hc1 < hc2) {
            hi = c2;
            c2 = c1;
            hc2 = hc1;
            c1 = hi - invPhi * (hi - lo);
            hc1 = h(c1);
        } else {
            lo = c1;
            c1 = c2;
            hc1 = hc2;
            c2 = lo + invPhi * (hi - lo);
            hc2 = h(c2);
        }
    }
 
    return std::min({bestValue, hc1, hc2});
}
 
}  // namespace detail
 
// -----------------------------------------------------------------------------
// Point
 
template <class Number, class Label>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Point<Number, Label>::hausdorffDistanceL1(const OtherPoint& other) const {
    return this->template distanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// Disk
 
template <class PointType_, class TLabel>
template <class ResultNumber, PointConcept OtherPoint>
detail::floating_result_t<ResultNumber> Disk<PointType_, TLabel>::distanceL1(
    const OtherPoint& point) const {
    using Float = detail::floating_result_t<ResultNumber>;
    if (contains(point)) {
        return Float{0};
    }
    const Float a = center<Float>().x() - static_cast<Float>(point.x());
    const Float b = center<Float>().y() - static_cast<Float>(point.y());
    return detail::diskPointDistanceL1(a, b, radius<Float>());
}
 
// -----------------------------------------------------------------------------
// Segment
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Segment<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    return detail::segmentLikeDistanceL1<ResultNumber>(
        Point<ResultNumber>(min()), Point<ResultNumber>(max()), Point<ResultNumber>(point), true, true);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Segment<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto this_min_to_other = other.template distanceL1<ResultNumber>(min());
    const auto this_max_to_other = other.template distanceL1<ResultNumber>(max());
    const auto other_min_to_this = this->template distanceL1<ResultNumber>(other.min());
    const auto other_max_to_this = this->template distanceL1<ResultNumber>(other.max());
 
    const auto best_from_this = this_min_to_other < this_max_to_other ? this_min_to_other : this_max_to_other;
    const auto best_from_other = other_min_to_this < other_max_to_this ? other_min_to_this : other_max_to_this;
 
    return best_from_this < best_from_other ? best_from_this : best_from_other;
}
 
// -----------------------------------------------------------------------------
// OrientedSegment
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto OrientedSegment<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    return static_cast<Segment<PointType>>(*this).template distanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto OrientedSegment<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    return static_cast<Segment<PointType>>(*this).template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto OrientedSegment<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    return static_cast<Segment<PointType>>(*this).template distanceL1<ResultNumber>(
        static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
// -----------------------------------------------------------------------------
// Line
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Line<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    return detail::segmentLikeDistanceL1<ResultNumber>(
        Point<ResultNumber>(min()), Point<ResultNumber>(max()), Point<ResultNumber>(point), false, false);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Line<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return other.template distanceL1<ResultNumber>(min());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Line<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto source_distance = this->template distanceL1<ResultNumber>(other.min());
    const auto target_distance = this->template distanceL1<ResultNumber>(other.max());
    return source_distance < target_distance ? source_distance : target_distance;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Line<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    return this->template distanceL1<ResultNumber>(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
// -----------------------------------------------------------------------------
// OrientedLine
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto OrientedLine<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    return this->asLine().template distanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto OrientedLine<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    return this->asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto OrientedLine<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    return this->asLine().template distanceL1<ResultNumber>(other.asLine());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto OrientedLine<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    return this->asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto OrientedLine<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    return this->asLine().template distanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// Ray
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    return detail::segmentLikeDistanceL1<ResultNumber>(
        Point<ResultNumber>(source()), Point<ResultNumber>(target()), Point<ResultNumber>(point), true, false);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return other.template distanceL1<ResultNumber>(source());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return other.template distanceL1<ResultNumber>(source());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto source_to_other = other.template distanceL1<ResultNumber>(source());
    const auto other_min_to_this = this->template distanceL1<ResultNumber>(other.min());
    const auto other_max_to_this = this->template distanceL1<ResultNumber>(other.max());
    const auto best_from_segment = other_min_to_this < other_max_to_this ? other_min_to_this : other_max_to_this;
    return source_to_other < best_from_segment ? source_to_other : best_from_segment;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto source_to_other = other.template distanceL1<ResultNumber>(source());
    const auto other_source_to_this = this->template distanceL1<ResultNumber>(other.source());
    const auto other_target_to_this = this->template distanceL1<ResultNumber>(other.target());
    const auto best_from_segment = other_source_to_this < other_target_to_this ? other_source_to_this : other_target_to_this;
    return source_to_other < best_from_segment ? source_to_other : best_from_segment;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Ray<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto this_source_to_other = other.template distanceL1<ResultNumber>(source());
    const auto other_source_to_this = this->template distanceL1<ResultNumber>(other.source());
    return this_source_to_other < other_source_to_this ? this_source_to_other : other_source_to_this;
}
 
// -----------------------------------------------------------------------------
// Halfplane
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Halfplane<PointType, LabelType>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return asLine().template distanceL1<ResultNumber>(other.asLine());
}
 
// -----------------------------------------------------------------------------
// Rectangle
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    const ResultNumber dx = static_cast<ResultNumber>(axisDistance(min().x(), max().x(), point.x(), point.x()));
    const ResultNumber dy = static_cast<ResultNumber>(axisDistance(min().y(), max().y(), point.y(), point.y()));
    return dx + dy;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto rectangle_vertices = vertices();
    auto best_distance = other.template distanceL1<ResultNumber>(rectangle_vertices[0]);
    for (std::size_t index = 1; index < rectangle_vertices.size(); ++index) {
        const auto current_distance = other.template distanceL1<ResultNumber>(rectangle_vertices[index]);
        if (current_distance < best_distance) {
            best_distance = current_distance;
        }
    }
 
    return best_distance;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    return this->template distanceL1<ResultNumber>(other.asLine());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    auto best_distance = this->template distanceL1<ResultNumber>(other.min());
    const auto other_max_distance = this->template distanceL1<ResultNumber>(other.max());
    if (other_max_distance < best_distance) {
        best_distance = other_max_distance;
    }
 
    const auto rectangle_edges = edges();
    for (const auto& edge : rectangle_edges) {
        const auto current_distance = edge.template distanceL1<ResultNumber>(other);
        if (current_distance < best_distance) {
            best_distance = current_distance;
        }
    }
 
    return best_distance;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    return this->template distanceL1<ResultNumber>(static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    auto best_distance = this->template distanceL1<ResultNumber>(other.source());
    const auto rectangle_edges = edges();
    for (const auto& edge : rectangle_edges) {
        const auto current_distance = other.template distanceL1<ResultNumber>(edge);
        if (current_distance < best_distance) {
            best_distance = current_distance;
        }
    }
 
    return best_distance;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherHalfplane& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template distanceL1<ResultNumber>(other.asLine());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Rectangle<PointType, LabelType>::distanceL1(const OtherRectangle& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    const ResultNumber dx = static_cast<ResultNumber>(axisDistance(min().x(), max().x(), other.min().x(), other.max().x()));
    const ResultNumber dy = static_cast<ResultNumber>(axisDistance(min().y(), max().y(), other.min().y(), other.max().y()));
    return dx + dy;
}
 
// -----------------------------------------------------------------------------
// Triangle
 
template <class PointType, class LabelType>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber Triangle<PointType, LabelType>::edgeMinDistanceL1(const OtherShape& other) const {
    const auto triangle_edges = edges();
    auto best = triangle_edges[0].template distanceL1<ResultNumber>(other);
    for (std::size_t index = 1; index < triangle_edges.size(); ++index) {
        const auto current = triangle_edges[index].template distanceL1<ResultNumber>(other);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber Triangle<PointType, LabelType>::vertexMinDistanceL1(const OtherShape& other) const {
    const auto triangle_vertices = vertices();
    auto best = other.template distanceL1<ResultNumber>(triangle_vertices[0]);
    for (std::size_t index = 1; index < triangle_vertices.size(); ++index) {
        const auto current = other.template distanceL1<ResultNumber>(triangle_vertices[index]);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template vertexMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template vertexMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template distanceL1<ResultNumber>(other.asLine());
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherRectangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Triangle<PointType, LabelType>::distanceL1(const OtherTriangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// Convex
//
// Always uses the O(n) edge scan below (no cyclic support-function fast path):
// see the distanceL1 declarations in convex.hpp for why the Euclidean fast
// path's search functional does not carry over to the L1 gauge.
 
template <class PointType_, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherPoint& point) const {
    if (contains(point)) {
        return ResultNumber{};
    }
    auto edgeVector = edges();
    ResultNumber best = edgeVector[0].template distanceL1<ResultNumber>(point);
    for (auto& e : edgeVector) {
        const ResultNumber current = e.template distanceL1<ResultNumber>(point);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    auto edgeVector = edges();
    ResultNumber best = edgeVector[0].template distanceL1<ResultNumber>(other);
    for (auto& e : edgeVector) {
        const ResultNumber current = e.template distanceL1<ResultNumber>(other);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    return this->template distanceL1<ResultNumber>(
        static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherConvex& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
 
    const auto minOverEdges = [](const auto& source, const auto& target) {
        const auto edgeVector = source.edges();
        ResultNumber best = target.template distanceL1<ResultNumber>(edgeVector[0]);
        for (const auto& edge : edgeVector) {
            const ResultNumber current = target.template distanceL1<ResultNumber>(edge);
            if (current < best) {
                best = current;
            }
        }
        return best;
    };
 
    if (size() <= other.size()) {
        return minOverEdges(*this, other);
    }
    return minOverEdges(other, *this);
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherTriangle& other) const {
    return this->template distanceL1<ResultNumber>(other.asConvex());
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherRectangle& other) const {
    return this->template distanceL1<ResultNumber>(other.asConvex());
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    ResultNumber best = other.template distanceL1<ResultNumber>(get(0));
    for (std::ptrdiff_t i = 1; i < static_cast<std::ptrdiff_t>(size()); ++i) {
        const ResultNumber current = other.template distanceL1<ResultNumber>(get(i));
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    return this->template distanceL1<ResultNumber>(other.asLine());
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    auto edgeVector = edges();
    ResultNumber best = other.template distanceL1<ResultNumber>(edgeVector[0]);
    for (const auto& e : edgeVector) {
        const ResultNumber current = other.template distanceL1<ResultNumber>(e);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Convex<PointType_, LabelType>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template distanceL1<ResultNumber>(other.asLine());
}
 
// -----------------------------------------------------------------------------
// Polygon
 
template <class PointType_, class TLabel>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber Polygon<PointType_, TLabel>::edgeMinDistanceL1(const OtherShape& other) const {
    const auto boundaryEdges = edges();
    ResultNumber best = boundaryEdges[0].template distanceL1<ResultNumber>(other);
    for (std::size_t index = 1; index < boundaryEdges.size(); ++index) {
        const ResultNumber current = boundaryEdges[index].template distanceL1<ResultNumber>(other);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(point);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherRectangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherTriangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherConvex& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, PolygonConcept OtherPolygon>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherPolygon& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// Hausdorff distance (added only where a Euclidean squaredHausdorffDistance
// overload already exists; Polygon has none today, so it gets none here).
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Segment<PointType, LabelType>::hausdorffDistanceL1(const OtherSegment& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Segment<PointType, LabelType>::hausdorffDistanceL1(const OtherPoint& point) const {
    return detail::maxVertexDistanceL1<ResultNumber>(*this, point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto OrientedSegment<PointType, LabelType>::hausdorffDistanceL1(const OtherSegment& other) const {
    return static_cast<Segment<PointType>>(*this).template hausdorffDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto OrientedSegment<PointType, LabelType>::hausdorffDistanceL1(const OtherOrientedSegment& other) const {
    return static_cast<Segment<PointType>>(*this).template hausdorffDistanceL1<ResultNumber>(
        static_cast<Segment<typename OtherOrientedSegment::PointType>>(other));
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto OrientedSegment<PointType, LabelType>::hausdorffDistanceL1(const OtherPoint& point) const {
    return static_cast<Segment<PointType>>(*this).template hausdorffDistanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Rectangle<PointType, LabelType>::hausdorffDistanceL1(const OtherRectangle& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Rectangle<PointType, LabelType>::hausdorffDistanceL1(const OtherPoint& point) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    return detail::maxVertexDistanceL1<ResultNumber>(*this, point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Rectangle<PointType, LabelType>::hausdorffDistanceL1(const OtherSegment& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Rectangle<PointType, LabelType>::hausdorffDistanceL1(const OtherOrientedSegment& other) const {
    // There is no nearest point of the empty set, so it has no distance to
    // anything; asking for one is a precondition violation.
    assert(!empty());
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Triangle<PointType, LabelType>::hausdorffDistanceL1(const OtherPoint& point) const {
    return detail::maxVertexDistanceL1<ResultNumber>(*this, point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Triangle<PointType, LabelType>::hausdorffDistanceL1(const OtherSegment& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Triangle<PointType, LabelType>::hausdorffDistanceL1(const OtherOrientedSegment& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Triangle<PointType, LabelType>::hausdorffDistanceL1(const OtherRectangle& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Triangle<PointType, LabelType>::hausdorffDistanceL1(const OtherTriangle& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherPoint& point) const {
    return detail::maxVertexDistanceL1<ResultNumber>(*this, point);
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherSegment& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherOrientedSegment& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherRectangle& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherTriangle& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
template <class PointType_, class LabelType>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto Convex<PointType_, LabelType>::hausdorffDistanceL1(const OtherConvex& other) const {
    const auto worst_from_this = detail::maxVertexDistanceL1<ResultNumber>(*this, other);
    const auto worst_from_other = detail::maxVertexDistanceL1<ResultNumber>(other, *this);
    return worst_from_this > worst_from_other ? worst_from_this : worst_from_other;
}
 
 
template <class PointType_, class TLabel>
template <class ResultNumber, MonotoneChainConcept OtherChain>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherChain& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// MonotoneChain
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber MonotoneChain<PointType, LabelType, Storage>::edgeMinDistanceL1(const OtherShape& other) const {
    assert(size() >= 1);
    if (size() == 1) {
        // A chain collapsed to a single vertex has no edge to measure from;
        // its distance is the distance from that vertex.
        return (*this)[0].template distanceL1<ResultNumber>(other);
    }
    ResultNumber best = this->template boundaryAt<false>(0).template distanceL1<ResultNumber>(other);
    for (std::size_t index = 1; index + 1 < size(); ++index) {
        const ResultNumber current =
            this->template boundaryAt<false>(index).template distanceL1<ResultNumber>(other);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherRectangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherTriangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherConvex& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType, class Storage>
template <class ResultNumber, MonotoneChainConcept OtherChain>
constexpr auto MonotoneChain<PointType, LabelType, Storage>::distanceL1(const OtherChain& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
// -----------------------------------------------------------------------------
// Polyline
 
template <class PointType, class LabelType>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber Polyline<PointType, LabelType>::edgeMinDistanceL1(const OtherShape& other) const {
    assert(size() >= 1);
    if (size() == 1) {
        // A polyline collapsed to a single vertex has no edge to measure from;
        // its distance is the distance from that vertex.
        return (*this)[0].template distanceL1<ResultNumber>(other);
    }
    ResultNumber best = this->template boundaryAt<false>(0).template distanceL1<ResultNumber>(other);
    for (std::size_t index = 1; index + 1 < size(); ++index) {
        const ResultNumber current =
            this->template boundaryAt<false>(index).template distanceL1<ResultNumber>(other);
        if (current < best) {
            best = current;
        }
    }
    return best;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PolylineConcept OtherPolyline>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherPolyline& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherRectangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherTriangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherConvex& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, MonotoneChainConcept OtherChain>
constexpr auto Polyline<PointType, LabelType>::distanceL1(const OtherChain& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType_, class TLabel>
template <class ResultNumber, PolylineConcept OtherPolyline>
constexpr auto Polygon<PointType_, TLabel>::distanceL1(const OtherPolyline& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
 
// -----------------------------------------------------------------------------
// HalfplaneIntersection
//
// Minimum over the region's boundary edges of the edge-to-shape L1 distance,
// mirroring squaredDistance. Disk is excluded (the library defines L1/LInf to
// a disk only from a point). Querying the empty region is undefined behavior.
 
namespace detail {
 
template <class ResultNumber, class Region, class Other>
constexpr ResultNumber regionEdgesDistanceL1(const Region& region, const Other& other) {
    ResultNumber best{};
    bool has = false;
    for (std::size_t i = 0; i < region.size(); ++i) {
        const ResultNumber current = std::visit(
            [&other](const auto& piece) {
                return static_cast<ResultNumber>(piece.template distanceL1<ResultNumber>(other));
            },
            region.template edge<ResultNumber>(i));
        if (!has || current < best) {
            best = current;
            has = true;
        }
    }
    return best;
}
 
}  // namespace detail
 
#define PGL_HPI_DISTANCE_L1(ConceptName, ArgType)                                              \
    template <class PointType, class LabelType>                                                \
    template <class ResultNumber, ConceptName ArgType>                                         \
    constexpr auto HalfplaneIntersection<PointType, LabelType>::distanceL1(                     \
        const ArgType& other) const {                                                          \
        if (intersects(other)) {                                                                \
            return ResultNumber{};                                                              \
        }                                                                                       \
        return detail::regionEdgesDistanceL1<ResultNumber>(*this, other);                       \
    }
 
PGL_HPI_DISTANCE_L1(PointConcept, OtherPoint)
PGL_HPI_DISTANCE_L1(SegmentConcept, OtherSegment)
PGL_HPI_DISTANCE_L1(OrientedSegmentConcept, OtherOrientedSegment)
PGL_HPI_DISTANCE_L1(LineConcept, OtherLine)
PGL_HPI_DISTANCE_L1(OrientedLineConcept, OtherOrientedLine)
PGL_HPI_DISTANCE_L1(RayConcept, OtherRay)
PGL_HPI_DISTANCE_L1(HalfplaneConcept, OtherHalfplane)
PGL_HPI_DISTANCE_L1(RectangleConcept, OtherRectangle)
PGL_HPI_DISTANCE_L1(TriangleConcept, OtherTriangle)
PGL_HPI_DISTANCE_L1(ConvexConcept, OtherConvex)
PGL_HPI_DISTANCE_L1(MonotoneChainConcept, OtherChain)
PGL_HPI_DISTANCE_L1(PolylineConcept, OtherPolyline)
PGL_HPI_DISTANCE_L1(PolygonConcept, OtherPolygon)
 
#undef PGL_HPI_DISTANCE_L1
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneIntersectionConcept OtherRegion>
constexpr auto HalfplaneIntersection<PointType, LabelType>::distanceL1(const OtherRegion& other) const {
    // Disjoint convex regions realize their distance on this region's
    // boundary; each edge re-dispatches into the other region's own edge scan.
    if (intersects(other)) {
        return ResultNumber{};
    }
    return detail::regionEdgesDistanceL1<ResultNumber>(*this, other);
}
 
 
// -----------------------------------------------------------------------------
// PolygonWithHoles
//
// See distance.hpp: a shape the closed region misses is nearest to a point of
// ∂A, so one scan over the edges of every ring answers all three metrics.
 
template <class PointType, class LabelType>
template <class ResultNumber, class OtherShape>
constexpr ResultNumber PolygonWithHoles<PointType, LabelType>::edgeMinDistanceL1(const OtherShape& other) const {
    ResultNumber best{};
    bool seeded = false;
    anyBoundaryEdge([&](const auto& edge) {
        const ResultNumber current = edge.template distanceL1<ResultNumber>(other);
        if (!seeded || current < best) {
            best = current;
            seeded = true;
        }
        return false;
    });
    return best;
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PointConcept OtherPoint>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherPoint& point) const {
    if (intersects(point)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(point);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, SegmentConcept OtherSegment>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedSegmentConcept OtherOrientedSegment>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherOrientedSegment& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, LineConcept OtherLine>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, OrientedLineConcept OtherOrientedLine>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherOrientedLine& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RayConcept OtherRay>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherRay& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneConcept OtherHalfplane>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherHalfplane& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, RectangleConcept OtherRectangle>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherRectangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, TriangleConcept OtherTriangle>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherTriangle& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, ConvexConcept OtherConvex>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherConvex& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PolygonConcept OtherPolygon>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherPolygon& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PolygonWithHolesConcept OtherRegion>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherRegion& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, MonotoneChainConcept OtherChain>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherChain& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PolylineConcept OtherPolyline>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherPolyline& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
template <class PointType, class LabelType>
template <class ResultNumber, HalfplaneIntersectionConcept OtherIntersection>
constexpr auto PolygonWithHoles<PointType, LabelType>::distanceL1(const OtherIntersection& other) const {
    if (intersects(other)) {
        return ResultNumber{};
    }
    return this->template edgeMinDistanceL1<ResultNumber>(other);
}
 
// No Disk overload: the library defines the L1 and LInf distances to a disk
// only from a point.
 
 
// ---------------------------------------------------------------------------
// PolygonSet
//
// The distance to a union is the minimum of the distances, with no caveat and
// no operand it fails for. An empty set has no component to measure from and
// reports zero.
 
template <class PointType, class LabelType>
template <class ResultNumber, detail::SetOperandConcept OtherShape>
    requires detail::ComponentDistanceL1Concept<ResultNumber, PolygonWithHoles<PointType>, OtherShape>
auto PolygonSet<PointType, LabelType>::distanceL1(const OtherShape& other) const {
    return minOverComponents([&other](const ComponentType& component) {
        return component.template distanceL1<ResultNumber>(other);
    });
}
 
template <class PointType, class LabelType>
template <class ResultNumber, PolygonSetConcept OtherSet>
auto PolygonSet<PointType, LabelType>::distanceL1(const OtherSet& other) const {
    ResultNumber best{};
    bool seeded = false;
    for (const auto& component : other) {
        const ResultNumber current = this->template distanceL1<ResultNumber>(component);
        if (!seeded || current < best) {
            best = current;
            seeded = true;
        }
    }
    return best;
}
 
}  // namespace pgl