Point order in polygons

For some functions, such as the dissolve operators like geos_union_polygon, the sequence order of points in a Polygon matters.

rules

The following rules apply to the sequence of points in a Polygon:

  1. outer rings need to be configured clock wise
  2. inner rings (lakes) are configured counter clock wise
  3. the first and the last point need to have the same coordinate

If the sequence of points is configured manually and used in the Sequence2points, always configure the correct sequence, although for the map and functions like Point_in_polygon an incorrect sequence might not matter.

The shapefile writers take care of rule 3: they close a ring that the value left open, so an ESRI Shapefile that the GeoDMS writes can be read back by Gdal.vect, QGIS and ArcGIS. Rules 1 and 2 are never changed by a writer; see fix_winding_order and reverse_polygon below.

multi-polygons

A multi-polygon lives in the same single point sequence. Each ring is written closed, one after the other, and the reader recognises a new ring when a point repeats the first point of that ring. After the rings of a polygon, the sequence walks back to where it came from with backtrack points, so that the whole sequence starts and ends at the very first point:

outer(closed) hole0(closed) hole1(closed) hole0[0] outer[0]      // one polygon with two holes
A(closed) B(closed) C(closed) B[0] A[0]                          // three separate polygons

Which polygon a hole belongs to follows from this order: an inner ring belongs to the outer ring that precedes it, not to the multi-polygon as a whole. That distinction matters whenever a polygon is nested inside the hole of another polygon, such as a shed on a courtyard enclosed by a building block.

what the readers accept

The geos_, cgal_ and bg_ operators read the role of a ring relative to the feature it belongs to: the first ring that survives decides what “outer” means, a ring wound the other way is a hole of it, and a ring wound like it opens the next polygon. A feature whose rings are all reversed, usually because a source lists its coordinates in latitude/longitude order, therefore arrives with the right topology. geos_polygon and cgal_polygon also hand back a correctly wound result, because both normalise the winding of what they produce; bg_polygon preserves the shape it read, so its result stays negatively wound.

This only covers a feature whose rings are all reversed. When some rings of a feature are reversed and others are not, no rule based on orientation can recover the roles; use fix_winding_order, which derives them from the nesting instead. Such features are often irregular in other ways too, for instance with outer rings that outer_multi_polygon reports as overlapping.

The dms_ operators do not look at the orientation at all: they read every element under the even-odd rule, see dms polygon operators.

validation

Use has_correct_winding: it is True only when the orientation of every ring agrees with its nesting, no ring collapsed, and the geometry is topologically valid.

attribute<bool> winding_ok (district) := has_correct_winding(district/geometry);

The sign of the Area is not a sufficient test. It does show a feature whose rings are all reversed, as a negative area, but area is a single signed sum over the whole sequence, so a feature of which only the lake is reversed comes out too large rather than negative.

repairing the point order

Which operator to reach for depends on what is wrong:

symptom operator
every ring of the feature is reversed, e.g. a source in latitude/longitude order reverse_polygon; the readers cope with this on their own, so this is about storing the layer in the documented order
some rings reversed and others not; islands in lakes ending up in the wrong role fix_winding_order
self-intersecting rings, holes outside their shell, overlapping outer rings fix_polygon

reverse_polygon and fix_winding_order never move a vertex, so they are safe to apply to a whole layer. fix_polygon does move coordinates, because repairing a self-intersection means introducing the intersection point.

Reversing the whole point sequence of a multi-polygon, for instance with Sequence2points, Reverse and Points2sequence, does not work: it destroys the ring structure described above, because the reader recognises a new ring where a point repeats the first point of the ring. reverse_polygon reverses each ring in place instead, which leaves every delimiter and backtrack point untouched.