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
- 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.
- The ring must be simple, without self-intersections, and enclose an area.
- 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.
- The order of points follows the usual rule: clockwise for exterior bounds (see Point order in polygons).
- For
bp_minkowski_sumthe 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. - 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_sumdoes not build those cells; its cost per element grows with n + m. dms_minkowski_sumaccepts 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 thebg_,geos_,cgal_orbp_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
- minkowski_difference, the eroding counterpart
- Boost polygon functions, the deprecated operators with a kernel shape in their name and what to write instead
- geos_buffer, Bg_buffer_multi_polygon and dms_buffer_multi_polygon, a round buffer: use these when you want a circle, and minkowski_sum when you want a specific or anisotropic kernel
- polygon operators, the operators of all libraries side by side
- Point order in polygons