RectClip versus Intersect with a rectangular path

[chrisdjali-wrld3d]

I'm chopping up complex polygons (i.e. with both positive and negative contours so the region covered has holes) from other Clipper2 operations into several simple polygons (i.e. each is a single positive contour) that I can feed to some existing code. As 1.0.5 was the latest Clipper2 release on Nuget until yesterday, I was doing this by defining two rectangular contours that together contained the whole shape and had a shared edge going through the middle of a hole, and calling the Intersect function, which would give me two chunks of the original polygon, so as the hole in question (and any others that happened to be split) was on the outer contour of the new shapes, it would be represented by a dent in these contours rather than a negative contour. This worked great for all the data I've needed it to work on so far.

Now Clipper2 1.1.1 is on Nuget, though, I've tried using RectClip instead as it's faster. However, unlike Intersect, when a former hole ends up on the new outer perimeter, it's still represented by a negative contour rather than a baked-in dent. I imagine this might be intended behaviour and part of why RectClip is faster, and I could work around it by passing the result to another Clipper2 function (which would presumably negate the speedup), but wanted to check it was expected behaviour rather than a bug before giving up on this optimisation and using my existing code.

[AngusJohnson]

Hi again Chris.

imagine this might be intended behaviour and part of why RectClip is faster,

Certainly part of why it's faster, but not so much intended behaviour but something I hadn't considered 😱.

and I could work around it by passing the result to another Clipper2 function (which would presumably negate the speedup),

Yes, I would expect so (unless the rectangular clip window is much smaller that the subject bounds).

but wanted to check it was expected behaviour rather than a bug

It's not really a bug, but something that I'll need to give quite a bit more thought.

before giving up on this optimisation and using my existing code.

That may be best for the time being.

[AngusJohnson]

PS: The results from RectClip are still accurate, they're just no in their simplest forms:

    public static void Test()
    {
      Paths64 subject = new Paths64(), solution;
      subject.Add(Clipper.MakePath(new int[] { 10, 10, 100, 10, 100, 100, 10, 100 }));
      subject.Add(Clipper.MakePath(new int[] { 0, 30, 0, 70, 50, 70, 50, 30 }));
      Rect64 rect = new Rect64(20, 20, 80, 80);
      solution = Clipper.RectClip(rect, subject);

      SvgWriter svg = new SvgWriter();
      SvgUtils.AddSubject(svg, subject);
      SvgUtils.AddSolution(svg, solution, false);
      svg.SaveToFile("tmp.svg", 200, 200);
      ClipperFileIO.OpenFileWithDefaultApp("tmp.svg");
    }

    public static void Test2()
    {
      Paths64 subject = new Paths64(), solution;
      subject.Add(Clipper.MakePath(new int[] { 10, 10, 100, 10, 100, 100, 10, 100 }));
      subject.Add(Clipper.MakePath(new int[] { 0, 0, 0, 60, 60, 60, 60, 0 }));
      Rect64 rect = new Rect64(20, 20, 80, 80);
      solution = Clipper.RectClip(rect, subject);

      SvgWriter svg = new SvgWriter();
      SvgUtils.AddSubject(svg, subject);
      SvgUtils.AddSolution(svg, solution, false);
      svg.SaveToFile("tmp2.svg", 200, 200);
      ClipperFileIO.OpenFileWithDefaultApp("tmp2.svg");
    }

Having said that, I do hope to improve that. (No timeframe but possibly in the next week or two). I'm pretty confident I'll have a much better solution in a day or two.

[AngusJohnson]

Well that day or two (I suggested above) turned out to be a week or two, and the new code is still unpublished 😱😁. But I do now have a Delphi version of RectClip that will produce much simpler clipping results. (More on that in a minute.)

However, it's important to note that RectClip is completely fill rule agnostic. So it can't know which paths are holes or otherwise. It simply follows individual paths, and trims anything that's outside the clipping rectangle. But in doing so, clipping solutions will retain the winding directions of the input polygons. (I guess I could create a modified RectClip that clipped everything inside the rectangle - a NegativeRectClip - but I wonder how widely useful that would be.)

Nevertheless, currently RectClip solutions can be downright ugly, though still strictly correct.

And this is because the current algorithm simply tracks any paths outside the clipping rectangle and truncates them to the rectangle. (That's why there can be quite a few overlapping lines along the clipping rectangle.)

The new code however will tidy up (ie remove) these overlapping edges on the clipping boundary and convert single polygons into multiple polygons.

But some overlapping edges can't be tidied up. Collinear edges heading in the same direction can't be split and rejoined without reversing the direction of one of the edges, and this would violate the guarantee that paths will retain their input winding states.

I hope to provide more detail on this once I've translated the Delphi code to C++ and C# and uploaded it here.

[gigglesun]

@AngusJohnson I was trying to figure out the algo used in rect clip, is here any reference doc I could refer to, thanks.

[AngusJohnson]

I was trying to figure out the algo used in rect clip, is here any reference doc I could refer to, thanks.

Sorry, there are no reference docs (yet) and the algorithm is entirely my own work.