MultiPolygon Support

[snodnipper]

I created a failing test against some test vector tiles from the mapbox/vector-tile-js repo.

See: testMultiPolygon() in https://github.com/snodnipper/mapbox-vector-tile-java/commit/fc38710b786356ac66d5b3f00c43ed0327f6d708

May I ask if this is a known limitation?

[ShibaBandit]

I'll check it out.

[snodnipper]

Cheers, using the MB JS tooling I get the following from the MVT.

[ [ { x: 2059, y: 2048 }, { x: 2048, y: 2048 }, { x: 2059, y: 2037 }, { x: 2059, y: 2048 } ], [ { x: 2037, y: 2059 }, { x: 2037, y: 2048 }, { x: 2048, y: 2048 }, { x: 2037, y: 2059 } ] ]

At 0,0 -> {"type":"Feature","geometry":{"type":"MultiPolygon","coordinates":[[[[0.966796875,0],[0,0],[0.966796875,0.9667509997666457],[0.966796875,0]]],[[[-0.966796875,-0.9667509997666315],[-0.966796875,0],[0,0],[-0.966796875,-0.9667509997666315]]]]},"properties":{},"id":1}

[ShibaBandit]

The current polygon parsing is intended to match the 2.1 spec (https://github.com/mapbox/vector-tile-spec/tree/master/2.1), where

4.3.4.4. Polygon Geometry Type ... An exterior ring is DEFINED as a linear ring having a positive area as calculated by applying the surveyor's formula to the vertices of the polygon in tile coordinates. In the tile coordinate system (with the Y axis positive down and X axis positive to the right) this makes the exterior ring's winding order appear clockwise.

An interior ring is DEFINED as a linear ring having a negative area as calculated by applying the surveyor's formula to the vertices of the polygon in tile coordinates. In the tile coordinate system (with the Y axis positive down and X axis positive to the right) this makes the interior ring's winding order appear counterclockwise.

I stepped through the mapbox polygon example and noticed I was coming up with negative areas for both rings using JTS (MvtReader#classifyRings()):

CGAlgorithms.signedArea()

So right now what's happening is the coordinates come out matching to what you posted above (thanks for posting those it was helpful), but the rings are discarded as interior when the parser was expecting an initial exterior.

[ShibaBandit]

I think the Mapbox parsers are more generous and will accept negative-signed-area outer rings if an outer ring has not been encountered yet because they're trying to be compatible with loosely-defined 1.0 MultiPolygon features? https://mapbox.github.io/earcut/ accepts it when the outer ring is null, a condition that I believe is outside the spec (AFAIK).

Is accepting this type of MultiPolygon a feature that you think will be needed in your project?

[snodnipper]

Thanks for looking into that. My immediate thoughts are that it would be a great addition to support this type of MultiPolygon as tippecanoe still appears to output v1* data afaik.

The tippecanoe data failures led me to check out the tests and add some mapbox test tiles...only for us to discover the legacy data version.

As for using this type of polygon in the projects I am involved with...I'll need to create thousands of polygons from GML/shapefile/geojson. I think my first point of call would be to see what is involved in getting tippecanoe to output 2.1 tiles - but my gut is telling me it would already be done if that was a trivial change.

If this lib could parse older data then that would certainly be helpful for immediate needs - as the JS toolset appears to handle these geometries.

Let me know if you have any recommendations for creating v2.1 compliant data easily from GIS data (e.g. geojson).

* I assumed it would be updated pretty quickly to the latest spec version but from initial inspection that does not appear to be the case.

[ShibaBandit]

I can look into a way to support the initial negative area ring case, but I'm not sure if that will completely solve it since I haven't done a 1.0 MVT parser. Is your tippecanoe output sharable?

[ShibaBandit]

Here's an example in another Mapbox project that has been corrected as of June 9th for encoding 2.0 MVT winding order - https://github.com/mapbox/geojson-vt/blob/master/src/tile.js

https://github.com/mapbox/geojson-vt/commit/a3aa2fa80b59ff993f864b94c4d23f3bda0318ad

function rewind(ring, clockwise) {
     var area = signedArea(ring);
     if (area < 0 === clockwise) ring.reverse();
 }

function signedArea(ring) {
     var sum = 0;
     for (var i = 0, len = ring.length, j = len - 1, p1, p2; i < len; j = i++) {
         p1 = ring[i];
         p2 = ring[j];
         sum += (p2[0] - p1[0]) * (p1[1] + p2[1]);
     }
     return sum;
}

I may ask on tippecanoe if they are enforcing this ordering or planning to.

[e-n-f]

Tippecanoe has claimed to produce v2 tiles since 03d5c897 (Apr 25) and has intended to get winding correct since 5dc9f503 (Oct 7). If you are getting incorrect tiles, I would appreciate a sample of the GeoJSON and tippecanoe flags you are using so I can fix it.

[snodnipper]

@ShibaBandit I have created a tippecanoe demo project using free data.

Perhaps it will be useful if I create a small project to read the MBTiles output and parse the geometries using your lib. I see @mourner says it produces 2.1 geometries. At the very least it would make a simple demo.

I would like to rule out a couple of things. Firstly that the geometries under test are only from Tippecanoe (and not, say, Mapbox Studio Classic) and secondly the data - I experienced issues with premium data.

@ericfischer thanks for the info.

[snodnipper]

I have created a very crude (sorry) demo project to demonstrate the issues reading tippecanoe input.

If you open Main.java and change boolean passThrough = true to false you should see the "com.vividsolutions.jts.geom.TopologyException: unable to assign hole to a shell" errors.

It should work with "./gradlew run" - but the default is to just spew out input without parsing (no error but an mbtiles that should look ok with mbview).

Note: I was using tippecanoe v1.12.5

[ShibaBandit]

@snodnipper Regarding the TopologyException, looks like some of the input geometry is invalid, so it likely won't work with JTS intersection (make tile geometry). You can check this with:

for(Geometry g : geoms) {
    if(!g.isValid()) {
        LOGGER.log(Level.SEVERE, "geometry invalid - " + g);
    }
    if(!g.isSimple()) {
        LOGGER.log(Level.SEVERE, "geometry not simple - " + g);
    }
}

The 'toString()' of a JTS geometry is WKT, so you can paste it into a viewer like QGIS with plugins.

Also, since you're reading an MVT, you don't have to recreate the geometry with...

JtsAdapter.createTileGeom()

...since coordinates are ready. You'll be transforming the geometry into something else since createTileGeom will invert the Y axis again.

I did notice that on the first MVT POLYGON I read out it had a negative area from CGAlgorithms.signedArea(r.getCoordinates()) so I can already see that I'm discarding initial rings, which may be leading to the invalid geometry.

I can try this again with altered handling where I accept negative initial rings as a exterior shell and see what happens...

[ShibaBandit]

@snodnipper Do you want to check out the neg_ring_exteriors branch and see if it fixes your issues? So was that output from tippecanoe? If so that could be an example to provide @ericfischer with negative exterior rings.

[snodnipper]

Thanks @ShibaBandit for that and sorry for the delay in getting back.

I have updated the demo to use the latest code and the output looks much better - much appreciated.

The only issue from JTS seems to be this error:

[main] ERROR com.wdtinc.mapbox_vector_tile.adapt.jts.JtsAdapter - side location conflict [ (3082.0, 2608.0, NaN) ]
com.vividsolutions.jts.geom.TopologyException: side location conflict [ (3082.0, 2608.0, NaN) ]
    at com.vividsolutions.jts.geomgraph.EdgeEndStar.propagateSideLabels(EdgeEndStar.java:300)
    at com.vividsolutions.jts.geomgraph.EdgeEndStar.computeLabelling(EdgeEndStar.java:139)
    at com.vividsolutions.jts.geomgraph.DirectedEdgeStar.computeLabelling(DirectedEdgeStar.java:127)
    at com.vividsolutions.jts.operation.overlay.OverlayOp.computeLabelling(OverlayOp.java:440)
    at com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:240)
    at com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:189)
    at com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:92)
    at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:96)
    at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:58)
    at com.vividsolutions.jts.geom.Geometry.intersection(Geometry.java:1338)
    at com.wdtinc.mapbox_vector_tile.adapt.jts.JtsAdapter.flatIntersection(JtsAdapter.java:141)
    at com.wdtinc.mapbox_vector_tile.adapt.jts.JtsAdapter.createTileGeom(JtsAdapter.java:84)
    at uk.os.wdtinc.demo.Main.lambda$main$1(Main.java:66)

