Skip to content

polygon operators

Jump to bottom
MaartenHilferink edited this page Oct 13, 2026 · 29 revisions

Back to Geometric functions

  • area - calculates the surface area of each polygon
  • centroid - center of mass of each polygon
  • mid - a point in the polygon, cheaper than centroid
  • outer_single_polygon - outer ring of a single polygon (drops holes)
  • outer_multi_polygon - outer ring(s) of each multi_polygon (drops the holes)
  • geos_buffer - buffer of a (multi)polygon, geos implementation
  • canyon - street-canyon heights for road points from surrounding heights
  • centroid_or_mid - the centroid if located within the polygon, otherwise a mid-point
  • poly2grid - a grid representation of polygons
  • poly2grid_untiled - a grid representation of polygons (untiled variant)
  • poly2allgrids - a cross-table representation of polygons and raster cells
  • poly2allgrids_uint64 - a uint64 cross-table representation of polygons and raster cells
  • lower_bound - the lowest X and Y values of the points in each polygon
  • upper_bound - the highest X and Y values of the points in each polygon
  • center_bound - the center X and Y values of the points in each polygon
  • points2polygon - create polygons from sequences of points
  • sub (difference) - element-wise cutout of one polygon from another, where both domains match or one is void
  • mul (polygon intersection) - element-wise overlap of two polygon arrays, where both domains match or one is void
  • add (union) - element-wise union of two polygon arrays, where both domains match or one is void
  • box_connectivity - find connected polygons based on bounding box overlap (faster, but less precise than polygon_connectivity)
  • polygon_connectivity - find all pairs of polygons in one set that overlap or touch, as relations F1 and F2 (integer coordinates)

Finding pairs of polygons:

Two families of operators find the pairs of polygons that meet, one pair per row of a new domain unit with a relation towards each polygon of the pair. The xxx_overlay_polygon operators compute the intersection geometry of every pair as well; the xxx_polygon_connectivity operators return the relations only. Both take one polygon set, for the pairs within it (each pair once, first_rel < second_rel), or two sets, for the pairs between them. The libraries differ in which pairs they find: the bp_, bg_ and cgal_ variants pair polygons with a common interior point, the geos_ variants also pair polygons that only touch, along an edge or at a point, with an empty geometry for such a pair. The unprefixed polygon_connectivity pairs touching polygons too and names its relations F1 and F2, as does box_connectivity, which only compares bounding boxes. For the intersection of two polygons that are already paired element by element, use mul (polygon intersection) or one of the xxx_intersect operators below.

operator pairs a pair when result items
bp_overlay_polygon, bg_overlay_polygon, cgal_overlay_polygon within one set, or between two sets the polygons have a common interior point geometry, first_rel, second_rel
geos_overlay_polygon within one set, or between two sets the polygons overlap or touch; a touching pair has an empty geometry geometry, first_rel, second_rel
bp_polygon_connectivity, bg_polygon_connectivity, cgal_polygon_connectivity within one set, or between two sets the polygons have a common interior point first_rel, second_rel
geos_polygon_connectivity within one set, or between two sets the polygons overlap or touch first_rel, second_rel
dms_overlay_polygon within one set, or between two sets the polygons have a common interior point; the operands need not be valid geometry, first_rel, second_rel
dms_polygon_connectivity within one set, or between two sets the polygons have a common interior point; the operands need not be valid first_rel, second_rel
polygon_connectivity within one set, integer coordinates the polygons overlap or touch F1, F2
box_connectivity within one set the bounding boxes overlap or touch F1, F2

Since GeoDMS 20.23.1 first_rel and second_rel of the xxx_overlay_polygon and xxx_polygon_connectivity operators are values of the domain unit of their argument. Before, an argument on a domain unit of another value type than uint32, such as a unit<uint8> of provinces, stopped these operators with the internal error Check Failed Error: dynamic_cast(basePtr) == basePtr, and on a uint32 domain unit that does not start at 0 the relation held the row number instead of the value.

Which argument first. The xxx_overlay_polygon and xxx_polygon_connectivity operators divide their work by the polygons of the first argument:

  • Each polygon of the first argument is compared on one thread with all the polygons of the second argument that its bounding box meets.
  • The polygons of the first argument are spread over the threads, and the tiles of the second argument are handled one after another.
  • Since GeoDMS 20.22.1 the polygons within one tile of the first argument are spread over the threads too; before, a tile ran on one thread.
  • Since GeoDMS 20.24.0 that also holds for a tile of only a few polygons.
  • A single polygon is never divided.

