Polygon winding order & holes vs outer rings

mourner commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

@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 commented 10 years ago

:+1: for having a specified winding order.

pnorman commented 10 years ago

@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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

Another approach is to just split MultiPolygons into several Polygon features. This is how Mapzen solved the issue: https://github.com/mapzen/mapbox-vector-tile/issues/4

bcamper commented 9 years ago

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

springmeyer commented 9 years ago

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:

[x] 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. - https://github.com/mapnik/mapnik/pull/2739
[x] When encoding polygon rings into protobuf geometries
[x] When decoding back into internal structure
[x] When transforming, reprojecting (no problems here)
[x] When simplifying (boost::geometry::simplify does)
[ ] When clipping - https://github.com/mapnik/mapnik/issues/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: #99
Work is happening at #94
Depends on https://github.com/mapnik/mapnik/labels/mapnik-geometry

springmeyer commented 8 years ago

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

mapbox / mapnik-vector-tile

Polygon winding order & holes vs outer rings #59