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, geos_minkowski_sum and dms_minkowski_sum. The dms_ form runs on the sweep that GeoDMS implements itself and accepts a geometry argument that is not a valid polygon; see dms polygon operators.

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 shape of the kernel.

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 Domain unit of the kernel is either void, one kernel for the whole attribute and the usual case, or the domain of the geometry, for a kernel per element.

The variant form, xx_minkowski_sum(geometry, size, variant), builds one of 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 i-prefixed spellings ('i4HV', 'i8D', …) are accepted too, so a configuration that replaces bp_polygon_i4HV can keep its literal. A d prefix is refused here with an error that names minkowski_difference, because honouring it would compute the opposite of what the operator name promises.

The five libraries compute the same set by different means, so their 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
geos_minkowski_sum GEOS dpoint only union of convex cells, one cascaded union
dms_minkowski_sum GeoDMS itself all point types per element one sweep over a piece per edge and per corner; convex kernels only

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.

dms_minkowski_sum assembles the sum from the element itself: one piece per edge, the edge shifted outward by the kernel point furthest in that direction, and one piece per convex corner, the arc of the kernel between the two edge directions, united in a single sweep per element. A convex element, such as a rectangular building, needs no sweep at all, and the elements of a tile are computed in parallel. On building outlines it is about as fast as geos_buffer_multi_polygon.

The bp_ operators with a kernel shape in their name, such as bp_polygon_i4HV and bp_split_union_polygon_dXD, are deprecated: they work, and log a warning that names the replacement. The migration table is on Boost polygon functions.

applies to

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

conditions

  1. The kernel must be a single ring, without holes or islands. This is the restriction that the convolution of boost polygon documents, and keeping all libraries to it is what lets them agree. A kernel with more than one ring is a configuration error.
  2. The ring must be simple, without self-intersections, 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 variant per element is refused rather than quietly resolved to the value of the first element. 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, which is reported as an error rather than returned as an empty result.
  6. A Minkowski sum multiplies vertices: a geometry with n vertices and a kernel with m produce in 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. dms_minkowski_sum does not build those cells; its cost per element grows with n + m.
  7. dms_minkowski_sum accepts convex kernels only: the variants '4HV', '4D', '8D' and '16D', or a kernel polygon that is convex, in either orientation and with or without the origin inside it. The star-shaped 'XHV' and 'XD' and a kernel polygon that is not convex are refused with an error that names the other libraries. For such a kernel use the bg_, geos_, cgal_ or bp_ form, or split the kernel into convex parts and unite the sums, since the sum with a union of kernels is the union of the sums.

since version

20.18.0; dms_minkowski_sum since 20.20.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