minkowskisum.hpp

Go to the documentation of this file.

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

 
#include <algorithm>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace pgl {
 
namespace detail {

template <class Shape>
std::vector<Convex<typename Shape::PointType>> minkowskiConvexPieces(const Shape& shape) {
    using ShapePoint = typename Shape::PointType;
    using PieceConvex = Convex<ShapePoint>;
 
    std::vector<PieceConvex> pieces;
    // Untrusted throughout: the constructor's Graham scan is what orders the
    // vertices and prunes a piece that has collapsed, and the convex merge below
    // relies on both.
    const auto add = [&pieces](std::vector<ShapePoint> vertices) {
        pieces.push_back(PieceConvex(std::move(vertices)));
    };
 
    if constexpr (is_polygon_v<Shape> || is_polygon_with_holes_v<Shape>) {
        const auto addEdge = [&add](const auto& edge) { add({edge.min(), edge.max()}); };
        if (shape.isDegenerate()) {
            if constexpr (is_polygon_with_holes_v<Shape>) {
                for (const auto& edge : shape.edges()) {
                    addEdge(edge);
                }
            } else {
                for (const auto& edge : shape.edgesView()) {
                    addEdge(edge);
                }
            }
            return pieces;
        }
        // Already canonical, and already `Convex`: no Graham scan to redo.
        pieces = shape.convexPartition();
        if constexpr (is_polygon_with_holes_v<Shape>) {
            for (const auto& slit : regionSlits(shape)) {
                addEdge(slit);
            }
        }
    } else if constexpr (is_polyline_v<Shape> || is_monotone_chain_v<Shape>) {
        // A chain of one vertex covers that vertex and has no edge to say so
        // with; every other chain is exactly the union of its edges, zero-length
        // ones included (the Graham scan prunes those to a point). An x-monotone
        // chain decomposes the same way — it is a polyline that happens to be
        // sorted, and nothing here needs the sorting.
        if (shape.size() == 1) {
            add({shape[0]});
        }
        for (const auto& edge : shape.edgesView()) {
            add({edge.min(), edge.max()});
        }
    } else {
        std::vector<ShapePoint> vertices;
        for (const auto& vertex : shape.vertices()) {
            vertices.emplace_back(vertex);
        }
        add(std::move(vertices));
    }
    return pieces;
}

template <class Shape, class OtherShape>
decltype(auto) holeFilteredFor(const Shape& shape, const OtherShape& other) {
    if constexpr (is_polygon_with_holes_v<Shape>) {
        if (shape.holes().empty()) {
            return Shape(shape);
        }
        using Extent =
            std::common_type_t<typename Shape::NumberType, typename OtherShape::NumberType>;
        const auto box = other.bbox();
        const Extent width = Extent(box.max().x()) - Extent(box.min().x());
        const Extent height = Extent(box.max().y()) - Extent(box.min().y());
 
        std::vector<typename Shape::PolygonType> kept;
        for (const auto& hole : shape.holes()) {
            const auto holeBox = hole.bbox();
            if (Extent(holeBox.max().x()) - Extent(holeBox.min().x()) >= width &&
                Extent(holeBox.max().y()) - Extent(holeBox.min().y()) >= height) {
                kept.push_back(hole);
            }
        }
        return Shape(shape.outer(), std::move(kept), true);
    } else {
        return (shape);  // nothing that could have a hole in it
    }
}

template <class ResultPoint, class ShapeA, class ShapeB>
PolygonSet<ResultPoint> decomposedMinkowskiSum(const ShapeA& a,
                                                                  const ShapeB& b) {
    const auto left = minkowskiConvexPieces(a);
    const auto right = minkowskiConvexPieces(b);
    using SumConvex = decltype(minkowskiConvexSum(left.front(), right.front()));
 
    std::vector<SumConvex> sums;
    sums.reserve(left.size() * right.size());
    for (const auto& piece : left) {
        for (const auto& other : right) {
            SumConvex sum = minkowskiConvexSum(piece, other);
            if (!sum.isDegenerate()) {
                sums.push_back(std::move(sum));
            }
        }
    }
    // Repeats are common once either decomposition has congruent pieces in the
    // same place — two slits sharing a direction, or a rectilinear operand whose
    // triangles come in matching pairs — and each duplicate would otherwise pay
    // for its whole boundary again in the arrangement.
    std::sort(sums.begin(), sums.end());
    sums.erase(std::unique(sums.begin(), sums.end()), sums.end());
 
    return regularizedUnionOf<ResultPoint>(sums);
}
 
// -----------------------------------------------------------------------------
// What an operand is, as far as the sum is concerned. Three questions decide
// which construction @ref regularizedMinkowskiSum runs, and all three are answered
// at run time: a `Polygon` that happens to be convex takes the same path a
// `Convex` does, and it is only convex on this particular call.

template <class Shape>
bool minkowskiIsConvex(const Shape& shape) {
    if constexpr (is_polygon_v<Shape>) {
        return shape.isConvex();
    } else if constexpr (is_polygon_with_holes_v<Shape>) {
        return shape.holes().empty() && shape.outer().isConvex();
    } else if constexpr (is_polyline_v<Shape> || is_monotone_chain_v<Shape>) {
        return false;
    } else {
        return true;
    }
}

template <class Shape>
bool minkowskiHasArea(const Shape& shape) {
    if constexpr (is_segment_v<Shape> || is_oriented_segment_v<Shape> ||
                  is_polyline_v<Shape> || is_monotone_chain_v<Shape>) {
        return false;
    } else {
        return !shape.isDegenerate();
    }
}

template <class Shape>
auto minkowskiAsConvex(const Shape& shape) {
    using ShapePoint = typename Shape::PointType;
    if constexpr (is_convex_v<Shape>) {
        return shape;
    } else if constexpr (is_polygon_v<Shape>) {
        return Convex<ShapePoint>(shape.vertices());
    } else if constexpr (is_polygon_with_holes_v<Shape>) {
        return Convex<ShapePoint>(shape.outer().vertices());
    } else {
        std::vector<ShapePoint> vertices;
        for (const auto& vertex : shape.vertices()) {
            vertices.emplace_back(vertex);
        }
        return Convex<ShapePoint>(std::move(vertices));
    }
}
 
// -----------------------------------------------------------------------------
// The x-monotone chain's own sum, which needs none of the above.

template <class Number>
using chainWide_t = promoted_number_t<promoted_number_t<Number>>;

template <class Number>
constexpr int chainSignOf(const Number& value) {
    const Number zero{};
    return value > zero ? 1 : (value < zero ? -1 : 0);
}

template <class P, class Q>
constexpr int chainSideSign(const P& a, const P& b, const Q& p) {
    return signOf(orientationSign(a, b, p));
}

template <class P>
struct ChainEnvelopeVertex {
    P point;                  
    P a, b;                   
    P c, d;                   
    bool isCrossing = false;  
};

template <class P>
constexpr ChainEnvelopeVertex<P> chainVertexAt(const P& point) {
    return ChainEnvelopeVertex<P>{point, P(), P(), P(), P(), false};
}

template <class P>
constexpr ChainEnvelopeVertex<P> chainVertexCrossing(const P& a, const P& b, const P& c,
                                                     const P& d) {
    return ChainEnvelopeVertex<P>{P(), a, b, c, d, true};
}

template <class P, class Number>
constexpr ChainEnvelopeVertex<P> chainVertexOnVertical(const P& a, const P& b, const Number& x) {
    using Coordinate = typename P::NumberType;
    const Coordinate cut = static_cast<Coordinate>(x);
    return chainVertexCrossing(a, b, P(cut, Coordinate{}), P(cut, Coordinate(1)));
}

template <class P>
constexpr int chainVertexSide(const ChainEnvelopeVertex<P>& vertex, const P& u1, const P& u2) {
    if (!vertex.isCrossing) {
        return chainSideSign(u1, u2, vertex.point);
    }
    using Wide = chainWide_t<typename P::NumberType>;
    const auto wide = [](const auto& value) -> decltype(auto) {
        return detail::asNumber<Wide>(value);
    };
 
    const Wide rx = wide(vertex.b.x()) - wide(vertex.a.x());
    const Wide ry = wide(vertex.b.y()) - wide(vertex.a.y());
    const Wide sx = wide(vertex.d.x()) - wide(vertex.c.x());
    const Wide sy = wide(vertex.d.y()) - wide(vertex.c.y());
    const Wide den = rx * sy - ry * sx;
    assert(den != Wide{} && "an envelope only ever names a crossing of two crossing lines");
    const Wide num =
        (wide(vertex.c.x()) - wide(vertex.a.x())) * sy - (wide(vertex.c.y()) - wide(vertex.a.y())) * sx;
 
    const Wide ux = wide(u2.x()) - wide(u1.x());
    const Wide uy = wide(u2.y()) - wide(u1.y());
    const Wide base =
        ux * (wide(vertex.a.y()) - wide(u1.y())) - uy * (wide(vertex.a.x()) - wide(u1.x()));
    const Wide slope = ux * ry - uy * rx;
 
    return chainSignOf(base * den + slope * num) * chainSignOf(den);
}

template <class P, class Number>
constexpr int chainVertexXSign(const ChainEnvelopeVertex<P>& vertex, const Number& x) {
    if (!vertex.isCrossing) {
        return chainSignOf(vertex.point.x() - x);
    }
    using Wide = chainWide_t<typename P::NumberType>;
    const auto wide = [](const auto& value) -> decltype(auto) {
        return detail::asNumber<Wide>(value);
    };
 
    const Wide rx = wide(vertex.b.x()) - wide(vertex.a.x());
    const Wide ry = wide(vertex.b.y()) - wide(vertex.a.y());
    const Wide sx = wide(vertex.d.x()) - wide(vertex.c.x());
    const Wide sy = wide(vertex.d.y()) - wide(vertex.c.y());
    const Wide den = rx * sy - ry * sx;
    assert(den != Wide{} && "an envelope only ever names a crossing of two crossing lines");
    const Wide num =
        (wide(vertex.c.x()) - wide(vertex.a.x())) * sy - (wide(vertex.c.y()) - wide(vertex.a.y())) * sx;
 
    return chainSignOf((wide(vertex.a.x()) - wide(x)) * den + rx * num) * chainSignOf(den);
}

template <class ResultPoint, class P>
ResultPoint chainVertexPoint(const ChainEnvelopeVertex<P>& vertex) {
    using ResultNumber = typename ResultPoint::NumberType;
    if (!vertex.isCrossing) {
        return ResultPoint(detail::asNumber<ResultNumber>(vertex.point.x()),
                           detail::asNumber<ResultNumber>(vertex.point.y()));
    }
    using Wide = chainWide_t<typename P::NumberType>;
    const auto wide = [](const auto& value) -> decltype(auto) {
        return detail::asNumber<Wide>(value);
    };
 
    const Wide rx = wide(vertex.b.x()) - wide(vertex.a.x());
    const Wide ry = wide(vertex.b.y()) - wide(vertex.a.y());
    const Wide sx = wide(vertex.d.x()) - wide(vertex.c.x());
    const Wide sy = wide(vertex.d.y()) - wide(vertex.c.y());
    const Wide den = rx * sy - ry * sx;
    assert(den != Wide{} && "an envelope only ever names a crossing of two crossing lines");
    const Wide num =
        (wide(vertex.c.x()) - wide(vertex.a.x())) * sy - (wide(vertex.c.y()) - wide(vertex.a.y())) * sx;
 
    const Wide xn = wide(vertex.a.x()) * den + rx * num;
    const Wide yn = wide(vertex.a.y()) * den + ry * num;
 
    if constexpr (extended_integral<Wide>) {
        // An exact fraction over the widened integers, handed to the same
        // conversion the boolean engine makes at the end of an arrangement.
        return ResultPoint(static_cast<ResultNumber>(Rational<Wide>(xn, den)),
                           static_cast<ResultNumber>(Rational<Wide>(yn, den)));
    } else {
        // The coordinate type already divides exactly (a Rational) or inexactly
        // by nature (a floating-point one); either way it needs no wrapper.
        return ResultPoint(static_cast<ResultNumber>(xn / den),
                           static_cast<ResultNumber>(yn / den));
    }
}

template <class P>
struct ChainEnvelopeArc {
    P a;                            
    P b;                            
    ChainEnvelopeVertex<P> start;   
    ChainEnvelopeVertex<P> step;    
    typename P::NumberType stepAt{};  
    bool hasStep = false;           
};

template <class P>
ChainEnvelopeArc<P> chainArcEnteredAt(const P& a, const P& b,
                                      const ChainEnvelopeVertex<P>& start) {
    ChainEnvelopeArc<P> arc;
    arc.a = a;
    arc.b = b;
    arc.start = start;
    return arc;
}

template <class P>
ChainEnvelopeArc<P> chainArcSteppedInto(const P& a, const P& b,
                                        const ChainEnvelopeVertex<P>& start,
                                        const ChainEnvelopeVertex<P>& step,
                                        const typename P::NumberType& x) {
    ChainEnvelopeArc<P> arc = chainArcEnteredAt(a, b, start);
    arc.step = step;
    arc.stepAt = x;
    arc.hasStep = true;
    return arc;
}

template <class P>
void chainMergeArc(std::vector<ChainEnvelopeArc<P>>& envelope, const std::vector<P>& arc,
                   bool keepHigher) {
    assert(arc.size() >= 2 && "a piece with no span cannot bound an envelope");
    const int keep = keepHigher ? 1 : -1;
 
    const auto plain = [&arc](std::size_t index) {
        return chainArcEnteredAt(arc[index], arc[index + 1], chainVertexAt(arc[index]));
    };
 
    if (envelope.empty()) {
        for (std::size_t index = 0; index + 1 < arc.size(); ++index) {
            envelope.push_back(plain(index));
        }
        return;
    }
 
    // Where the boundary arrives at an arc: on the previous arc's segment when a
    // step brings it there, which is the value the span before it ends on.
    const auto entry = [&envelope](std::size_t index) -> const ChainEnvelopeVertex<P>& {
        return envelope[index].hasStep ? envelope[index].step : envelope[index].start;
    };
 
    const auto& x0 = arc.front().x();
    std::size_t i = envelope.size() - 1;
    while (i > 0 && chainVertexXSign(entry(i), x0) > 0) {
        --i;
    }
 
    // Arcs up to and including `i` survive; whatever the sweep decides is
    // appended after them, so it may keep reading the old envelope as it goes.
    std::size_t kept = i + 1;
    std::vector<ChainEnvelopeArc<P>> merged;
    std::size_t j = 0;
 
    // Who bounds the sum where the incoming arc starts. That start is a vertex of
    // the arc, so it lies on it and the envelope's own segment decides.
    const int startSide = -chainSideSign(envelope[i].a, envelope[i].b, arc.front());
    int winner = keep * startSide >= 0 ? 1 : -1;
    if (winner < 0) {
        // The incoming piece starts beyond the envelope, so the boundary steps
        // across to it. It leaves the envelope wherever the boundary had reached:
        // partway along the arc in force, or — when that arc begins right here,
        // which leaves it bounding nothing at all — at the point that arc was
        // itself entered at.
        ChainEnvelopeVertex<P> from;
        if (chainVertexXSign(entry(i), x0) == 0) {
            from = entry(i);
            kept = i;
        } else {
            from = chainVertexOnVertical(envelope[i].a, envelope[i].b, x0);
        }
        merged.push_back(chainArcSteppedInto(arc[0], arc[1], chainVertexAt(arc[0]), from, x0));
    }
 
    while (true) {
        const bool envelopeEndsLast = i + 1 == envelope.size();
 
        // Which of the two spans ends first; a negative order is the envelope's.
        const int order = envelopeEndsLast
                              ? chainSignOf(envelope[i].b.x() - arc[j + 1].x())
                              : chainVertexXSign(entry(i + 1), arc[j + 1].x());
 
        // Which of the two is ahead where the span ends, read at whichever of the
        // two segments that point belongs to.
        int side;
        if (order <= 0) {
            side = envelopeEndsLast ? chainSideSign(arc[j], arc[j + 1], envelope[i].b)
                                    : chainVertexSide(entry(i + 1), arc[j], arc[j + 1]);
        } else {
            side = -chainSideSign(envelope[i].a, envelope[i].b, arc[j + 1]);
        }
        const int ahead = keep * side;
        if (ahead != 0 && ahead != winner) {
            // The two segments swapped places inside the span, so they cross
            // there. Which two segments cross is all the boundary needs to know.
            const ChainEnvelopeVertex<P> crossing =
                chainVertexCrossing(envelope[i].a, envelope[i].b, arc[j], arc[j + 1]);
            merged.push_back(ahead > 0
                                 ? chainArcEnteredAt(envelope[i].a, envelope[i].b, crossing)
                                 : chainArcEnteredAt(arc[j], arc[j + 1], crossing));
            winner = ahead;
        }
 
        if (order >= 0) {
            // The incoming arc's segment ends here. It runs at least as far as
            // the envelope, so running out of segments means the merge is done.
            ++j;
            if (j + 1 >= arc.size()) {
                break;
            }
            if (winner < 0) {
                merged.push_back(plain(j));
            }
        }
        if (order <= 0) {
            if (envelopeEndsLast) {
                // Past the old envelope's right end the incoming arc is alone. It
                // takes over there, over a step unless the two happen to meet.
                if (winner > 0) {
                    const auto& stepAt = envelope[i].b.x();
                    merged.push_back(
                        side == 0
                            ? chainArcEnteredAt(arc[j], arc[j + 1], chainVertexAt(envelope[i].b))
                            : chainArcSteppedInto(
                                  arc[j], arc[j + 1],
                                  chainVertexOnVertical(arc[j], arc[j + 1], stepAt),
                                  chainVertexAt(envelope[i].b), stepAt));
                }
                for (std::size_t rest = j + 1; rest + 1 < arc.size(); ++rest) {
                    merged.push_back(plain(rest));
                }
                break;
            }
            ++i;
            if (!envelope[i].hasStep) {
                if (winner > 0) {
                    merged.push_back(envelope[i]);
                }
            } else {
                // The envelope jumps here, so whichever of the two bounds the sum
                // can change without the segments ever meeting. Both ends of what
                // the boundary actually walks are read afresh: the near one from
                // whoever bounded it before the jump, the far one from whoever
                // bounds it after.
                const int afterSide = chainVertexSide(envelope[i].start, arc[j], arc[j + 1]);
                const int after = afterSide == 0 ? winner : keep * afterSide;
                const auto& stepAt = envelope[i].stepAt;
                if (after > 0) {
                    merged.push_back(
                        winner > 0 ? envelope[i]
                                   : chainArcSteppedInto(
                                         envelope[i].a, envelope[i].b, envelope[i].start,
                                         chainVertexOnVertical(arc[j], arc[j + 1], stepAt),
                                         stepAt));
                } else if (winner > 0) {
                    merged.push_back(chainArcSteppedInto(
                        arc[j], arc[j + 1], chainVertexOnVertical(arc[j], arc[j + 1], stepAt),
                        envelope[i].step, stepAt));
                }
                winner = after;
            }
        }
    }
 
    envelope.resize(kept);
    envelope.insert(envelope.end(), std::make_move_iterator(merged.begin()),
                    std::make_move_iterator(merged.end()));
}

template <class P, class L>
std::vector<P> chainPieceArc(const Convex<P, L>& piece, bool upper) {
    const std::size_t n = piece.size();
    const std::size_t top = piece.maxIndex();
    assert(n >= 2 && "a piece with no span has no arc; an operand of no width is handled apart");
 
    std::vector<P> arc;
    if (upper) {
        // Clockwise from the lexicographic minimum: the boundary above, already
        // in increasing lexicographic order.
        arc.reserve(n - top + 1);
        arc.push_back(piece[0]);
        for (std::size_t k = n; k > top; --k) {
            arc.push_back(piece[k - 1]);
        }
        std::size_t drop = 0;
        while (drop + 1 < arc.size() && arc[drop].x() == arc[drop + 1].x()) {
            ++drop;
        }
        arc.erase(arc.begin(), arc.begin() + static_cast<std::ptrdiff_t>(drop));
    } else {
        arc.reserve(top + 1);
        for (std::size_t k = 0; k <= top; ++k) {
            arc.push_back(piece[k]);
        }
        while (arc.size() >= 2 && arc[arc.size() - 2].x() == arc.back().x()) {
            arc.pop_back();
        }
    }
    return arc;
}

template <class ResultPoint, class P>
void chainAppendEnvelope(std::vector<ResultPoint>& walk,
                         const std::vector<ChainEnvelopeArc<P>>& envelope) {
    using ResultNumber = typename ResultPoint::NumberType;
    for (const ChainEnvelopeArc<P>& arc : envelope) {
        if (arc.hasStep) {
            walk.push_back(chainVertexPoint<ResultPoint>(arc.step));
        }
        walk.push_back(chainVertexPoint<ResultPoint>(arc.start));
    }
    walk.emplace_back(detail::asNumber<ResultNumber>(envelope.back().b.x()),
                      detail::asNumber<ResultNumber>(envelope.back().b.y()));
}

template <class ResultPoint>
void chainDropRepeated(std::vector<ResultPoint>& walk) {
    walk.erase(std::unique(walk.begin(), walk.end()), walk.end());
    while (walk.size() >= 2 && walk.front() == walk.back()) {
        walk.pop_back();
    }
}

template <class ResultPoint>
void chainDropCollinear(std::vector<ResultPoint>& walk) {
    if (walk.size() < 3) {
        return;
    }
    std::vector<ResultPoint> kept;
    kept.reserve(walk.size());
    for (std::size_t index = 0; index < walk.size(); ++index) {
        const ResultPoint& previous = walk[(index + walk.size() - 1) % walk.size()];
        const ResultPoint& vertex = walk[index];
        const ResultPoint& next = walk[(index + 1) % walk.size()];
        // Only the sign of that dot product is wanted — whether the walk carries
        // on in the same direction or doubles back — so dotSign answers it,
        // computing in the promoted coordinate type instead of one that a long
        // stretch of the walk can overflow.
        const bool straight = collinear(previous, vertex, next) &&
                              dotSign(vertex - previous, next - vertex) > 0;
        if (!straight) {
            kept.push_back(vertex);
        }
    }
    walk.swap(kept);
}

template <class ResultPoint, class ChainType, class ConvexOperand>
std::vector<ResultPoint> chainSumWalk(const ChainType& chain, const ConvexOperand& other) {
    using SumPoint = minkowskiPoint_t<ChainType, ConvexOperand>;
    using SumNumber = typename SumPoint::NumberType;
    using ResultNumber = typename ResultPoint::NumberType;
 
    const auto convert = [](const auto& vertex) {
        return ResultPoint(detail::asNumber<ResultNumber>(vertex.x()),
                           detail::asNumber<ResultNumber>(vertex.y()));
    };
    const auto shifted = [](const auto& p, const auto& q) {
        return SumPoint(detail::asNumber<SumNumber>(p.x()) + detail::asNumber<SumNumber>(q.x()),
                        detail::asNumber<SumNumber>(p.y()) + detail::asNumber<SumNumber>(q.y()));
    };
 
    const std::vector<SumPoint> operandVertices = minkowskiVertices<SumPoint>(other);
    if (chain.empty() || operandVertices.empty()) {
        return {};  // an empty operand absorbs
    }
 
    const auto byX = [](const SumPoint& p, const SumPoint& q) { return p.x() < q.x(); };
    const auto [leftmost, rightmost] =
        std::minmax_element(operandVertices.begin(), operandVertices.end(), byX);
    if (leftmost->x() == rightmost->x()) {
        // An operand of zero width — a vertical segment, or a shape that has
        // collapsed onto one — leaves the sum's fibre over x the chain's own
        // fibre widened by the operand's, so the boundary traces the chain out
        // through the operand's top and back through its bottom.
        const auto byY = [](const SumPoint& p, const SumPoint& q) { return p.y() < q.y(); };
        const auto [lowest, highest] =
            std::minmax_element(operandVertices.begin(), operandVertices.end(), byY);
        std::vector<ResultPoint> swept;
        swept.reserve(2 * chain.size());
        for (std::size_t index = 0; index < chain.size(); ++index) {
            swept.push_back(convert(shifted(chain[index], *lowest)));
        }
        for (std::size_t index = chain.size(); index > 0; --index) {
            swept.push_back(convert(shifted(chain[index - 1], *highest)));
        }
        chainDropRepeated(swept);
        chainDropCollinear(swept);
        return swept;
    }
 
    std::vector<ChainEnvelopeArc<SumPoint>> lower;
    std::vector<ChainEnvelopeArc<SumPoint>> upper;
    const auto mergePiece = [&lower, &upper](const auto& piece) {
        chainMergeArc(lower, chainPieceArc(piece, false), false);
        chainMergeArc(upper, chainPieceArc(piece, true), true);
    };
 
    if (chain.size() == 1) {
        // No edge to sweep along: the sum is the operand, translated.
        std::vector<SumPoint> translated;
        translated.reserve(operandVertices.size());
        for (const SumPoint& vertex : operandVertices) {
            translated.push_back(shifted(vertex, chain[0]));
        }
        mergePiece(Convex<SumPoint>(translated));
    } else {
        for (const auto& edge : chain.edgesView()) {
            mergePiece(minkowskiConvexSum(edge, other));
        }
    }
 
    std::vector<ResultPoint> walk;
    chainAppendEnvelope(walk, lower);
    const std::size_t fromRight = walk.size();
    chainAppendEnvelope(walk, upper);
    // The upper envelope was read left to right; the boundary walks it back.
    std::reverse(walk.begin() + static_cast<std::ptrdiff_t>(fromRight), walk.end());
    chainDropRepeated(walk);
    chainDropCollinear(walk);
    return walk;
}

template <class ResultPoint, class ChainType, class ConvexOperand>
Polygon<ResultPoint> chainMinkowskiSum(const ChainType& chain, const ConvexOperand& other) {
    std::vector<ResultPoint> walk = chainSumWalk<ResultPoint>(chain, other);
    // The walk already runs counterclockwise — the lower boundary left to right,
    // then the upper one back — and a walk with no area has no orientation to get
    // wrong, so all the canonical form still wants is its lexicographically
    // smallest vertex first. Rotating it here rather than leaving it to the
    // constructor skips an exact signed area over the whole ring, which for a
    // rational result type is the one costly thing left in this construction: its
    // running denominator is the common multiple of every crossing's.
    std::rotate(walk.begin(), std::min_element(walk.begin(), walk.end()), walk.end());
    return Polygon<ResultPoint>(std::move(walk), true);
}
 
// -----------------------------------------------------------------------------
// The boundary decomposition: what a convex operand buys the other one.

template <class P>
std::vector<std::vector<P>> minkowskiMonotoneRuns(const std::vector<P>& walk) {
    std::vector<std::vector<P>> runs;
    const auto direction = [](const P& from, const P& to) {
        return from == to ? 0 : (from < to ? 1 : -1);
    };
 
    std::size_t start = 0;
    while (start + 1 < walk.size()) {
        const int forward = direction(walk[start], walk[start + 1]);
        if (forward == 0) {
            ++start;  // a repeated vertex spans no edge
            continue;
        }
        std::size_t end = start + 1;
        while (end + 1 < walk.size() && direction(walk[end], walk[end + 1]) == forward) {
            ++end;
        }
        std::vector<P> run(walk.begin() + static_cast<std::ptrdiff_t>(start),
                           walk.begin() + static_cast<std::ptrdiff_t>(end) + 1);
        if (forward < 0) {
            std::reverse(run.begin(), run.end());
        }
        runs.push_back(std::move(run));
        start = end;
    }
    return runs;
}

template <class Shape>
std::vector<std::vector<typename Shape::PointType>> minkowskiBoundaryRuns(const Shape& shape) {
    using ShapePoint = typename Shape::PointType;
 
    std::vector<std::vector<ShapePoint>> walks;
    const auto addRing = [&walks](const auto& ring) {
        std::vector<ShapePoint> walk = ring.vertices();
        if (!walk.empty()) {
            walk.push_back(walk.front());
        }
        walks.push_back(std::move(walk));
    };
    if constexpr (is_polygon_with_holes_v<Shape>) {
        addRing(shape.outer());
        for (const auto& hole : shape.holes()) {
            addRing(hole);
        }
    } else if constexpr (is_polygon_v<Shape>) {
        addRing(shape);
    } else {
        // A chain is open: no closing edge, and its own vertex order is the walk.
        std::vector<ShapePoint> walk;
        walk.reserve(shape.size());
        for (std::size_t index = 0; index < shape.size(); ++index) {
            walk.push_back(shape[index]);
        }
        walks.push_back(std::move(walk));
    }
 
    std::vector<std::vector<ShapePoint>> runs;
    for (const std::vector<ShapePoint>& walk : walks) {
        std::vector<std::vector<ShapePoint>> walkRuns = minkowskiMonotoneRuns(walk);
        if (walkRuns.empty() && !walk.empty()) {
            // No run means no two consecutive vertices differ, so the whole walk
            // is one point. It still sums to something — the operand translated
            // there — and a chain of that single vertex is what says so.
            walkRuns.push_back({walk.front()});
        }
        runs.insert(runs.end(), std::make_move_iterator(walkRuns.begin()),
                    std::make_move_iterator(walkRuns.end()));
    }
    return runs;
}

template <class ExactPoint, class Shape, class ConvexOperand>
std::vector<PolygonWithHoles<ExactPoint>> minkowskiBoundaryPieces(
    const Shape& shape, const ConvexOperand& other,
    std::vector<std::vector<typename Shape::PointType>> runs) {
    using ShapePoint = typename Shape::PointType;
    using SumPoint = minkowskiPoint_t<Shape, ConvexOperand>;
    using SumNumber = typename SumPoint::NumberType;
    using ExactNumber = typename ExactPoint::NumberType;
    using ExactPolygon = Polygon<ExactPoint>;
 
    std::vector<PolygonWithHoles<ExactPoint>> pieces;
    pieces.reserve(runs.size() + 1);
 
    for (std::vector<ShapePoint>& run : runs) {
        const MonotoneChain<ShapePoint> chain(std::move(run), true);
        ExactPolygon sum = chainMinkowskiSum<ExactPoint>(chain, other);
        if (sum.size() >= 3) {
            pieces.emplace_back(std::move(sum), std::vector<ExactPolygon>{}, true);
        }
    }
 
    if constexpr (is_polygon_v<Shape> || is_polygon_with_holes_v<Shape>) {
        // The interior term. A boundary with no area beside it needs none: the
        // runs already cover such a shape entirely.
        if (!shape.isDegenerate()) {
            const std::vector<SumPoint> operandVertices = minkowskiVertices<SumPoint>(other);
            if (operandVertices.empty()) {
                return {};  // an empty operand absorbs
            }
            const SumPoint& q0 = operandVertices.front();
            // Translating a ring preserves both the lexicographic order of its
            // vertices and its orientation, so the canonical form survives and
            // the rings can be rebuilt trusted.
            const auto translated = [&q0](const auto& ring) {
                std::vector<ExactPoint> moved;
                moved.reserve(ring.size());
                for (const auto& vertex : ring.vertices()) {
                    moved.emplace_back(static_cast<ExactNumber>(detail::asNumber<SumNumber>(vertex.x()) +
                                                                q0.x()),
                                       static_cast<ExactNumber>(detail::asNumber<SumNumber>(vertex.y()) +
                                                                q0.y()));
                }
                return ExactPolygon(std::move(moved), true);
            };
            if constexpr (is_polygon_with_holes_v<Shape>) {
                std::vector<ExactPolygon> holes;
                holes.reserve(shape.holes().size());
                for (const auto& hole : shape.holes()) {
                    holes.push_back(translated(hole));
                }
                pieces.emplace_back(translated(shape.outer()), std::move(holes), true);
            } else {
                pieces.emplace_back(translated(shape), std::vector<ExactPolygon>{}, true);
            }
        }
    }
    return pieces;
}

template <class Shape>
inline constexpr bool minkowskiHasWalkableBoundary =
    is_polygon_v<Shape> || is_polygon_with_holes_v<Shape> || is_polyline_v<Shape> ||
    is_monotone_chain_v<Shape>;

template <class Shape>
bool minkowskiHasSimpleBoundary(const Shape& shape) {
    if constexpr (is_polygon_with_holes_v<Shape>) {
        return shape.holes().empty() || regionSlits(shape).empty();
    } else {
        return is_polygon_v<Shape> || is_polyline_v<Shape> || is_monotone_chain_v<Shape>;
    }
}

template <class Ring>
std::size_t minkowskiReflexCount(const Ring& ring, bool isHole) {
    const std::size_t n = ring.size();
    if (n < 3) {
        return 0;
    }
    std::size_t reflex = 0;
    for (std::size_t i = 0; i < n; ++i) {
        const auto turn = orientationSign(ring[(i + n - 1) % n], ring[i], ring[(i + 1) % n]);
        if (isHole ? turn > 0 : turn < 0) {
            ++reflex;
        }
    }
    return reflex;
}

template <class Shape>
std::pair<std::size_t, std::size_t> minkowskiPieceEstimate(const Shape& shape) {
    if constexpr (is_polygon_v<Shape> || is_polygon_with_holes_v<Shape>) {
        std::size_t edges = 0;
        std::size_t reflex = 0;
        std::size_t holes = 0;
        if constexpr (is_polygon_with_holes_v<Shape>) {
            edges = shape.outer().size();
            reflex = minkowskiReflexCount(shape.outer(), false);
            holes = shape.holes().size();
            for (const auto& hole : shape.holes()) {
                edges += hole.size();
                reflex += minkowskiReflexCount(hole, true);
            }
        } else {
            edges = shape.size();
            reflex = minkowskiReflexCount(shape, false);
        }
        const std::size_t pieces = reflex + 1 + holes;
        return {pieces, edges + 2 * (pieces - 1 + holes)};
    } else {
        const std::size_t edges = shape.size() > 1 ? shape.size() - 1 : 0;
        const std::size_t pieces = edges > 0 ? edges : 1;
        return {pieces, 2 * pieces};
    }
}

template <class Shape, class ConvexOperand, class Runs>
bool minkowskiBoundaryPays(const Shape& shape, const ConvexOperand& other, const Runs& runs) {
    const std::size_t operandEdges = other.size();
    std::size_t edges = 0;
    if constexpr (is_polygon_with_holes_v<Shape>) {
        edges = shape.outer().size();
        for (const auto& hole : shape.holes()) {
            edges += hole.size();
        }
    } else if constexpr (is_polygon_v<Shape>) {
        edges = shape.size();  // a ring has one edge per vertex
    } else {
        edges = shape.size() > 1 ? shape.size() - 1 : 0;
    }
    const auto [pieces, pieceVertices] = minkowskiPieceEstimate(shape);
    const std::size_t convexEdges = pieceVertices + pieces * operandEdges;
    const std::size_t boundaryEdges = 2 * edges + runs.size() * operandEdges;
    return 6 * boundaryEdges < 5 * convexEdges;
}
 
// -----------------------------------------------------------------------------
// The one-sided decomposition, which sums its pieces with the engine below and
// so has to be declared before it.
 
template <class ResultPoint, class ShapeA, class ShapeB>
PolygonSet<ResultPoint> regularizedMinkowskiSum(const ShapeA& a,
                                                                   const ShapeB& b);

template <class ExactPoint, class ShapeA, class ShapeB>
std::vector<PolygonWithHoles<ExactPoint>> minkowskiOneSidedPieces(const ShapeA& a,
                                                                  const ShapeB& b) {
    std::vector<PolygonWithHoles<ExactPoint>> pieces;
    for (const auto& piece : minkowskiConvexPieces(a)) {
        const PolygonSet<ExactPoint> sum = regularizedMinkowskiSum<ExactPoint>(b, piece);
        pieces.insert(pieces.end(), sum.begin(), sum.end());
    }
    return pieces;
}

template <class Shape>
std::size_t minkowskiPieceCount(const Shape& shape) {
    if constexpr (is_polygon_with_holes_v<Shape>) {
        return shape.vertexCount();
    } else {
        return shape.size();
    }
}

template <class ShapeA, class ShapeB>
bool minkowskiOneSidedDecomposesLeft(const ShapeA& a, const ShapeB& b) {
    return static_cast<long double>(minkowskiPieceCount(a)) * b.bbox().template area<long double>() <=
           static_cast<long double>(minkowskiPieceCount(b)) * a.bbox().template area<long double>();
}

template <class ResultPoint, class ShapeA, class ShapeB>
PolygonSet<ResultPoint> regularizedMinkowskiSum(const ShapeA& a,
                                                                   const ShapeB& b) {
    using SumPoint = minkowskiPoint_t<ShapeA, ShapeB>;
    using SumNumber = typename SumPoint::NumberType;
    using ExactPoint = Point<Exact1DNumber<SumNumber, SumNumber>>;
 
    // Filtering either operand leaves the other's outer boundary untouched, so
    // the two tests see the same boxes whichever order they run in.
    const auto& left = holeFilteredFor(a, b);
    const auto& right = holeFilteredFor(b, a);
 
    const bool leftConvex = minkowskiIsConvex(left);
    const bool rightConvex = minkowskiIsConvex(right);
 
    if (leftConvex && rightConvex) {
        const auto sum = minkowskiConvexSum(minkowskiAsConvex(left), minkowskiAsConvex(right));
        if (sum.isDegenerate()) {
            return {};  // nothing with area, so the regularized sum is empty
        }
        return PolygonSet<ResultPoint>(
            PolygonWithHoles<ResultPoint>(Polygon<ResultPoint>(sum.asPolygon())));
    }
 
    // The sum is commutative, so it is the convex operand that decides and not
    // which side it arrived on. Only one of the two branches can fire: a pair that
    // got past the test above has at most one convex operand, so the other is the
    // one to decompose.
    //
    // Both branches are gated on the coordinates being exact, and that is not a
    // performance choice. A convex piece sum never divides — every one of its
    // vertices is a sum of two input vertices — so the all-pairs decomposition is
    // exact in *any* coordinate type, floating-point included, and only the final
    // arrangement rounds. A run's sum does divide, to place the crossings of its
    // own sub-sums, and those rounded vertices then feed a second arrangement. On
    // integral operands stored as `double`, measured against the exact answer, that
    // costs a worst-case relative area error of 0.145 where the all-pairs
    // decomposition holds 2e-14, and it turns single regions into two or invents
    // holes. So the decomposition is taken only where its pieces can carry their
    // own crossings, which is exactly where `Exact1DNumber` is a rational.
    constexpr bool exactPieces = !std::is_floating_point_v<SumNumber>;
    if constexpr (exactPieces && minkowskiHasWalkableBoundary<std::remove_cvref_t<decltype(left)>>) {
        if (rightConvex && minkowskiHasArea(right) && minkowskiHasSimpleBoundary(left)) {
            const auto convexRight = minkowskiAsConvex(right);
            auto runs = minkowskiBoundaryRuns(left);
            if (minkowskiBoundaryPays(left, convexRight, runs)) {
                return regularizedUnionOf<ResultPoint>(
                    minkowskiBoundaryPieces<ExactPoint>(left, convexRight, std::move(runs)), true);
            }
        }
    }
    if constexpr (exactPieces && minkowskiHasWalkableBoundary<std::remove_cvref_t<decltype(right)>>) {
        if (leftConvex && minkowskiHasArea(left) && minkowskiHasSimpleBoundary(right)) {
            const auto convexLeft = minkowskiAsConvex(left);
            auto runs = minkowskiBoundaryRuns(right);
            if (minkowskiBoundaryPays(right, convexLeft, runs)) {
                return regularizedUnionOf<ResultPoint>(
                    minkowskiBoundaryPieces<ExactPoint>(right, convexLeft, std::move(runs)), true);
            }
        }
    }
 
    // Neither operand is convex, so one of them is decomposed and the other is
    // not. The recursion this opens is one level deep: every sum below has a
    // `Convex` operand and so is answered by construction 1 or 2, or — for a
    // piece with no area, which only a slit produces — by construction 4.
    //
    // Both operands must have **area**, and that is what the construction turns
    // on rather than a size or a vertex count. Its whole advantage is that the
    // pieces scatter instead of piling up, and that needs a decomposition into
    // pieces *small* relative to the operand — which triangles of a triangulation
    // are and the edges of a chain are not. A 32-vertex chain over the large
    // coordinate range has edges as long as the chain itself, so every piece of
    // its sum spans the whole answer and they all cross each other; measured
    // against a region of the same extent that is 3x *slower* than construction 4,
    // whichever of the two is decomposed. The same chain against a *small* polygon
    // is 22x faster, so there is something here for a criterion that can tell a
    // chain's pieces apart by length — but extent alone does not do it, since two
    // large regions gain 1.75x where a large chain and a large region lose.
    if constexpr (exactPieces) {
        if (!leftConvex && !rightConvex && minkowskiHasArea(left) &&
            minkowskiHasArea(right)) {
            auto pieces = minkowskiOneSidedDecomposesLeft(left, right)
                              ? minkowskiOneSidedPieces<ExactPoint>(left, right)
                              : minkowskiOneSidedPieces<ExactPoint>(right, left);
            return regularizedUnionOf<ResultPoint>(pieces, true);
        }
    }
 
    return decomposedMinkowskiSum<ResultPoint>(left, right);
}

template <class ResultPoint, class ShapeA, class ShapeB>
PolygonWithHoles<ResultPoint> singleRegionMinkowskiSum(const ShapeA& a, const ShapeB& b) {
    PolygonSet<ResultPoint> sum = regularizedMinkowskiSum<ResultPoint>(a, b);
    if (sum.componentCount() == 0) {
        return PolygonWithHoles<ResultPoint>();
    }
    return sum.component(0);
}

template <class ResultPoint, class SetT, class ShapeB>
PolygonSet<ResultPoint> setMinkowskiSum(const SetT& set, const ShapeB& other) {
    using SumPoint = minkowskiPoint_t<SetT, ShapeB>;
    using SumNumber = typename SumPoint::NumberType;
    using ExactPoint = Point<Exact1DNumber<SumNumber, SumNumber>>;
 
    std::vector<PolygonWithHoles<ExactPoint>> regions;
    const auto addSum = [&regions](const auto& left, const auto& right) {
        for (const auto& region : regularizedMinkowskiSum<ExactPoint>(left, right)) {
            regions.push_back(region);
        }
    };
    for (const auto& component : set) {
        if constexpr (is_polygon_set_v<ShapeB>) {
            for (const auto& piece : other) {
                addSum(component, piece);
            }
        } else {
            addSum(component, other);
        }
    }
    // A component sum is a region and may carry a slit, so the coverage
    // classifier is not available: this is the witness path, as it is wherever a
    // region is united rather than a convex piece.
    return regularizedUnionOf<ResultPoint>(regions);
}
 
}  // namespace detail
 
