Dissolve GeoJSON : Please have a talk with w8r/martinez

[cyrilchapon]

In here we are trying to "dissolve" a huge mass of geojson Polygons / MultiPolygons.

We followed the documentation, and did this :

  const polyboolPolygons = polygons.map(polybool.polygonFromGeoJSON)

  const unionPolyboolPolygon = polyboolPolygons.reduce(
    (polyboolPolygonAcc, polyboolPolygon) => (
      (!polyboolPolygonAcc && polyboolPolygon) ||
      polybool.union(polyboolPolygonAcc, polyboolPolygon)
    ),
    null
  )

  const unionPolygon = polybool.polygonToGeoJSON(unionPolyboolPolygon)

This works perfectly, but it takes like 20 seconds to process the whole stuff...

On the other side, w8r/martinez process it in less than 400ms... but produces aberrations, like this :

(The base "larger" polygon has many holes, and you can see some are respected, others are curiously understood as other polygons, witch comes "over" the first)

I cannot really provide any dataset, because this one is huge, and I could not reproduce on a smaller one.

Sooo, is there a chance we can engage in a discussion between the 2 repos, to come up with a solution fully working, in less than 400ms? 😄

(Note: I duplicated the issue there)

[velipso]

Just re-reading this -- you should be using the core API to calculate a more efficient union. There is an example of literally what you describe in the docs, if you want to union a lot of shapes together.

That will speed things up, not sure by how much.

[bluenote10]

I've had a brief look at both implementations, and it looks like there are other difference that affect performance:

• The other repo is based on the 2013 version of the algorithm, this implementation here on the 2008 version (too bad the 2013 is behind a paywall -- I've no idea how different they are conceptually).
• The other implementation uses splay trees for the sweep status and priority queues for maintaining the events. This implementation here is a bit simpler, because it uses linked lists with insertion sort for both -- so there is probably a O(log N) vs O(N) difference here.
• It should be mentioned though that the other implementation has quite a lot of open issues in terms of wrong behavior. I have checked many of them, and the polybooljs implementation handles them all correctly. So maybe it is also the more accurate / robust handling of edge cases (or the precision mode).