minkowski_difference

Geometric functions minkowski_difference

syntax

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

and the same two forms for bg_minkowski_difference, cgal_minkowski_difference, geos_minkowski_difference and dms_minkowski_difference. 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.

definition

The Minkowski difference, or erosion, of a geometry A by a kernel K is the set of positions at which K fits entirely inside A. It shrinks A by the shape of the kernel.

The library operators compute it as

A (-) K  =  A \ ( (R \ A) (+) -K )

with R a box containing A with room to spare and -K the kernel reflected through the origin: eroding A is dilating everything outside it, with their own minkowski_sum. dms_minkowski_difference computes the same set without the box: per element one sweep that keeps what A covers and no piece of the dilated outside covers, the pieces being those along the edges and at the corners of A that minkowski_sum describes. Like dms_minkowski_sum it takes convex kernels only.

description

Everything in minkowski_sum about the two argument forms, the six variant names, the kernel restrictions and the libraries applies here as well, with one difference: this operator erodes, so it accepts the d-prefixed variant spellings ('d4HV', 'd8D', …) and refuses an i prefix with an error that names minkowski_sum.

Erosion is not the inverse of dilation. Dilating and then eroding by the same kernel is the morphological closing: it fills notches narrower than the kernel and can only add, never remove, so the result always contains the original. Eroding and then dilating is the opening: it removes protrusions thinner than the kernel, and the result always lies within the original. Neither returns to where it started, which is exactly what makes them useful for cleaning up geometry.

Erosion can empty a feature: anything thinner than the kernel disappears, and a feature that vanishes entirely leaves an empty sequence rather than a null.

The bp_ operators with a kernel shape in their name, bp_polygon_d4HV to bp_split_union_polygon_dXD, are deprecated; Boost polygon functions gives what to write instead.

applies to

As minkowski_sum.

conditions

As minkowski_sum. In addition, the library operators erode within a bounding box that is grown past the reach of the kernel, so a geometry whose coordinates already sit near the bp_ integer limit (2^25) has less room here than under minkowski_sum.

dms_minkowski_difference refuses the variants 'XHV' and 'XD' (also as 'dXHV' and 'dXD') and a kernel polygon that is not convex, as dms_minkowski_sum does; condition 7 of minkowski_sum says what to use instead.

since version

20.18.0; dms_minkowski_difference since 20.20.0

examples

// shrink every parcel by 5 units, with a square kernel
attribute<ipoint> parcel_core (polygon, parcel) := bp_minkowski_difference(parcel/border, 5.0, '4HV');

// morphological opening: drop slivers thinner than 5 units, keep the rest in place
attribute<ipoint> opened (polygon, parcel) :=
    bp_minkowski_sum(bp_minkowski_difference(parcel/border, 5.0, 'd4HV'), 5.0, 'i4HV');

// morphological closing: fill gaps narrower than 5 units
attribute<ipoint> closed (polygon, parcel) :=
    bp_minkowski_difference(bp_minkowski_sum(parcel/border, 5.0, 'i4HV'), 5.0, 'd4HV');

see also