incorrect rendering of holes in GeoJSON polygons

[tyrasd]

When rendering polygons from a GeoJSON data layer, only some of the holes get rendered correctly. The rest gets an outline but is filled like the rest of the polygon.

Here is a cut-out of the rendering of a single large (multi)polygon containing several holes.

Taking a deeper look at the data, I notice that all the incorrectly filled holes have clockwise point order. But as of the geojson specs point order shouldn't matter.

[tmcw]

Upstream in Mapnik if true. ping @springmeyer this GeoJSON passes a basic geojsonhint sniff test.

[tyrasd]

ps: the GeoJSON file is displayed correctly in other tools such as QGIS. Or even in TileMill after a manual conversion to shapefile with ogr2ogr.

[springmeyer]

Where exactly in the spec does it say that order (by point you mean winding, ya?) does not matter? My sense is that winding order of geojson should match the WKT/WKB spec. In this case the polygon example from the geojson spec is non-conforming, which is what we determined a few years back: https://github.com/mapnik/mapnik/issues/450#issuecomment-2366770

[tyrasd]

Yes, with “point order” I meant winding.

The spec says: “For type "Polygon", the "coordinates" member must be an array of LinearRing coordinate arrays. […] the first must be the exterior ring and any others must be interior rings or holes.” and “A LinearRing is closed LineString with 4 or more positions.”

In “Appendix A. Geometry Examples” there is an example polygon with a hole that has clockwise winding:

{ "type": "Polygon",
  "coordinates": [
    [ [100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0] ],
    [ [100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2] ]
    ]
 }

[jfirebaugh]

/cc @sgillies :)

[sgillies]

Yeah, in the GeoJSON spec a hole is a hole and orientation and winding doesn't matter. For the outside ring, I usually advocate for counterclockwise (right hand rule) points, to mean a surface facing "up" (positive z).

[springmeyer]

@sgillies - thanks for the clarification. So the problem here is that Mapnik expects clockwise winding order for the first exterior ring for proper rendering. If that is also what you advocate, does it make sense to fix the geometry examples to use that orientation?

/cc @artemp - sounds like in the geojson plugin we need to call boost::geometry::correct on negative area polygons.

This helps clear up why topojson has the no-force-clockwise option: https://github.com/mbostock/topojson/wiki/Command-Line-Reference#geometry

[artemp]

@springmeyer - i recall agg can handle both CW and CCW ordering so maybe better fix this at rasteriser level. I'll take a look, thanks.

any reason we can't just ?

ras_ptr->filling_rule(agg::fill_even_odd);

[sgillies]

@springmeyer I'm advocating CCW for polygons that face up (toward increasing z), like KML. GeoJSON is definitely underspecified in this area, and by design: some of the authors didn't want to be constrained to valid geometries.

I think that it could be useful to define better behaved profiles of GeoJSON and publish them.

[artemp]

I changed polygon filling rule from non-zero to even-odd in mapnik master - https://github.com/mapnik/mapnik/commit/2eaf6a1ead673a83cd92f7d84fee7d2db1d77aa0

I wonder why we switch to non-zero in the first place.. was it overlapping inner rings and/or overlapping multipolygons in OSM ? /cc @springmeyer

[springmeyer]

@artemp - we considered a patch for even/odd fill back in https://github.com/mapnik/mapnik/issues/450 but never applied because we saw it caused rendering problems for other polygons. But this may have been incorrect/unrelated - so we should revisit.

[artemp]

@springmeyer - I see #450 references even_odd_corruption.png - have you got a copy somewhere ?

[springmeyer]

@artemp - yep, dug this up from trac archive: http://cl.ly/0Z0d2i1W1h2r

[springmeyer]

update: looks like the original patch to Mapnik to support this alternative winding order as part of mapnik/mapnik#450 works, but to avoid artifacts with lines we need to maintain fill_non_zero. Tracking this at mapnik/mapnik#2054.

In summary this should work in the next release of TileMill that includes an updated Mapnik.

[tmcw]

Would the general consensus be

• First ring (outer ring) counter-clockwise
• Interior rings clockwise

Or is it just important that the order is different between outer and inner? I tried looking for the WKT spec, but remembered why I should never try to do that.

[rcoup]

Or is it just important that the order is different between outer and inner?

Orientation of the outer ring is important for geographic/latlong coordinate systems where you want to use a polygon to describe eg. "Australia" vs "All the world except Australia". And for rendering :smile:

• KML/Google Earth uses LHR (CCW) for exterior rings.
• GEOS/JTS/PostGIS have tended to favour RHR (CW) but afaik keep track of which rings are interior/exterior explicitly so it doesn't matter as much.
• MS SQL Server uses LHR (CCW) and pre-2012 used to prevent rings bigger than a hemisphere.

[sgillies]

@tmcw let's do follow the right hand rule, counter-clockwise exterior rings, clockwise interior rings.

[strk]

Just a note: GEOS/JTS/PostGIS don't care about winding. The presence of an ST_ForceRHR function is just there to help with clients that do care.

[RAytoun]

Can you let me know what the final outcome is for the winding of polygons. I can then teach new mappers from the start to do all polygons as clockwise/anti-clockwise so that if an inner is required at any stage the outer direction will be correct. Thanks.

[pnorman]

This issue is about geojson and other mapnik datasources, and not something that OSM mappers need to worry about when mapping. The only time winding order matters for ways is coastlines, where it's land on the left, but the reasons are entirely unrelated to Mapnik.

[RAytoun]

OK Thanks Paul.