So put the argument with the most, and the smallest, polygons first. With a few very large polygons as the first argument, those few comparisons do nearly all the work, each on one thread.

  • On the 342 CBS gemeenten against the 14,729 CBS buurten, dms_polygon_connectivity took 16 to 17 s with the gemeenten first and 6 s with the buurten first (GeoDMS 20.24.0, 32 logical processors).
  • In a country-wide overlay on GeoDMS 20.12.0, a dissolved rural area of a few hundred very large polygons as the first argument did not finish in 10 hours. With the separate source polygons first, dissolved afterwards, it took 5.5 minutes.

Swapping the arguments gives the same pairs, with first_rel and second_rel swapped. To spread one very large polygon over the threads, split it first, for instance with dms_split_convex_polygon, and take the parts together again through its polygon_rel.

Ring order (winding) operators:

  • reverse_polygon - reverse the winding order of every ring, without changing the sequence layout
  • fix_winding_order - give every ring the clockwise-outer / counter-clockwise-hole order, deriving the ring roles from their nesting; repairs half-flipped multi-polygons that a reversal cannot
  • has_correct_winding - True for each element whose ring order is certifiably correct; the replacement for the area(g) < 0 test, which misses a half-flipped feature
  • fix_polygon - fix_winding_order plus repair of self-intersections and other invalidity (GEOS MakeValid)

Operators based on the geos library (recommended: faster, reliable, supports float64/dpoint coordinates):

  • geos_buffer_multi_polygon - creates a buffer polygon for each multi polygon
  • geos_difference - element-wise difference of two polygon arrays (A minus B); also invoked by the - operator for fpoint/dpoint coordinates
  • geos_intersect - element-wise intersection of two polygon arrays; also invoked by the * and & operators for fpoint/dpoint coordinates
  • geos_minkowski_sum - grow each geometry by a kernel: the kernel as a polygon argument, or one of six named shapes at a given size
  • geos_minkowski_difference - shrink each geometry by a kernel; the eroding counterpart
  • geos_overlay_polygon - spatial overlay between two polygon datasets, producing all intersecting pairs with their intersection geometry
  • geos_polygon - clean and validate polygon geometry using GEOS
  • geos_polygon_connectivity - find all pairs of adjacent or overlapping polygons
  • geos_simplify_multi_polygon - simplify the geometry of a multi polygon
  • geos_split_polygon - split multi-polygons into individual single-polygon parts, each as a separate domain entry
  • geos_split_union_polygon - dissolve polygons (optionally grouped by attribute), then split into individual parts
  • geos_union - element-wise union of two polygon arrays; also invoked by the + and | operators for fpoint/dpoint coordinates
  • geos_union_polygon - dissolve all polygons into one, optionally grouped by a partition attribute
  • geos_xor - element-wise symmetric difference of two polygon arrays; also invoked by the ^ operator for fpoint/dpoint coordinates

To be potentially developed operators:

