Dissolve : Please have a talk with voidqk/polybooljs

[cyrilchapon]

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

We naturally thought of making a successive and recursive union, with that

  const dissolved = polygons.reduce(
    (dissolvedAccumulator, feature) => (
      (!dissolvedAccumulator && feature) ||
      union(dissolvedAccumulator, feature)
    ),
    null
  )

(This simple implementation uses turf.union, which uses w8r/martinez under the hood. I also tested it with raw w8r/martinez.union, please trust me)

We are encountering bugs like this :

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

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

One the other side, voidqk/polybooljs perfectly succeed in dissolving the whole. See

... but it takes like 20 seconds to achieve this, whereas w8r/martinez takes under 400ms...

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)

[rowanwins]

Hi @cyrilchapon

@w8r has been working through a number of issues with the algorithm, unfortunately it's far from easy to get something performant and that covers all the edge cases.

There is also another repo which is somewhere between the two in terms of performance so it might be worth checking that out to see how it performs on your test case.

Each author has tackled things very differently so it's not just as simple as picking the best pieces out from each unfortunately.

Cheers

[cyrilchapon]

@rowanwins, thanks for the clarification

There is also another repo which is somewhere between the two in terms of performance so it might be worth checking that out to see how it performs on your test case.

I just landed on it, I'll sure give it a try, thanks :)

Each author has tackled things very differently so it's not just as simple as picking the best pieces out from each unfortunately.

Yeah, but that would be worth a look, or a discussion IMHO. Currently, we have 3 different repos to kinda achieve the same thing (roughly boolean operations on polygons). Cherry-picking one or another in case of "best performance" or "best edge-cases" is far from ideal, isn't it ?

Haven't been trying mfogel/polygon-clipping, I just bring my "lambda user" POV : w8r/martinez is incredibly fast, voidqk/polybooljs is incredibly covering each cases. I'm not a math guy, and did not digg into algorithmic concerns, but things being "tackled very differently", the root is a single algorithm, and things could converge, or at least give inspiration, couldn't they ?

[cyrilchapon]

FYI, polygon-clipping succeeds on it, in a decent still not that fast computing time.

(Well actually it fails on the raw input, but succeeds if I flatten every multi polygons to polygons; but that's not the point I'll open an issue there)