// -----------------------------------------------------------------------------
// Out-of-line: the region-valued Minkowski sums are declared in
// shape/polyline.hpp, shape/polygon.hpp and shape/polygonwithholes.hpp, which
// precede this header in the layering, but they can only be defined once
// Triangulation is visible.
 
// A pair with a body in it is one region — see @ref detail::singleRegionMinkowskiSum
// for why, and for what a degenerate operand costs.
 
#define PGL_DEFINE_REGION_MINKOWSKI_SUM(RECEIVER, CONCEPT, OPERAND)                        \
    template <class PointType_, class TLabel>                                              \
    template <class ResultNumber, CONCEPT OPERAND>                                         \
    PolygonWithHoles<Point<ResultNumber, typename PointType_::LabelType>>                  \
    RECEIVER<PointType_, TLabel>::minkowskiSum(const OPERAND& other) const {               \
        return detail::singleRegionMinkowskiSum<                                           \
            Point<ResultNumber, typename PointType_::LabelType>>(*this, other);            \
    }
 
// A pair with no body in it, where the regularization can genuinely leave several
// components for operands that are in no way degenerate.
 
#define PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(RECEIVER, CONCEPT, OPERAND)                    \
    template <class PointType_, class TLabel>                                              \
    template <class ResultNumber, CONCEPT OPERAND>                                         \
    PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>                        \
    RECEIVER<PointType_, TLabel>::minkowskiSum(const OPERAND& other) const {               \
        return detail::regularizedMinkowskiSum<                                            \
            Point<ResultNumber, typename PointType_::LabelType>>(*this, other);            \
    }
 
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, PolygonConcept, OtherPolygon)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, ConvexConcept, OtherConvex)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, TriangleConcept, OtherTriangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, RectangleConcept, OtherRectangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, PolygonWithHolesConcept, OtherRegion)
 
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, PolygonConcept, OtherPolygon)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, ConvexConcept, OtherConvex)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, TriangleConcept, OtherTriangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, RectangleConcept, OtherRectangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, PolygonWithHolesConcept, OtherRegion)
 
