minkowski.hpp File Reference

Minkowski sums of two shapes, and the operator+ that spells them. More...

#include "implementation/transformations.hpp"
#include <algorithm>
#include <cstddef>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Macros
#define	PGL_DEFINE_MINKOWSKI_SUM(SHAPE)

Functions
template<class A, class B> requires MinkowskiSummableConcept<A, B>
constexpr auto	pgl::operator+ (const A &a, const B &b)
	Returns the Minkowski sum a ⊕ b, the same as a.minkowskiSum(b).

Detailed Description

Minkowski sums of two shapes, and the operator+ that spells them.

The Minkowski sum of two shapes is the set . It is a construction, so it lives here rather than in a shape header, and it is defined only for the pairs whose sum is representable by a Pangolin shape (pgl::MinkowskiSummableConcept):

• The empty shape absorbs: ∅ ⊕ B is empty.
• Summing with a Point is a translation, so it is closed for every shape kind and returns the other operand's type. This is also what shape + point has always meant, which is why the translating operator+ overloads live in this file too.
• Two bounded convex shapes (Point, Segment, OrientedSegment, Rectangle, Triangle, Convex) sum to a Convex with at most m + n vertices, computed in O(m + n) by merging the two edge-direction sequences. Two Rectangles are the one non-trivial pair closed under the sum, and return a Rectangle.
• A Halfplane and anything bounded and polygonal sum to that same half-plane, translated to the operand's support point: a half-plane absorbs whatever is bounded, whether or not it is convex.
• Two convex polyhedra, at least one of them unbounded (Halfplane, Line, OrientedLine, Ray, HalfplaneIntersection, and on the other side those or any bounded convex shape) sum to a convex polyhedron, returned as a HalfplaneIntersection. See pgl::detail::minkowskiPolyhedralSum.

Every vertex of the result is a sum of two input vertices, so the whole construction is exact in the operands' coordinate type: integers in, integers out. The one operand that is not on the lattice to begin with is a HalfplaneIntersection, whose vertices are line crossings; a sum with one is exact over pgl::division_result_t coordinates instead, the same type that shape's own accessors report a vertex in.

pgl::detail::minkowskiSumOf is the single dispatcher, and pgl::MinkowskiSummableConcept the single gate: widening the set of pairs whose sum is one shape means relaxing that concept and adding one branch to the dispatcher. Nothing else here, and no shape header, encodes which pairs are allowed.

The non-convex sums are not here, and are not a widening of that concept: a sum that can enclose a hole needs a PolygonWithHoles region result, so it needs a triangulation and the boolean engine and lives in implementation/minkowskisum.hpp, as an overload set on pgl::Polygon, pgl::PolygonWithHoles and pgl::Polyline over exactly the pairs this file turns away.

Macro Definition Documentation

PGL_DEFINE_MINKOWSKI_SUM

#define PGL_DEFINE_MINKOWSKI_SUM

(

SHAPE

)

Value:

template <class PointType, class LabelType>                                          \
template <class OtherShape>                                                          \
    requires MinkowskiSummableConcept<SHAPE<PointType, LabelType>, OtherShape>       \
constexpr auto SHAPE<PointType, LabelType>::minkowskiSum(const OtherShape& other) const { \
    return detail::minkowskiSumOf(*this, other);                                     \
}