polygon operators

Back to Geometric functions


Polygon operators calculate with Polygon geometries: they combine two polygon attributes element by element, find the pairs of polygons that meet, dissolve, split and clean polygons, grow, shrink and simplify them, measure them and convert them to a grid. Most of these operations exist in several implementations, one per geometry library, and the prefix of the operator name says which: geos_ for GEOS, bg_ for boost geometry and bp_ for boost polygon (both described on boost polygon), cgal_ for cgal, and dms_ for the implementation of GeoDMS itself, described on dms polygon operators.

operations and their implementations

The table gives, per operation, the operator of each library. An empty cell means that the library has no operator for it.

operation geos_ dms_ bg_ bp_ cgal_
intersection geos_intersect dms_intersect bg_intersect bp_intersect cgal_intersect
union geos_union dms_union bg_union bp_union cgal_union
difference geos_difference dms_difference bg_difference bp_difference cgal_difference
symmetric difference geos_xor dms_xor bg_xor bp_xor cgal_xor
clean and validate geos_polygon dms_polygon bg_polygon bp_polygon cgal_polygon
dissolve geos_union_polygon dms_union_polygon bg_union_polygon bp_union_polygon cgal_union_polygon
split into single polygons geos_split_polygon dms_split_polygon bg_split_polygon bp_split_polygon cgal_split_polygon
dissolve, then split geos_split_union_polygon dms_split_union_polygon bg_split_union_polygon bp_split_union_polygon cgal_split_union_polygon
split into convex parts   dms_split_convex_polygon, dms_split_convex_polygon_keilsnoeyink      
pairs that meet, with their intersection geos_overlay_polygon dms_overlay_polygon bg_overlay_polygon bp_overlay_polygon cgal_overlay_polygon
pairs that meet, as relations geos_polygon_connectivity dms_polygon_connectivity, dms_convex_polygon_connectivity bg_polygon_connectivity bp_polygon_connectivity cgal_polygon_connectivity
grow by a kernel, see minkowski_sum geos_minkowski_sum dms_minkowski_sum bg_minkowski_sum bp_minkowski_sum cgal_minkowski_sum
shrink by a kernel, see minkowski_difference geos_minkowski_difference dms_minkowski_difference bg_minkowski_difference bp_minkowski_difference cgal_minkowski_difference
buffer of polygons geos_buffer_multi_polygon dms_buffer_multi_polygon Bg_buffer_multi_polygon, bg_buffer_single_polygon    
buffer of arcs geos_buffer_linestring   Bg_buffer_linestring bp_buffer_linestring cgal_buffer_linestring
buffer of points geos_buffer_point, geos_buffer_multi_point   Bg_buffer_point, Bg_buffer_multi_point bp_buffer_point, bp_buffer_multi_point cgal_buffer_point, cgal_buffer_multi_point
buffer of any geometry geos_buffer        
simplify polygons geos_simplify_multi_polygon   bg_simplify_multi_polygon, Bg_simplify_polygon    
simplify arcs geos_simplify_linestring   Bg_simplify_linestring    
keep the outer rings     bg_outer_multi_polygon, bg_outer_single_polygon    

The operators outer_multi_polygon and outer_single_polygon, without a prefix, are the same as their bg_ namesakes. The bp_ clean, dissolve and split operators also come with the suffixes _filtered, which drops rings below a given area, and _inflated and _deflated, which grow or shrink the polygons by a given distance first, for instance bp_union_polygon_filtered; see Boost polygon functions and Polygon filtered. The bp_ names that carry a kernel shape, such as bp_polygon_i4HV, are deprecated: they work, and log a warning that names the replacement with minkowski_sum or minkowski_difference; see Polygon inflated and Polygon deflated.

choosing a library

prefix point types operands when to use
geos_ dpoint for clean, dissolve, split, pairs and the kernel operators; every point type for the other operators valid polygons; an invalid operand is repaired with MakeValid first the default for data that is valid: fast, robust, and the widest set of operations
dms_ every point type need not be valid: rings are read under the even-odd rule data that is not valid, or a model that needs a tolerance; see dms polygon operators
bg_ every point type valid polygons, repaired through GEOS largely superseded by geos_; bg_union_polygon is not reliable on real data
bp_ spoint and ipoint; the buffers every integer point type valid polygons, with coordinates below 2^25 integer data, and the _filtered, _inflated and _deflated variants
cgal_ every point type valid polygons exact arithmetic, where precision matters more than speed

The infix operators * (intersection), + (union), - (difference) and ^ (symmetric difference) apply the bp_ operator to spoint and ipoint polygons and the geos_ operator to fpoint and dpoint polygons, see Mul (polygon intersection), Add (union) and Sub (difference). The functions Bitand, Bitor and bitxor do the same as *, + and ^. For wpoint and upoint polygons, and for the reading of the dms_ family, call the operator by its name.