// A Polyline has no area, so most of its operands are the ones that have some.
// A Segment is the exception, and belongs here for the reason a chain does: two
// shapes with no area between them still sweep one out, since an edge of the
// chain and the segment span a parallelogram unless they are parallel.
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polyline, ConvexConcept, OtherConvex)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polyline, TriangleConcept, OtherTriangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polyline, RectangleConcept, OtherRectangle)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polyline, PolygonConcept, OtherPolygon)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polyline, PolygonWithHolesConcept, OtherRegion)
 
// The thinnest operand any of the three receivers takes. A segment is a single
// convex piece, so it costs one convex merge per piece of the receiver, and it
// is the receiver's own shape that decides whether the sweep strands a cavity.
// The two polygonal receivers are bodies and hold the sum in one region; the
// polyline is the pair with no body on either side, and stays a set.
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, SegmentConcept, OtherSegment)
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, OrientedSegmentConcept, OtherOriented)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, SegmentConcept, OtherSegment)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, OrientedSegmentConcept, OtherOriented)
PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(Polyline, SegmentConcept, OtherSegment)
PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(Polyline, OrientedSegmentConcept, OtherOriented)
 
// Two chains, the pair with the least area of all: both operands decompose into
// their edges, and a segment operand is the one-edge case of it. A polyline
// outranks a monotone chain and owns the mixed pair; the chain's own forwarder
// reaches this definition for it.
PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(Polyline, PolylineConcept, OtherPolyline)
PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(Polyline, MonotoneChainConcept, OtherChain)
 