On 10 February 2015 at 17:37, Paul Norman notifications@github.com wrote:

This issue is about geojson and other mapnik datasources, and not something that OSM mappers need to worry about when mapping. The only time winding order matters for ways is coastlines, where it's land on the left, but the reasons are entirely unrelated to Mapnik.

— Reply to this email directly or view it on GitHub https://github.com/mapbox/tilemill/issues/2110#issuecomment-73744744.

[springmeyer]

Re-reading this ticket and will summarize my understanding:

• Some applications, depending on how they store geometries, may care about winding order and some may not (need to) care.
• Same goes for formats in practice: depending on the way the format encodes polygon geometries the winding order may or may not (need to) matter.
• GeoJSON does not specify a required winding order for polygons: therefore to correctly interpret polygons with holes (interior rings) decoding applications need to treat the first array as the exterior ring and all following arrays as interior rings.
• The original rendering bug in Mapnik (causing the incorrect polygon filling in Tilemill) resulted from Mapnik using agg::filling_rule_e::fill_non_zero for agg::rasterizer_scanline_aa which expects that polygons will have interior rings with a different winding order. The solution could have been to detect GeoJSON interior rings and ensure their winding order was reversed, but instead we went with a simpler approach of using agg::filling_rule_e::fill_even_odd which does not depend on winding order to draw holes. In the future we may revisit this.
• When winding order matters for geometry encoding, there is generally consensus that the winding order of the exterior ring should be the opposite of the interior rings. However, some applications prefer RRH (right hand rule) and some prefer LHR (left hand rule).
• There is some contradicting details however in the comments above about what the terms RRH and LHR actually imply about winding order.
  • PostGIS ST_ForceRHR doc says RHR == CW for exterior ring, CCW for interior rings
  • @rcoup confirms the postgis doc here that RHR == CW for exterior ring, CCW for interior rings.
  • @sgillies says here that RHR == CCW for exterior ring, CW for interior rings
  • The KML Spec confirms @sgillies that RHR = CCW oriented coordinates.
  • Luckily XKCD clears up this confusion up completely
  • BTW, the shapefile spec does not mention RRH, but states that exterior rings (aka outer rings) are CW, and interior are CCW
• More important than differences in terminology, the important thing about polygon winding order is that a spec state clearly the expected orientation of exterior and interior rings. The current plan is CCW exterior, CW interior for vector tiles as per https://github.com/mapbox/mapnik-vector-tile/issues/59.

[artemp]

The current plan is CCW exterior, CW interior for vector tiles as per mapbox/mapnik-vector-tile#59.

CCW for exterior ring and CW for interior rings is in sync with OGC/ISO specs : @springmeyer - surprised PostGIS is not compliant with (see below)

6.1.11 Polygon, Triangle
6.1.11.1 Description
A Polygon is a planar Surface defined by 1 exterior boundary and 0 or more interior boundaries. Each interior boundary defines a hole in the Polygon. A Triangle is a polygon with 3 distinct, non-collinear vertices and no interior boundary.
The exterior boundary LinearRing defines the “top” of the surface which is the side of the surface from which the exterior boundary appears to traverse the boundary in a counter clockwise direction. The interior LinearRings will have the opposite orientation, and appear as clockwise when viewed from the “top”,
The assertions for Polygons (the rules that define valid Polygons) are as follows:
a) Polygons are topologically closed;
b) The boundary of a Polygon consists of a set of LinearRings that make up its exterior and interior boundaries;
c) No two Rings in the boundary cross and the Rings in the boundary of a Polygon may intersect at a Point but only as a tangent, e.g.
26 Copyright © 2010 Open Geospatial Consortium, Inc.
∀ P ∈ Polygon, ∀ c1,c2∈P.Boundary(), c1≠c2,
∀ p,q ∈Point,p,q ∈ c1,p ≠ q, [p∈c2]⇒[∃ δ>0∋[|p-q|<δ]⇒[q∉c2]];
Note: This last condition says that at a point common to the two curves, nearby points cannot be common. This forces each common point to be a point of tangency.
d) A Polygon may not have cut lines, spikes or punctures e.g.:
∀ P ∈ Polygon, P = P.Interior.Closure;
e) The interior of every Polygon is a connected point set;
f) The exterior of a Polygon with 1 or more holes is not connected. Each hole defines a connected component of the exterior.
In the above assertions, interior, closure and exterior have the standard topological definitions. The combination of (a) and (c) makes a Polygon a regular closed Point set. Polygons are simple geometric objects. Figure 11 shows some examples of Polygons.

[strk]

PostGIS does not care about orientation.

It does have an ST_ForceRHR function to force the "right-hand-rule" where the rule is defined as "area is on the right as you walk on the edge", which makes shells clockwise and holes counterclockwise.

Is there any definition of "right-hand-rule" in OGC ?

You can obtain the reverse ordering ST_Reverse(ST_ForceRHR(geom))

[sgillies]

@strk KML's "right-hand rule" is from André-Marie Ampère, not the OGC. Imagine the fingers of your right hand curling around the polygon's exterior with your thumb pointing "up" (toward space), signing a positive area for the polygon in the signed area sense.

[pramsey]

"Right hand rule" as defined by PostGIS inherits from a BC government data quality rule for data capture, which was described as "right hand rule" (right hand in the area of interest as you walk the line) but is in fact the opposite of "right hand rule" as understood by computer graphics people and most others. I think the FME also inherited this terminological snafu from BC. As @strk notes, internally PostGIS/JTS/GEOS/OGC/WKT/WKB don't make any assumptions about winding order.