Shorter version of my question:
Is there any polygon union algorithm that allows me to change one of the polygons quickly?

Longer version:
Currently the major performance bottleneck I'm facing in one of my own project is to quickly compute the union of multiple polygons. I've been using the polybooljs library, which is based on the algorithm by F. Martinez etc. (2008), and it is indeed a lot faster than my previous approach already, but this part is still the bottleneck.

One obvious direction for improvement is based on the observation that, in my use case, my polygons are dynamic, and in most of the cases I would only change one of them at the time, so instead of starting over and compute the entire union, it would be so much faster if I could just replace one of the polygons in the union somehow.

However, the only way I can think of to make this work, is to keep tracking the number of times each subregion of the union is contributed by the polygons involved, so that I could correctly removed those parts that are contributed only once by the old polygon, and then make a union with the new one (and update the contribution accordingly). But as I read through the Martinez paper, it doesn't seem like their algorithm even have the notion of subregions, let alone keeping informations on them.

So technically I have serveral subquestions:

  1. Am I on the right direction thinking in terms of the contriubtion?
  2. Is it still possible to somehow modify Martinez-Rueda-Feito algorithm to achieve what I want?
  3. If not, are there any algorithms that addressed this already, or can be modified in the way I'm thinkg?

Some of the specifications include:

  • The polygons involved may not be convex, but are simple.
  • A typical union would consist of a few dozen polygons.
  • The result could have holes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.