// The chain's two non-convex pairs, mirrored so that neither spelling is the
// privileged one, exactly as `Polygon` and `PolygonWithHoles` mirror theirs. The
// two calls build the same piece sums and take the same union, so they agree by
// construction rather than by a forwarding hop.
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, PolylineConcept, OtherPolyline)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, PolylineConcept, OtherPolyline)
 
// A monotone chain against a non-convex receiver, which owns the pair by rank.
// The chain's monotonicity buys nothing here: it is the receiver's concavity that
// calls for a region, and no sorting of the chain's edges takes that back.
PGL_DEFINE_REGION_MINKOWSKI_SUM(Polygon, MonotoneChainConcept, OtherChain)
PGL_DEFINE_REGION_MINKOWSKI_SUM(PolygonWithHoles, MonotoneChainConcept, OtherChain)
 
#undef PGL_DEFINE_REGION_MINKOWSKI_SUM
 
// -----------------------------------------------------------------------------
// The chain-valued receiver's own overload set: declared in
// shape/monotonechain.hpp, and a polygon rather than a region-with-holes result
// for every bounded convex operand a monotone chain accepts.
 
#define PGL_DEFINE_CHAIN_MINKOWSKI_SUM(CONCEPT, OPERAND)                                       \
    template <class PointType_, class TLabel, class Storage>                                   \
    template <class ResultNumber, CONCEPT OPERAND>                                             \
    Polygon<Point<ResultNumber, typename PointType_::LabelType>>                                \
    MonotoneChain<PointType_, TLabel, Storage>::minkowskiSum(const OPERAND& other) const {     \
        return detail::chainMinkowskiSum<Point<ResultNumber, typename PointType_::LabelType>>(  \
            *this, other);                                                                     \
    }
 
