Polygon winding order & holes vs outer rings

[mourner]

Do geometry rings have a defined winding order in vector tiles? E.g. counter-clockwise for outer rings and clockwise for rings? Or should I expect any order of any particular ring?

Winding order isn't mentioned anywhere in spec, but some polygon algorithms depend on a certain winding order. Also, some algorithms (especially triangulation) need to know if a polygon ring is a hole or an outer ring, which could also be derived from winding order if geometry is flattened.

[mourner]

OK, so Artem says we pass winding order as is, so there's no easy way to derive ring status... Could you consider winding order correction for a future release? It's pretty easy, and given that geometries are flattened, it would be extremely useful. Usual accepted order is CCW for outer rings, CW for rings.

[mourner]

Note that closing #53 will also close this issue, since polygon clipping procedure also resets winding order. Although fixing just the latter is much easier.

[pnorman]

Could you consider winding order correction for a future release?

Wouldn't the spec need to change for rings to have a defined winding order, or are you suggesting giving an order that wasn't there in the tile when parsing one?

[mourner]

@pnorman yes, I'm suggesting changing the winding order of polygon rings depending on whether it's a hole or an outer ring. I don't see any problems with this since the original winding order is pretty much random and has no practical use.

[jfirebaugh]

👍 for having a specified winding order.

[pnorman]

@pnorman yes, I'm suggesting changing the winding order of polygon rings depending on whether it's a hole or an outer ring. I don't see any problems with this since the original winding order is pretty much random and has no practical use.

I don't see an issue with it either, but I'm just questioning if it's a mapnik-vector-tile issue or an issue that the specification doesn't require a winding order.

[jfirebaugh]

The fix for this would be to update both the specification (to require a winding order), and mapnik-vector-tile (to output spec-compliant windings).

[mourner]

Another thing to note is that Mapnik VT output doesn't have outer1, inner1, inner1, ..., outer2, inner2, ... order — it can have outer rings and holes mixed up in random order, which is a problem when you're trying to figure out which is which.

[mourner]

Another approach is to just split MultiPolygons into several Polygon features. This is how Mapzen solved the issue: tilezen/mapbox-vector-tile#4

[bcamper]

@mourner yep, not an ideal solution, it would be nice to have multi-geometries directly supported in the spec.

[springmeyer]

Update here: my plan is to have mapnik-vector-tile ensure:

• 1. exterior rings are encoded as CCW
• 2. interior rings are encoded as CW
• 3. interior rings always follow exterior rings

So, here are some examples then of how you would decode:

• CCW -> single polygon, no interior rings
• CCW,CW,CW -> single polygon, two interior rings
• CCW,CCW,CCW - > Multipolygon with 3 polygons, each with only an exterior ring
• CCW,CCW,CCW,CW - > Multipolygon with 3 polygons, each with one exterior ring, and the final one with one exterior ring and one interior ring
• CW -> single interior ring: degenerate, throw it out

As part of this push we need to ensure these winding order expectations are consistently maintained at a variety of steps. To that end I'll update the below set of check boxes as things progress:

• Respect and/or correct winding order when decoding geometries from postgis, shapefiles, geojson, etc into internal structure. Shapefile window order already matches or expectation so we should not need to do anything. PostGIS and Geosjon make no promises so we'll correct on the fly. - New geometry storage and API mapnik/mapnik#2739
• When encoding polygon rings into protobuf geometries
• When decoding back into internal structure
• When transforming, reprojecting (no problems here)
• When simplifying (boost::geometry::simplify does)
• When clipping - Maintain ordering of exterior/interior rings after clipping mapnik/mapnik#2756
• Test coverage to explore when/to what extent self-intersections will break the ability to detect winding order
• Test coverage to explore when/to what extent degenerate exterior rings might break assumptions of ring order and how geometry culling will need to play this smart: Culling degenerate geometries #99
• Work is happening at [wip] Mapnik geometry #94
• Depends on https://github.com/mapnik/mapnik/labels/mapnik-geometry

[springmeyer]

This ticket is now resolved thanks to the work of many. Going to close with a short recap:

• The Mapbox Vector Tile Specification version 2 clarified how winding order and ring order should be: https://www.mapbox.com/vector-tiles/specification/. The winding order must be CW for exterior rings when viewed in screen coordinates (it will be the reverse, CCW in geographical coordinates)
• The spec text is at https://github.com/mapbox/vector-tile-spec/tree/master/2.1
• The mapnik-vector-tile encoder now adheres to the v2 spec as of >= v1.0.1 (https://github.com/mapbox/mapnik-vector-tile/blob/master/CHANGELOG.md#100)

https://www.mapbox.com/blog/vector-tile-spec-changes/ is a good resource to learn more about what changed.

/cc @rouault