ClipperOffset.Execute returns Polytree

[frankbielig]

Clipper1 provides an offset interface where you directly get a Polytree as result. This interface is unfortunately omitted in Clipper2:

void Execute(Paths& solution, double delta);
void Execute(PolyTree& polytree, double delta);

-->

Paths Execute(double delta);

Of course, you can make a Polytree out of the path again. However, this detour is significantly slower than the direct path in Clipper1. The necessary information is certainly already available within the offset operation.

Request: Add a new function to get a Polytree from the offset operation. Alternatively, the current function could be replaced, since a Polytree can be easily converted with PolyTreeToPaths.

[AngusJohnson]

Hi again Frank.

Firstly, I've converted this to a Discussion since I don't consider this an Issue WRT Clipper2.

Yes, I could fairly easily reimplement Polytrees for offsetting too.
I took this out of Clipper2 as I couldn't envisage why anyone would need this (and I'm also keen to keep the library as simple as possible).
Perhaps you could explain why this would be useful to you?

Alternatively, the current function could be replaced, since a Polytree can be easily converted with PolyTreeToPaths.

No, that's not a good idea as it would unnecessarily slow the op for everyone else.

[sethhillbrand]

Well, I can't speak for @frankbielig but we use this function in KiCad (https://gitlab.com/kicad/code/kicad/-/blob/master/libs/kimath/src/geometry/shape_poly_set.cpp#L1070) and need to build the PolyTree in order to have the holes assigned to the correct outlines after processing. We currently just deal with the extra processing time but if there's a way to have the original interface present in Clipper2, we would definitely use that.

[frankbielig]

@sethhillbrand , this is our use case as well. We have also implemented the work-around with extra costs.

[mmassing]

Same here!

[AngusJohnson]

Try this ...
Clipper2Lib.zip

[frankbielig]

In our application, this function runs more than 3 times faster in Clipper1 than in Clipper2. No pressure ;)

[AngusJohnson]

In our application, this function runs more than 3 times faster in Clipper1 than in Clipper2. No pressure ;)

I'll investigate 😉.
It would help if you gave me some data, or at least some idea of the kinds of shapes you're offsetting, and whether you're rounding joins or squaring etc.

The only thing I can think of that's likely to be slower is squared joins. And that's because in Clipper1 the squaring wasn't occurring at delta distance, just a rough approximation of that distance.

[AngusJohnson]

In our application, this function runs more than 3 times faster in Clipper1 than in Clipper2. No pressure ;)

Yep, I found the problem. I was wasting a heap of time recalculating step_sin and step_cos.
I'll upload the fix shortly (together with a few other fixes).

Edit: I've just done some time tests and the differences are way less than a factor of 3, so perhaps it's something else after all.
Nevertheless this still provides a modest improvement.

[frankbielig]

We will check you latest changes as soon as they are available. We really appreciate your dedication to us!

[AngusJohnson]

We will check you latest changes as soon as they are available.

These latest changes are already available in a zip package, see my post below for the link. It'll take me a little while to migrate to C# and Delphi, so the formal repository update will take a little while longer.

[AngusJohnson]

This library extension generally works. But it does not show the expected performance increase. It looks like you are doing the same thing internally that we are doing outside. There was hope for performance improvement by reusing some of your internal structures.

I presume you're doing (ie re-doing) a Union op on the offset solution.
If so, then I'm at least saving you that time expense because ClipperOffset always does a Union op internally (ie regardless of a need or otherwise for a Polytree). The internal Union tidies up all intersections at concavities etc.

[frankbielig]

You're right. We are doing a Union operation on top. At least this part we can really skip then. That's great.

[AngusJohnson]

In our application, this function runs more than 3 times faster in Clipper1 than in Clipper2. No pressure ;)

I've attached the source code for a simple Clipper1 - Clipper2 Offset comparison utility. This also contains the latest unpublished changes to the library

And the results:

Clipper 1 tests
Clipper1 - round
155 millisecs
Clipper1 - miter
6.16 millisecs
Clipper1 - square
72.7 millisecs

Clipper 2 tests
Clipper2 - round
106 millisecs
Clipper2 - miter
4.86 millisecs
Clipper2 - square
5.51 millisecs

(Edit: the timings for round above improve dramatically when using SomplifyPaths in the loop.)

Here's the zip package:
clipper_compare.zip

[AngusJohnson]

I've now uploaded into the repository the changes mentioned above.