PGL_DEFINE_CHAIN_MINKOWSKI_SUM(ConvexConcept, OtherConvex)
PGL_DEFINE_CHAIN_MINKOWSKI_SUM(TriangleConcept, OtherTriangle)
PGL_DEFINE_CHAIN_MINKOWSKI_SUM(RectangleConcept, OtherRectangle)
 
#undef PGL_DEFINE_CHAIN_MINKOWSKI_SUM
 
// The two operands with no area of their own. The sweep above has nothing to say
// about them: a summand with no area leaves consecutive pieces of the sum merely
// touching rather than overlapping, so the sum can pinch shut and needs regions —
// the same answer, from the same engine, as a Polyline's.
 
#define PGL_DEFINE_CHAIN_REGULARIZED_SUM(CONCEPT, OPERAND)                                     \
    template <class PointType_, class TLabel, class Storage>                                   \
    template <class ResultNumber, CONCEPT OPERAND>                                             \
    PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>                             \
    MonotoneChain<PointType_, TLabel, Storage>::minkowskiSum(const OPERAND& other) const {     \
        return detail::regularizedMinkowskiSum<                                                \
            Point<ResultNumber, typename PointType_::LabelType>>(*this, other);                \
    }
 
PGL_DEFINE_CHAIN_REGULARIZED_SUM(SegmentConcept, OtherSegment)
PGL_DEFINE_CHAIN_REGULARIZED_SUM(OrientedSegmentConcept, OtherOriented)
// A second chain is not convex either, so the sweep has nothing to say about it
// and the region-valued engine answers, as it does for two polylines.
PGL_DEFINE_CHAIN_REGULARIZED_SUM(MonotoneChainConcept, OtherChain)
 
