dms_split_convex_polygon_keilsnoeyink

Geometric functions dms_split_convex_polygon_keilsnoeyink

dms_split_convex_polygon_keilsnoeyink splits every polygon into strictly convex parts as dms_split_convex_polygon does, but with the minimum number of parts for every polygon without holes, at a higher cost.

syntax

dms_split_convex_polygon_keilsnoeyink(polygon_data_item)

description

Since GeoDMS 20.24.0.

dms_split_convex_polygon_keilsnoeyink(polygon_data_item) gives the same kind of result as dms_split_convex_polygon:

a new uint32 Domain unit with one entry per part;
the subitems geometry and polygon_rel;
the same reading of the argument, under the even-odd rule.

Everything that page says about the parts holds here too: their union is exactly dms_polygon of the element, they do not overlap, every part is strictly convex, no cut adds a vertex, and the order of the parts does not depend on how the input is written.

The difference is the number of parts:

A polygon without holes gets the minimum number of strictly convex parts that cuts between its vertices can give. The operator finds it with the dynamic programme of Keil, in the form that Keil and Snoeyink (2002) bound.
A polygon with holes, or one that touches another polygon of the same element at a vertex, is split as dms_split_convex_polygon splits it (Hertel and Mehlhorn). With holes the minimum is NP-hard to find.
A polygon without holes whose minimum would cost too much is also split as dms_split_convex_polygon splits it. The limit lies at about 0.1 s per polygon, and depends on the number of vertices and of inward corners.

The result is therefore never larger than that of dms_split_convex_polygon, and usually smaller. Measured with GeoDMS 20.24.0 on a machine with 32 logical processors:

data	dms_split_convex_polygon	dms_split_convex_polygon_keilsnoeyink
57,290 BAG building outlines	149,010 parts in 0.05 s	126,522 parts (-15%) in 0.24 s
14,729 CBS buurten 2025	1,834,591 parts in 0.64 s	1,442,923 parts (-21%) in 4.8 s

Both operators compute the polygons of a tile in parallel, so the time depends on the number of processors.

when to use which

Use dms_split_convex_polygon unless fewer parts pay for the extra time downstream. They can pay where the work grows with the number of parts, or with the number of pairs of parts, and the parts are used more than once.

In the one such use measured, they did not: which parts of neighbouring polygons overlap after a [[dms_minkowski_sum]], with dms_polygon_connectivity or dms_convex_polygon_connectivity grouped by polygon. The fewer parts made that step 5 to 31% faster, but the split took 0.04 to 0.18 s longer on 57,290 building outlines and 4.2 s longer on the 14,729 buurten, more than that saved.

For a [[dms_minkowski_sum]] or a buffer of the polygons themselves, use those operators directly; going through the convex parts is slower. The same holds for finding which polygons lie within a distance of each other: grow the polygons themselves and apply dms_polygon_connectivity to them.

applies to

Attribute polygon_data_item with a polygon Value type: spoint, ipoint, wpoint, upoint, fpoint or dpoint

conditions

The composition type of the argument needs to be polygon.

since version

20.24.0

example

unit<uint32> parts := dms_split_convex_polygon_keilsnoeyink(pand/geometry)
{
    attribute<rdc>  geometry;
    attribute<pand> polygon_rel;
}
attribute<uint32> nr_parts (pand) := pcount(parts/polygon_rel);