Operators based on the boost polygon library (usually slower than the bg_-variants, and can only process integer coordinates):

  • bp_buffer_multi_polygon - removed in 20.13.0: never implemented; use bg_buffer_multi_polygon or geos_buffer_multi_polygon
  • bp_difference - element-wise difference of two polygon arrays (integer coordinates)
  • bp_intersect - element-wise intersection of two polygon arrays (integer coordinates)
  • bp_overlay_polygon (the former overlay_polygon, a name that was removed in 18.0.0) - spatial overlay between two polygon datasets, or within one, producing all intersecting pairs with their intersection geometry (integer coordinates)
  • bp_polygon - clean and validate polygon geometry using Boost Polygon (integer coordinates)
  • bp_polygon_connectivity - find all pairs of overlapping polygons, between two datasets or within one, as relations only (integer coordinates); not a renaming of polygon_connectivity, which pairs touching polygons too and names its relations F1 and F2
  • bp_split_polygon (or old syntax split_polygon) - split multi-polygons into individual single-polygon parts (integer coordinates)
  • bp_split_union_polygon (or old syntax split_partitioned_union_polygon) - dissolve polygons (optionally grouped by attribute), then split into individual parts (integer coordinates). Combination of split_polygon and partitioned_union_polygon
  • bp_union - element-wise union of two polygon arrays (integer coordinates)
  • bp_union_polygon (or old syntax union_polygon (dissolve) or partitioned_union_polygon (dissolve by attribute)) - dissolve all polygons into one, optionally grouped by a partition attribute (integer coordinates)
  • bp_polygon_filtered, bp_union_polygon_filtered, bp_split_polygon_filtered, bp_split_union_polygon_filtered - bp-set operations that drop rings smaller than the given area
  • bp_polygon_inflated, bp_union_polygon_inflated, bp_split_polygon_inflated, bp_split_union_polygon_inflated - bp-set operations after growing the polygons with the given distance
  • bp_polygon_deflated, bp_union_polygon_deflated, bp_split_polygon_deflated, bp_split_union_polygon_deflated - bp-set operations after shrinking the polygons with the given distance
  • bp_minkowski_sum - grow each geometry by a kernel: the kernel as a polygon argument, or one of six named shapes at a given size
  • bp_minkowski_difference - shrink each geometry by a kernel; the eroding counterpart
  • bp kernel-suffix variants - DEPRECATED since 20.18.0: the 48 names bp_polygon_i4HV … bp_split_union_polygon_dXD (12 kernels x {plain, union, split, split_union}) that carried the kernel shape in the operator name. They still work but warn, naming the replacement. The kernel is an argument now: use bp_minkowski_sum / bp_minkowski_difference on the result of the same operator without the suffix. See the migration table on Boost polygon functions.
  • bp_xor - element-wise symmetric difference of two polygon arrays (integer coordinates)
  • polygon inflated - increases each polygon by expanding its boundary outward
  • polygon deflated - decreases each polygon by contracting its boundary inward

Several boost polygon functions can be combined in a single operator; for the full list of those combinations, see here.

Operators based on the boost geometry library (float64/dpoint coordinates; largely superseded by their geos equivalents):

Since GeoDMS 20.23.1 a polygon whose outer ring comes out of a bg_ operation, or out of the repair of an invalid argument, in reverse order is kept, with that ring put in the right order. Before, such a polygon was removed right after its ring had been reversed, with only warnings about its rings in the log, so the result of the bg_ set operations and unions and of the bg_ variants of minkowski_sum and minkowski_difference could lack a polygon. Whether that happened depends on the input.

For examples, see here.

Operators based on the cgal library:

  • cgal_difference - element-wise difference of two polygon arrays (CGAL)
  • cgal_intersect - element-wise intersection of two polygon arrays (CGAL)
  • cgal_minkowski_sum - grow each geometry by a kernel, through CGAL::minkowski_sum_2: the exact one of the four backends
  • cgal_minkowski_difference - shrink each geometry by a kernel; the eroding counterpart
  • cgal_overlay_polygon - spatial overlay between two polygon datasets, producing all intersecting pairs (CGAL)
  • cgal_polygon - clean and validate polygon geometry using CGAL
  • cgal_polygon_connectivity - find all pairs of adjacent or overlapping polygons (CGAL)
  • cgal_split_polygon - split multi-polygons into individual single-polygon parts (CGAL)
  • cgal_split_union_polygon - dissolve polygons (optionally grouped by attribute), then split into individual parts (CGAL)
  • cgal_union - element-wise union of two polygon arrays (CGAL)
  • cgal_union_polygon - dissolve all polygons into one, optionally grouped by a partition attribute (CGAL)
  • cgal_xor - element-wise symmetric difference of two polygon arrays (CGAL)

Operators implemented by GeoDMS itself (prefix dms_), since 20.20.0:

A snap-rounding sweep of GeoDMS's own, the fifth family next to the four libraries. Its distinction is fault tolerance: the operands need not be valid polygons. Rings may self-intersect, self-touch, overlap, touch or fail to close, and are read under the even-odd rule, and an optional third argument gives the grid size that near-coincident vertices and slivers snap to. All six point types; the result has clockwise shells, counter-clockwise holes and no collinear vertices. The infix operators *, +, - and ^ keep their bp_ (integer) and geos_ (float) bindings. The family page is dms polygon operators; the worked example is Cleaning invalid polygons.

GeoDMS ©Object Vision BV. Source code distributed under GNU GPL-3. Documentation distributed under CC BY-SA 4.0.

GeoDMS

Clone this wiki locally