Reuse of large clip polygons

[frankbielig]

Hi Angus,

I really appreciate your dedication to this library. It does a very good job in many areas. Especially for small and medium clip tasks it is unbeatable.

However, there is a use case where there are very large clip polygons which needs to be applied to very many small and medium polygons. It turns out that adding the clipping polygons takes a disproportionate amount of time compared to the actual clipping task.

Ideally, I would like to be able to reuse the Clipper object with the large clipping polygons added. In Geos, for example, there is PreparedGeometry for such use cases.

It doesn't have to be that complicated. It would be helpful if you could create a copy of a Clipper object in the assumption that it is faster than the construction over the polygons themselves. Alternatively, the ability to remove objects to be clipped in whatever form might help.

What's your take on this feature? Do you see any other way to optimize the use-case described above?

[AngusJohnson]

Hi again Frank.
I think I understand what you're after ... and that's creating reusable paths that have been converted into the structure (or structures) that's internal to Clipper64. (Something like a ReusableInternalClipperPath64 that can be assigned to Clipper64 objects.)
This is certainly very possible, and it may offer some performance improvement, but how much remains to be seen with testing.
I'll look at this over the next week or so and get back to you here, hopefully with some test code.

[AngusJohnson]

Hi Frank.
I've just finished a first draft of this (see attached below).
Basic usage:

  Paths64 subject, clip, solution;
  subject.push_back(MakePath({ ...... }));
  subject.push_back(MakePath({ ...... }));
  subject.push_back(MakePath({ ...... }));
  subject.push_back(MakePath({ ...... }));

  ReuseableDataContainer64 stored_subjects;
  stored_subjects.AddPaths(subject, PathType::Subject, false);

  clip.push_back(MakePath({ ...... }));

  Clipper64 c;
  c.AddReuseableData(stored_subjects);
  c.AddClip(clip);
  c.Execute(ClipType::Intersection, FillRule::NonZero, solution);

  Paths64 clip2, solution2;
  clip2.push_back(MakePath({ ...... }));

  Clipper64 c2;
  c2.AddReuseableData(stored_subjects);
  c2.AddClip(clip2);
  c2.Execute(ClipType::Intersection, FillRule::NonZero, solution);

Clipper2Lib.zip

[AngusJohnson]

However, there is a use case where there are very large clip polygons which needs to be applied to very many small and medium polygons. It turns out that adding the clipping polygons takes a disproportionate amount of time compared to the actual clipping task.

I've just done some performance tests and this new ReuseableDataContainer64 class and Clipper64.AddReuseableData() method is a little over 50% faster than Clipper64.AddClip or Clipper64.AddSubject. But generally this will make very little difference to overall clipping performance since Clipper64.Execute is vastly more time costly. However, if you're reusing the same clip or subject paths in hundreds or thousands of clipping operations then in that case I expect the performance gains to be significant.

Edit: And of course, there'd be a lot of benefit in pre-"unioning" this reuseable data, if there's significant overlap.

[frankbielig]

Thank you for the updates. I'll try it in next couple of days. Your measurements are already very encouraging

[frankbielig]

The API extensions you brought bring an average of 10% runtime improvements in our use cases. That is already very good. Therefore I plead for these changes to be included in the next release.

[frankbielig]

However, we still have cases where Clipper2 is significantly slower than Clipper1. We are not talking about a few percent but about multiples. We are still trying to find out which special properties lead to this difference.
On the other hand, version 2 is very often faster than version 1, just like you said.

[AngusJohnson]

The API extensions you brought bring an average of 10% runtime improvements in our use cases. That is already very good. Therefore I plead for these changes to be included in the next release.

Yes, I will include these changes.

However, we still have cases where Clipper2 is significantly slower than Clipper1.

I'm certainly very interested in examples and finding out why.