dms_polygon_connectivity - ObjectVision/GeoDMS GitHub Wiki

Geometric functions dms_polygon_connectivity

• dms_polygon_connectivity(polygon_data_item)
• dms_polygon_connectivity(first_polygon_data_item, second_polygon_data_item)
• dms_polygon_connectivity(polygon_data_item, group)
• dms_polygon_connectivity(first_polygon_data_item, second_polygon_data_item, first_group, second_group)

dms_polygon_connectivity finds the pairs of polygons that overlap and returns them as a new uint32 domain unit with a relation towards each polygon of a pair. It answers the same question as dms_overlay_polygon without computing the intersection geometry, and it does not even build one: use it when only the pairing is needed, and the overlay when the geometry or the area of each overlap is needed too.

With one argument the pairs are those within a single set, each once, with first_rel < second_rel. With two arguments they run between two sets.

Since GeoDMS 20.24.0 a group can be given to every polygon: a uint32 attribute on the domain of each polygon argument, both groups with the same values unit. The grouped forms answer which groups overlap, through their polygons:

• Two polygons of the same group are never a pair.
• One pair per pair of groups. Of all overlapping pairs between two groups, only the first in the order of (first_rel, second_rel) is returned. As soon as such a pair is known, the later candidates between those two groups are not compared at all, which is where the time is saved.
• Direction. With one set, dms_polygon_connectivity(polygons, group), the pairs run forward and a pair of groups has no direction: groups a and b give one pair. With two sets the pair of groups has a direction: a in the first set with b in the second is another pair of groups than b in the first set with a in the second.
• Undefined groups are never equal, and every pair of a polygon without a group is returned.

The typical use is the parts of a split, such as dms_split_convex_polygon, to find which original polygons overlap after a dms_minkowski_sum of their parts:

unit<uint32>   parts := dms_split_convex_polygon(pand/geometry);
attribute<rdc> grown (parts, polygon) := dms_minkowski_sum(parts/geometry, 1.0, '8D');
unit<uint32>   pairs := dms_polygon_connectivity(grown, parts/polygon_rel);
attribute<pand> pand1 (pairs) := parts/polygon_rel[pairs/first_rel];
attribute<pand> pand2 (pairs) := parts/polygon_rel[pairs/second_rel];

Every pair of panden then occurs once. When only those pairs are needed, dms_minkowski_sum on the whole panden followed by the one-argument form is faster still, 1.2 to 1.8 times on building outlines and CBS buurten; the split pays when the parts are needed anyway. For convex polygons, dms_convex_polygon_connectivity decides each pair without the sweep, which made the connectivity 5 to 20% faster on those data: finding the candidate pairs takes most of the time.

Unlike the four library variants, neither argument has to be a valid polygon: the pairs are decided by the even-odd reading of the dms polygon operators family. Two polygons form a pair when their intersection encloses an area; polygons that only touch are not a pair, as with bp_polygon_connectivity and unlike geos_polygon_connectivity.

The result is a new domain unit (uint32) with one entry per pair and two subitems:

• first_rel: relation to the domain of the first (or only) argument
• second_rel: relation to the domain of the second argument, or of the only argument in the one-argument form

Note the names: the unprefixed polygon_connectivity and box_connectivity call their relations F1 and F2.

• attribute arguments with a polygon value type: spoint, ipoint, wpoint, upoint, fpoint or dpoint

1. The composition type of the polygon arguments needs to be polygon.
2. The values unit of the two polygon arguments must match.
3. In the grouped forms, each group has the domain unit of its polygon argument, the groups are uint32, and in the four-argument form their values units must match.

20.20.0; the grouped forms since 20.24.0

The work is spread over the threads by the polygons of the first argument, so put the argument with the most, and the smallest, polygons first; see Which argument first under polygon operators.

unit<uint32> overlap := dms_polygon_connectivity(district/geometry)
{
    attribute<district> first_rel;
    attribute<district> second_rel;
}

• dms_overlay_polygon - the same pairs, with the intersection geometry of each pair
• dms_convex_polygon_connectivity - the same forms for convex polygons, each pair decided by an exact test instead of the sweep
• dms polygon operators - the family: the even-odd rule, the grid and what the result looks like
• geos_polygon_connectivity, bp_polygon_connectivity, bg_polygon_connectivity, cgal_polygon_connectivity - the same operator on the geometry libraries, which need valid operands
• polygon_connectivity - the unprefixed operator, for integer coordinates, with relations F1 and F2
• box_connectivity - the cheap approximation on bounding boxes
• polygon operators - the comparison of the operators that find pairs of polygons