element by element

The intersection, union, difference and symmetric difference combine two polygon attributes with the same Values unit, element by element: both on the same Domain unit, or one of them a Parameter that is combined with every element of the other. The dms_ variants take an optional third argument, the grid size that serves as the tolerance.

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 attribute, for the pairs within it, each pair once with first_rel < second_rel, or two, for the pairs between them. The relations first_rel and second_rel refer to the domain unit of the polygons they point at, whatever its value type and range.

The libraries differ in which pairs they find:

operator a pair when result items
geos_overlay_polygon the polygons overlap or touch; a touching pair has an empty geometry geometry, first_rel, second_rel
dms_overlay_polygon, bg_overlay_polygon, bp_overlay_polygon, cgal_overlay_polygon the polygons have a common interior point; for dms_ the operands need not be valid geometry, first_rel, second_rel
geos_polygon_connectivity the polygons overlap or touch first_rel, second_rel
dms_polygon_connectivity, bg_polygon_connectivity, bp_polygon_connectivity, cgal_polygon_connectivity the polygons have a common interior point; for dms_ the operands need not be valid first_rel, second_rel
dms_convex_polygon_connectivity as dms_polygon_connectivity, for convex polygons, with an exact test per pair first_rel, second_rel
Polygon_connectivity the polygons overlap or touch; one attribute with spoint or ipoint coordinates F1, F2
box_connectivity the bounding boxes overlap or touch; one attribute F1, F2

dms_polygon_connectivity and dms_convex_polygon_connectivity also take a group per polygon, and then return no pair within a group and one pair per pair of groups. For the intersection of two polygon attributes that are already paired element by element, use the element-by-element operators above.

which argument first

The pair operators divide their work by the polygons of the first argument. Each of them is compared, on one thread, with the polygons of the second argument whose bounding box meets its own. The polygons of the first argument are spread over the threads, also within one tile, and the tiles of the second argument are handled one after another. 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. As an example, dms_polygon_connectivity of the 342 CBS gemeenten and the 14,729 CBS buurten took 16 to 17 s with the gemeenten first and 6 s with the buurten first, on 32 logical processors with GeoDMS 20.24.0.

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.

dissolving, splitting and cleaning

  • xxx_union_polygon(polygons) dissolves all polygons into one value, a Parameter. With a relation or partition attribute as second argument it dissolves per group, with one element per value of its Values unit: the dissolve by attribute of GIS terminology.
  • xxx_split_polygon(polygons) results in a new domain unit with one row per single polygon, with the subitems geometry and polygon_rel, the relation to the element that the part came from.
  • xxx_split_union_polygon dissolves first and then splits.
  • xxx_polygon returns each element as a clean polygon. The library variants repair what their library considers invalid; dms_polygon reads every element under the even-odd rule and writes it back valid.
  • dms_split_convex_polygon and dms_split_convex_polygon_keilsnoeyink split each polygon, holes included, into convex parts.

growing, shrinking and simplifying

A buffer grows each geometry by a distance, with round corners approximated by a given number of points; a negative distance shrinks a polygon. A buffer of points or arcs results in polygons; these buffers are also listed on point operators and arc polygon operators. geos_buffer picks the buffer that fits the Composition of its argument.

The kernel operators grow or shrink by a shape instead of a distance: a kernel polygon, or a named shape at a given size. minkowski_sum and minkowski_difference describe them for all five libraries.

The simplify operators remove the points that lie within a tolerance distance from the simplified line, with the Ramer-Douglas-Peucker algorithm. The tolerance is a Parameter in the units of the coordinates. Bg_simplify_polygon simplifies each ring on its own and is meant for elements that are a single polygon; the _multi_polygon variants take any polygon. Each element is simplified on its own, so the shared border of two neighbouring polygons is simplified twice, differently, which leaves gaps and overlaps between them; Simplify geometry points to a configuration that simplifies a set of neighbouring polygons consistently.

ring order and validity

A valid polygon has its outer rings clockwise and its holes counter-clockwise; see Point order in polygons.

  • reverse_polygon reverses the order of every ring, without changing the layout of the sequence.
  • fix_winding_order puts every ring in that order, deriving whether it is an outer ring or a hole from the nesting of the rings, which also repairs a multi polygon of which only some rings are reversed.
  • has_correct_winding is true for each element whose ring order is correct. Unlike the test area(g) < 0 it also finds a multi polygon of which only some rings are reversed.
  • fix_polygon applies fix_winding_order and repairs self-intersections and other invalid geometry with GEOS MakeValid.

measuring, locating and converting

see also