minkowskisum.hpp File Reference

Minkowski sums whose result is not a single convex shape: one region when the substantive case is connected and regular, several only when thin or slit geometry can genuinely separate it, and one polygon for the receiver whose monotonicity rules holes out. More...

#include "implementation/booleans.hpp"
#include <algorithm>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Macros
#define	PGL_DEFINE_REGION_MINKOWSKI_SUM(RECEIVER, CONCEPT, OPERAND)
#define	PGL_DEFINE_REGION_SET_MINKOWSKI_SUM(RECEIVER, CONCEPT, OPERAND)
#define	PGL_DEFINE_CHAIN_MINKOWSKI_SUM(CONCEPT, OPERAND)
#define	PGL_DEFINE_CHAIN_REGULARIZED_SUM(CONCEPT, OPERAND)
#define	PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM(RECEIVER)

Detailed Description

Minkowski sums whose result is not a single convex shape: one region when the substantive case is connected and regular, several only when thin or slit geometry can genuinely separate it, and one polygon for the receiver whose monotonicity rules holes out.

implementation/minkowski.hpp sums the pairs whose result is a single shape: a translation, a rectangle, or — for two bounded convex operands — a Convex, merged from the two edge-direction sequences in linear time. What it cannot do is the case the sum was invented for, a non-convex operand: doc/raw/shape_methods.md said outright that such a sum "can be a region with holes … none of those is representable today". It is now, so this header adds it.

The construction that always works is the one identity the sum satisfies over unions,

A ⊕ B  =  ⋃ᵢⱼ (Aᵢ ⊕ Bⱼ)      whenever  A = ⋃ᵢ Aᵢ  and  B = ⋃ⱼ Bⱼ,

used with a convex decomposition of each operand: the triangles of its triangulated domain, plus the pieces of it that have no area beside them (a degenerate operand is its own boundary, and a region carries slits). Each Aᵢ ⊕ Bⱼ is then the linear convex merge, and the union of the |A|·|B| results is one call to pgl::regularizedUnionOf — the cell engine of booleans.hpp, which increment 11 observed was already n-ary in everything but its signature. That is pgl::detail::decomposedMinkowskiSum, and it costs Θ(a²b²).

It is also the last thing pgl::detail::regularizedMinkowskiSum tries, because it charges for both operands' concavity whether or not either has any. Three cheaper constructions come first. The first two turn on a convex operand rather than on a type:

• Both operands convex — a Polygon or a hole-free region can be, and then the answer is just the linear merge of minkowski.hpp, in O(a + b).
• One operand convex — the other's boundary is decomposed into x-monotone runs instead of its area being triangulated, on the identity A ⊕ B = (A + q₀) ∪ (∂A ⊕ B); each run's sum is the chain sweep below, which needs no arrangement at all. See pgl::detail::minkowskiBoundaryPieces.
• Neither convex, both with area — only one of them is decomposed, and the whole of the other is summed against each of its pieces by the two constructions above. That leaves the arrangement a regions to unite where the all-pairs decomposition left it a·b convex pieces, and the pieces it does leave scatter instead of piling up. See pgl::detail::minkowskiOneSidedPieces, and pgl::detail::minkowskiOneSidedDecomposesLeft for which operand pays.

None changes the worst case — a boundary that turns at every vertex has one monotone run per edge, and the one-sided decomposition still ends in an arrangement of Θ(a·b) edges — and none is a special case in the contract: all four return the same answer, and the paragraphs below describe all of them.

Two consequences worth stating, because they are what tells this entry point apart from the convex-shape-valued one:

• **The result is a pgl::PolygonWithHoles wherever one operand is a body**, and a pgl::PolygonSet only where neither is. A body is a shape that is the closure of a connected, non-empty interior — a nondegenerate Rectangle, Triangle, Convex or Polygon, and a PolygonWithHoles whose slits leave its interior connected. One of those on either side makes the regularized sum a single component, whatever the other operand is; see pgl::detail::singleRegionMinkowskiSum for the argument. What is left over is two thin operands — a chain and a segment, say — where a direction the two share sweeps out nothing and the answer really can scatter, for operands that are in no way degenerate. Those keep the set.

  The body is a precondition where the type asks for one. A degenerate operand can split a sum this file promises in one region, and then one component of it is what comes back — the sums that take a body are not contracted for anything else, exactly as pgl::MonotoneChain::minkowskiSum is not. pgl::detail::regularizedMinkowskiSum stays total underneath and is what a caller with no nondegenerate operand to offer wants.

