dms_split_convex_polygon

Geometric functions dms_split_convex_polygon

dms_split_convex_polygon splits every polygon, holes included, into strictly convex parts without holes, each a separate entry of a new domain, the way dms_split_polygon splits it into its single polygons.

syntax

  • dms_split_convex_polygon(polygon_data_item)

description

Since GeoDMS 20.24.0.

dms_split_convex_polygon(polygon_data_item) results in a new uint32 Domain unit with one entry per convex part. Each element is first read under the even-odd rule of the dms polygon operators family, so the argument does not have to be a valid polygon: a bow tie gives its two triangles, a hole that touches the shell, or an outline wound the wrong way, are read as dms_polygon reads them.

The result carries the two subitems of dms_split_polygon, so it fits the same configurations:

  • geometry: one convex part, a single ring without holes
  • polygon_rel: a relation towards the domain of polygon_data_item, the element the part came from

What the parts are:

  • Together they are the element. Their union is exactly dms_polygon of the element, on the same grid, and their areas add up to its area. Two parts of one element meet only along a cut, never overlap.
  • Every part is strictly convex: every corner turns the same way and none is straight. A vertex of the input between two collinear edges is not a corner of any part.
  • A convex element stays one part, a rectangle for instance, without any further work. An L-shape gives two parts, a square with a square hole at least four.
  • The number of parts is small, not minimal. With holes the minimum is NP-hard to find, so the operator does not promise it: it splits each polygon into triangles and then removes every cut whose two sides together are still convex (Hertel and Mehlhorn), which gives at most four times the minimum and usually close to it.
  • The result does not depend on how the input is written. Every part runs clockwise from its lexicographically first vertex, and the parts of one element are in the order of those vertices, whatever ring order, starting point or orientation the input had.

The vertices of the parts are those of the cleaned element: for integer coordinates the input’s own vertices, for float coordinates the vertices on the grid of the family, see dms polygon operators. No cut ever adds a vertex.

An element that encloses no area has no parts.

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.

why convex parts

Some operations are much cheaper on convex polygons than on general ones. Whether two convex polygons overlap, for instance, is decided by looking for one separating line, and the minkowski_sum of a convex part with a convex kernel is a merge of their edges. A model that only needs to know which buffered buildings overlap can test their convex parts pairwise instead of forming each union.

since version

20.24.0

example 

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

see also