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.
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_polygondissolves first and then splits.xxx_polygonreturns 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) < 0it 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
- Area gives the area of each polygon.
- Centroid gives the center of mass, mid a point inside the polygon that is cheaper to compute, and Centroid_or_mid the centroid when it lies inside the polygon and a mid point otherwise.
- Lower_bound, Upper_bound and Center_bound give the lowest, highest and center X and Y of the points of each polygon.
- points2polygon makes polygons from sequences of points.
- Poly2grid and poly2grid_untiled give a grid representation of polygons; poly2allgrids and poly2allgrids_uint64 give a cross table of polygons and grid cells, see Polygon to grid.
- canyon computes street canyon indicators for road points from the surrounding building facades.
see also
- dms polygon operators, the
dms_family: the even-odd rule and the grid as tolerance - Cleaning invalid polygons, a worked example of the
dms_operators - Polygon processing example and Buffer processing example
- Spatial joins and allocation, how the pair operators relate to the other matching functions
- point operators, arc polygon operators and point polygon operators