• The result is regularized, closure((A ⊕ B)°). That costs nothing when both operands have area — a simple polygon is the closure of its own interior, and so is a sum with one — and drops the lower-dimensional parts otherwise, exactly as the boolean operations do.

A pgl::Polyline receiver is the same construction, and it is here for the same reason: a chain has no area, but dragging another shape along one sweeps out material that closes over a hole as readily as a C does — a closed chain is the plainest example there is. It takes every bounded operand with area to sweep (Triangle, Rectangle, Convex, Polygon, PolygonWithHoles) plus Segment and OrientedSegment, which have none and sweep one out all the same: an edge of the chain and the segment span a parallelogram unless the two are parallel. Being its own boundary, the chain's own decomposition is its edges.

A Segment is the thinnest operand all three receivers take, and the cheapest: it is one convex piece, so it costs one convex merge per piece of the receiver and the arrangement it feeds is a single translated copy of that decomposition.

Exactness follows the same rule as booleans.hpp: every vertex of every convex piece sum is a sum of two input vertices, so the pieces are exact in the operands' promoted coordinate type; only the union of them can put a vertex at a crossing, and that arrangement is built over rationals and converted to the requested type once, at the end.

The boundary decomposition is the one construction here that does not fit that rule, since a run's sum can put a vertex at a crossing of two of its own pieces. Its pieces are therefore built over the exact type directly, and it is taken only when that type is a rational: on floating-point coordinates it would be rounding twice where the convex decomposition rounds once, which was measured to matter.

The chain that needs none of it

A pgl::MonotoneChain receiver is the exception this file also holds, and it is worth reading as the counterpoint to everything above. A chain sorted along x cannot bend back on itself, and its sum with a convex operand therefore meets every vertical line in a single interval — see pgl::detail::chainSumWalk for why. Such a set is the region between two x-monotone chains: one polygon, never holed, never in pieces, with nothing to regularize.

So that pair skips the whole engine above. No arrangement is built and nothing is triangulated: one convex merge per chain edge, then a sweep merging the pieces' boundaries into the sum's two, which the chain hands over already sorted along x. The sweep carries an envelope as a sequence of the pieces' own integer segments and leaves the points where one takes over from the next implicit, so it never divides — the answer is exact in integers whenever it lands on the lattice, and a crossing is converted from an exact fraction only where the boundary actually has one.

What stays here for a chain is the pairs the theorem does not cover: a Polygon, a pgl::PolygonWithHoles — whose own concavity strands cavities however monotone the chain is — and a Segment or pgl::OrientedSegment, which have no area, so that consecutive pieces of the sum can meet at a point rather than overlap and the answer can pinch shut where no polygon may.

Macro Definition Documentation

PGL_DEFINE_CHAIN_MINKOWSKI_SUM

#define PGL_DEFINE_CHAIN_MINKOWSKI_SUM	(		CONCEPT,
			OPERAND )

Value:

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_REGULARIZED_SUM

#define PGL_DEFINE_CHAIN_REGULARIZED_SUM	(		CONCEPT,
			OPERAND )

Value:

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_REGION_MINKOWSKI_SUM

#define PGL_DEFINE_REGION_MINKOWSKI_SUM	(		RECEIVER,
			CONCEPT,
			OPERAND )

Value:

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);            \
}

PGL_DEFINE_REGION_SET_MINKOWSKI_SUM

#define PGL_DEFINE_REGION_SET_MINKOWSKI_SUM	(		RECEIVER,
			CONCEPT,
			OPERAND )

Value:

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_SET_MIRROR_MINKOWSKI_SUM

#define PGL_DEFINE_SET_MIRROR_MINKOWSKI_SUM

(

RECEIVER

)

Value:

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);                           \
}