minkowski_sum

Geometric functions minkowski_sum

syntax

  • bp_minkowski_sum(polygon_data_item, kernel)
  • bp_minkowski_sum(polygon_data_item, size, variant)

and the same two forms for bg_minkowski_sum, cgal_minkowski_sum and geos_minkowski_sum.

See minkowski_difference for the eroding counterpart.

definition

The Minkowski sum of a geometry A and a kernel K is the set of all sums of a point of A and a point of K: sweeping K over A and keeping everything it covers. For a kernel centred on the origin that grows A outward by the kernel’s shape, which is what the older polygon inflated operators did with twelve fixed kernels.

Since GeoDMS 20.18.0. Before, the kernel was part of the operator name (bp_polygon_i4HV, bp_split_union_polygon_dXD, and 46 more), so only those twelve shapes were reachable and only through the boost.polygon backend. The kernel is now an argument, and all four geometry backends have the operator. The name-suffixed operators still work but are depreciated — see the migration table on Boost polygon functions.

description

The kernel form, xx_minkowski_sum(geometry, kernel), takes the kernel as a polygon Data item. This is the general Minkowski sum: the kernel is not assumed to contain the origin, so a kernel that sits off-centre displaces the result by that much. To grow a shape symmetrically, centre the kernel on (0, 0).

The kernel’s Domain unit is either Void — one kernel for the whole attribute, the usual case — or the same domain as the geometry, for a kernel per element.

The variant form, xx_minkowski_sum(geometry, size, variant), builds one of the six classic kernels at the given size, centred on the origin. variant is a Parameter of value type string, read once before any tile is calculated:

variant kernel
'4HV' axis-aligned square, 4 points
'4D' diamond, 4 points
'8D' octagon, 8 points
'16D' 16-gon
'XHV' 8-point star with spikes along the axes
'XD' 8-point star with spikes along the diagonals

The names are case-insensitive. The old i-prefixed spellings ('i4HV', 'i8D', …) are accepted too, so a configuration migrating away from bp_polygon_i4HV can keep its literal. A d prefix is rejected here and names minkowski_difference instead, because honouring it would compute the opposite of what the operator name promises.

The four backends compute the same set by different means, so results agree in shape but not bit-for-bit:

operator library coordinates method
bp_minkowski_sum boost polygon spoint, ipoint its own convolution, under the winding rule
cgal_minkowski_sum CGAL all point types CGAL::minkowski_sum_2, exact reduced convolution
bg_minkowski_sum boost geometry all point types union of convex cells (see below)
geos_minkowski_sum GEOS dpoint only union of convex cells, one cascaded union

boost.geometry and GEOS have no Minkowski primitive, so for those the kernel is split into convex parts and the sum is assembled as the union of the geometry shifted to each part, together with the cell each part sweeps along each boundary edge. Every cell is convex, which is what makes an ordinary union exact here.

applies to

  • Attribute polygon_data_item with composition type polygon and a Value type the chosen backend supports (see the table above).
  • kernel with composition polygon and the same value type, on a Void domain or the geometry’s own.
  • Parameter size with float64 value type, or an attribute on the geometry’s domain.
  • parameter variant with string value type.

conditions

  1. The kernel must be a single ring — no holes, no islands. This is the same restriction boost.polygon’s own convolution documents, and keeping all four backends to it is what lets them agree. A kernel with more than one ring is a configuration error.
  2. The ring must be simple (non-self-intersecting) and enclose an area.
  3. variant must be a Parameter. It selects one of six fixed rings and is read once, before any tile is calculated, so a per-element variant is rejected rather than quietly resolved to the first element’s value. size and kernel may vary per element; variant may not.
  4. The order of points follows the usual rule: clockwise for exterior bounds (see Point order in polygons).
  5. For bp_minkowski_sum the integer-coordinate limits of boost polygon apply: coordinates must stay below 2^25 after translation, and a kernel smaller than one coordinate unit rounds away to nothing. The error says so rather than returning an empty result silently.
  6. A Minkowski sum multiplies vertices: a geometry with n vertices and a kernel with m produces on the order of n·m cells before they collapse. On large dissolved geometry this is slow, in the same way bg_overlay_polygon is; prefer a coarse kernel ('4HV', '4D') where the rounding does not matter.

since version

20.18.0

examples 

// grow every building by 75 units, with 8-point rounding on the corners
attribute<ipoint> bld_grown (polygon, bld) := bp_minkowski_sum(bld/border, 75.0, '8D');

// the same through GEOS, on float64 coordinates
attribute<dpoint> bld_grown_geos (polygon, bld) := geos_minkowski_sum(bld/geometry, 75.0, '8D');

A kernel of your own. A single kernel has to be a Void-domain polygon parameter, and dissolving a one-row polygon attribute is how you get one:

unit<uint32> KS  : nrofrows = 1;
unit<uint32> KPt : nrofrows = 4;
attribute<int32>  kx   (KPt) : [ 30, 30, -30, -30 ];   // a 60 x 20 rectangle: anisotropic,
attribute<int32>  ky   (KPt) : [ 10, -10, -10,  10 ];  // wider than it is tall
attribute<KS>     kseq (KPt) : [  0,  0,   0,   0 ];
attribute<uint32> kord (KPt) : [  0,  1,   2,   3 ];

attribute<ipoint> kernel_row (KS, polygon) := points2polygon(point_xy(kx, ky, ipoint), kseq, kord);
parameter<ipoint> kernel     (polygon)     := bp_union_polygon(kernel_row);

attribute<ipoint> smeared (polygon, bld) := bp_minkowski_sum(bld/border, kernel);

That is the case the variant form cannot express: a kernel that is not one of the six shapes.

see also