All source data is from tippecanoe so it sounds like it could be an issue.

I have also translated some of their vector-tile-js code into java, where I could create valid multipolygon geojson - more for interests sake. I haven't attempted to put that output into the JTS or the ESRI geom library but it might be interesting in thrashing out such issues.

UPDATE: JtsAdapter.createTileGeom was erroneously called and that caused the error.

Thanks for sorting that issue.

Would you rather we investigate the tippecanoe rather than include this change in the lib?

[ShibaBandit]

Thanks for trying it. I will probably make some API changes to support reading this style of MultiPolygon rather than being strict and expecting positive area first. Hope to have this implemented soon as time allows.

[ShibaBandit]

@snodnipper If you want, you can post your inputs / outputs somewhere in this issue (re-open) - https://github.com/mapbox/tippecanoe/issues/285 ... or create your own. I don't do much c++ so I prob won't do a pull request. Totally up to you if you want to pursue it.

[e-n-f]

If you have specific examples of polygons that Tippecanoe is getting wrong, please do post the source GeoJSON and the tippecanoe options you are using here or in a Tippecanoe issue so I can fix whatever is going wrong. Thanks!

[snodnipper]

@ericfischer - I'll try and get some (isolated) data together to you in the coming days.

If you need to shoot ahead then you can check out the geojson created by this project. Changing z12 to 5 (from memory) will show relatively few geoms inc. invalid ones afaik.

[e-n-f]

Thanks @snodnipper. I'm tracking this in https://github.com/mapbox/tippecanoe/issues/295 now.

[ShibaBandit]

Merged support into master in #2