minkowskierosion.hpp File Reference

Minkowski erosions: the set of translations of one shape that keep it inside another. More...

#include "implementation/minkowskisum.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_EROSION(SHAPE)
#define	PGL_DEFINE_CONVEX_MINKOWSKI_EROSION(SHAPE)
#define	PGL_DEFINE_REGION_MINKOWSKI_EROSION(RECEIVER)

Detailed Description

Minkowski erosions: the set of translations of one shape that keep it inside another.

The erosion of A by B is the set , the operation implementation/minkowski.hpp's sum is the morphological dual of. It is defined for exactly the pairs whose sum is (pgl::MinkowskiSummableConcept, plus the region-valued overload sets of implementation/minkowskisum.hpp), and it is not commutative: A ⊖ B reads its two operands quite differently, so every pair the sum answers by forwarding to the higher-ranked operand is answered here on the receiver itself.

One identity carries the convex receivers

Write a closed half-plane as H = {p : cross(d, p) >= c}. Then

H ⊖ B = {x : cross(d, x) >= c - inf_{b in B} cross(d, b)},

which is H translated by -b*, where b* is the point of B attaining that infimum — the very support point pgl::detail::minkowskiHalfplaneSum translates the other way to make the sum. And because erosion distributes over an intersection of constraints,

A ⊖ B = ⋂ᵢ (Hᵢ ⊖ B)      whenever  A = ⋂ᵢ Hᵢ,

a convex receiver needs nothing but its own half-planes and the operand's support function: one clamp per constraint, O(a·b) in the two operands' sizes, and no arithmetic beyond a cross product and a subtraction. Three consequences are worth stating, because they are what the contract below is made of:

• The operand need not be convex. A support function only sees the convex hull, so A ⊖ B is A ⊖ hull(B) for convex A, and a Polygon, a PolygonWithHoles, a PolygonSet, a Polyline and a MonotoneChain are all as cheap to erode by as their vertex count. That is why the pairs the sum forwards to a region-valued overload come back here as a convex region.
• It is exact on the lattice. Every constraint of the result is a constraint of the receiver translated by one vertex of the operand, so the half-planes are integral whenever both operands are — even though the vertices of the result generally are not, which is exactly what a pgl::HalfplaneIntersection is for. The one operand that brings a division is a HalfplaneIntersection, whose own support point is a crossing of two stored boundary lines; see pgl::detail::minkowskiErosionPoint_t.
• An unbounded operand empties a bounded receiver, and the same clamp says so: the infimum is -∞ in any direction the operand recedes through, that constraint admits no point at all, and the erosion is empty. No shape of a bounded receiver can survive it, which is why this file may hand a non-convex receiver to the convex construction when the operand is unbounded — the hull it would silently take is irrelevant to an answer that is empty either way.

The non-convex receivers need the boolean engine

That identity is all about A being an intersection of half-planes, so it says nothing about a Polygon with a notch, and the erosion of one is genuinely harder than its sum: it can disconnect a connected shape, which is why every region-valued erosion returns a pgl::PolygonSet where the corresponding sum returns one pgl::PolygonWithHoles.

What always works is the complement, taken inside a window big enough to hide that the plane is not one. With W a box containing A and every a + b, and U = closure(W° ∖ A) the material just outside A,

A ⊖ B  =  A ∖ (U ⊕ (-B)),

since for x ∈ A some x + b leaves A exactly when some x + b lands in U, and U is where every such point is. So one difference, one Minkowski sum — pgl::detail::regularizedMinkowskiSum, whole — and one more difference answer it. That A ∖ … at the front is also what makes it read A ⊖ B ⊆ A, which is true only of an operand covering the origin, so the operand is first moved onto one of its own vertices and the answer moved back. See pgl::detail::regularizedMinkowskiErosion.

A convex receiver that merely arrived as a Polygon or a hole-free region skips all of that for the linear clamp above, exactly as the sum's first construction skips the arrangement for the linear merge.

Two contracts, and why they differ

• A convex-receiver erosion is literal: the point set itself, lower dimensional pieces included. HalfplaneIntersection holds a point, a segment, a line, a half-plane, the empty set and the whole plane, so there is nothing to round off and no reason to drop anything.
• A region-valued erosion is regularized, closure((A ⊖ B)°), as its sum and every boolean operation in booleans.hpp is. A PolygonSet holds nothing thinner than a region, and an erosion produces thin material readily — a corridor exactly as wide as the operand erodes to a curve.

Eroding by nothing

A ⊖ ∅ is the whole plane: every x satisfies x ⊕ ∅ ⊆ A vacuously. That is the one answer a shrinking operation gives that is bigger than its receiver, and what happens to it turns on when the operand is known to be empty. An EmptyShape operand is empty by its type, so the dispatcher answers before any result type is chosen and every receiver gets the plane as a HalfplaneIntersection. An operand that merely turns out to cover no point — an empty Convex, Rectangle, Polygon, PolygonSet or HalfplaneIntersection — arrives at whatever result type its pair fixed, and the three tighter ones cannot hold the plane: Rectangle ⊖ Rectangle, Halfplane ⊖ bounded and every region-valued pair throw std::logic_error rather than answer something else, where a HalfplaneIntersection result simply returns it.

There is deliberately no operator for the erosion. operator+ spells the sum because A ⊕ {p} is the translation A + p it already spelled, but A - B is read at least as often as A ⊕ (-B), which is a different set; the operator- this library has stays what it was, a translation by a point.

Macro Definition Documentation

PGL_DEFINE_CONVEX_MINKOWSKI_EROSION

#define PGL_DEFINE_CONVEX_MINKOWSKI_EROSION

(

SHAPE

)

Value:

template <class PointType_, class TLabel>                                                  \
template <class OtherShape>                                                                \
    requires (!MinkowskiSummableConcept<SHAPE<PointType_, TLabel>, OtherShape> &&          \
              BoundedPolygonalConcept<OtherShape>)                                         \
constexpr auto SHAPE<PointType_, TLabel>::minkowskiErosion(const OtherShape& other)        \
    const {                                                                                \
    return detail::minkowskiConvexErosion(*this, other);                                   \
}

PGL_DEFINE_MINKOWSKI_EROSION

#define PGL_DEFINE_MINKOWSKI_EROSION

(

SHAPE

)

Value:

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

PGL_DEFINE_REGION_MINKOWSKI_EROSION

#define PGL_DEFINE_REGION_MINKOWSKI_EROSION

(

RECEIVER

)

Value:

template <class PointType_, class TLabel>                                                  \
template <class ResultNumber, class OtherShape>                                            \
    requires (!MinkowskiSummableConcept<RECEIVER<PointType_, TLabel>, OtherShape> &&        \
              BoundedPolygonalConcept<OtherShape>)                                         \
PolygonSet<Point<ResultNumber, typename PointType_::LabelType>>                            \
RECEIVER<PointType_, TLabel>::minkowskiErosion(const OtherShape& other) const {            \
    return detail::regularizedMinkowskiErosion<                                            \
        Point<ResultNumber, typename PointType_::LabelType>>(*this, other);                \
}