#undef PGL_DEFINE_CHAIN_REGULARIZED_SUM
 
// -----------------------------------------------------------------------------
// The set receiver: one definition over the whole operand family, since the
// construction reads none of the operand's shape — it hands each component pair
// to the engine above and unites what comes back.
 
template <class PointType_, class TLabel>
template <class ResultNumber, detail::SetMinkowskiOperandConcept OtherShape>
PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>
PolygonSet<PointType_, TLabel>::minkowskiSum(const OtherShape& other) const {
    return detail::setMinkowskiSum<Point<ResultNumber, typename PointType_::LabelType>>(*this,
                                                                                        other);
}
 
// The mirror spellings. A set outranks every one of these, so it owns the pair
// and they hand it straight over — the three receivers that carry no rank-based
// forwarder of their own, unlike the convex shapes and the chain.
 
#define PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM(RECEIVER)                                      \
    template <class PointType_, class TLabel>                                              \
    template <class ResultNumber, PolygonSetConcept OtherSet>                              \
    PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>                        \
    RECEIVER<PointType_, TLabel>::minkowskiSum(const OtherSet& other) const {              \
        return other.template minkowskiSum<ResultNumber>(*this);                           \
    }
 
PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM(Polygon)
PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM(PolygonWithHoles)
PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM(Polyline)
 
#undef PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM
 
}  // namespace pgl