Clipping 2 Polygons

[woodie2]

Hello I have 2 polygons:

I want to clipp it eachother to get 3 single polygons without any overlaps.

First I do a intersection of both:

after that I use the intersection part as clip object for the both polygons to get that:

but clipper gives me instead the whole yellow polygon and as hole the intersection part (clip item), why clipper doesn't cut that part off?

[rs0xFFFF]

Code?
Wrong clip operation?

[woodie2]

 var
  ASubject
  AClip,
  ASolution1,
  ASolution2,
  ASolution3       : TPaths64;
  AClipper64   : TClipper64;
begin

ASubject :=
((59902588, 43229077), (59906591, 43224910), (59907532, 43224684), (59908106, 43224590), (59905090, 43227740), (59903719, 43229140), (59903181, 43229693))

AClip :=
((59896761, 43235524), (59897111, 43232823), (59897365, 43231002), (59897660, 43228983), (59897942, 43227057), (59898382, 43227032), (59899120, 43226996), (59899912, 43226903), (59899942, 43226875), (59900039, 43226875), (59900099, 43226874), (59900393, 43226822), (59900780, 43226685), (59900901, 43226660), (59902078, 43226137), (59903707, 43225489), (59904359, 43225340), (59904491, 43225391), (59904588, 43225458), (59904619, 43225500), (59905104, 43226135), (59905939, 43227185), (59906367, 43227698), (59905730, 43228342), (59905610, 43228464), (59904829, 43229258), (59904495, 43229324), (59904490, 43229325), (59904481, 43229327), (59904472, 43229330), (59904464, 43229333), (59904457, 43229336), (59904441, 43229344), (59904435, 43229348), (59904428, 43229352), (59904416, 43229360), (59904411, 43229365), (59904406, 43229369), (59904401, 43229375), (59904397, 43229380), (59904388, 43229389), (59904384, 43229394), (59904381, 43229398), (59904378, 43229403), (59904375, 43229407), (59904372, 43229412), (59904368, 43229417), (59904366, 43229424), (59904363, 43229429), (59904361, 43229435), (59904358, 43229441), (59904356, 43229447), (59904354, 43229454), (59904352, 43229462), (59904350, 43229469), (59904348, 43229477), (59904347, 43229484), (59904347, 43229492), (59904346, 43229501), (59904346, 43229510), (59904347, 43229518), (59904348, 43229528), (59904349, 43229537), (59904350, 43229542), (59904370, 43229656), (59904354, 43229739), (59903896, 43230204), (59903575, 43230533), (59903183, 43230932), (59902981, 43231140), (59902482, 43231650), (59901647, 43232504), (59901487, 43232672), (59900608, 43233588), (59900223, 43233990), (59900223, 43233905), (59899922, 43234094), (59899763, 43234337), (59899749, 43234408), (59899797, 43234435), (59899652, 43234590), (59899360, 43234898), (59898796, 43235469), (59898332, 43235701), (59898090, 43235784), (59897686, 43235712))

AClipper64 := TClipper64.Create;
  try
    AClipper64.AddSubject(ASubject);
    AClipper64.AddClip(AClip);
    AClipper64.Execute(ctIntersection, frEvenOdd, ASolution1);
    AClipper64.Clear;

    AClipper64.AddSubject(ASubject);
    AClipper64.AddClip(ASolution1);
    AClipper64.Execute(ctDifference, frEvenOdd, ASolution2);
    AClipper64.Clear;

    AClipper64.AddSubject(AClip);
    AClipper64.AddClip(ASolution1);
    AClipper64.Execute(ctDifference, frEvenOdd, ASolution3);
    AClipper64.Clear;
  finally
    FreeAndNil(AClipper64);
  end;
end

ASolution3 has after that, the AClip Path and the ASolution1 Path as Hole, instead a difference of AClip and ASolution1

[alexisnaveros]

@AngusJohnson I think that case is worth your attention... My understanding is that the intersection of both shapes causes rounding of the intersection points to be "above left" of the actual edge of the yellow shape. Then subtracting that intersection shape is found not to intersect the bottom-right yellow edge, and therefore it's considered a hole, but that's a hole bounded by a wall with a thickness probably less than 1 (unless the removal of round() caused that wall thickness to be 1.5-ish).

Shouldn't a "wall", between a hole and the outer space, with a thickness less than 1 be removed? Since it's below the numerical accuracy tracked by the code.

Woodie2 could change his code to compute the intersection C between A and B, but then subtract B from A, and A from B... but then I would be concerned, is it guaranteed that the 3 outputs would share the exact same vertices where the intersection happens? If not, then the 3 shapes might still overlap or leave a gap.

[AngusJohnson]

Shouldn't a "wall", between a hole and the outer space, with a thickness less than 1 be removed? Since it's below the numerical accuracy tracked by the code.

• A lot of effort has gone into returning solutions close to their simplest forms, but there's no way to do this perfectly without significantly degrading performance. So there will, on occasions, be solutions with touching polygons. If solutions aren't sufficiently simple, then a subsequent union operation will bring these solutions very close to their simplest forms.

http://www.angusj.com/clipper2/Docs/Overview.htm#closed_paths

Unfortunately, a followup Union does not remove the hole in this instance.

[alexisnaveros]

Yeah, that makes sense... It's the kind of glitches I repair in post-processing after a Delaunay triangulation, and it's a complicated mess.

@woodie2 Compute the intersection C from A and B, but then don't subtract C from A or B. Rather, subtract A from B, and B from A. That should fix the issue, without glitches.

[woodie2]

Compute the intersection C from A and B, but then don't subtract C from A or B. Rather, subtract A from B, and B from A. That should fix the issue, without glitches.

Yes in that simply example it can be a solution to subtract A from B, and B from A. but I need a general solution that always works.

[AngusJohnson]

    AClipper64.AddSubject(ASubject);
    AClipper64.AddClip(AClip);
    AClipper64.Execute(ctIntersection, frEvenOdd, ASolution1);
    AClipper64.Clear;

    AClipper64.AddSubject(ASubject);
    AClipper64.AddClip(ASolution1);
    AClipper64.Execute(ctDifference, frEvenOdd, ASolution2);
    AClipper64.Clear;

I don't understand the purpose of the ops above.
Surely the following op is much simpler for the same result ...

    AClipper64.AddSubject(Aclip);
    AClipper64.AddClip(ASubject);
    AClipper64.Execute(ctDifference, frEvenOdd, ASolution2);

And I don't understand the purpose of the follow op either.
Isn't it just the Union of ASubject and AClip?

    AClipper64.AddSubject(AClip);
    AClipper64.AddClip(ASolution1);
    AClipper64.Execute(ctDifference, frEvenOdd, ASolution3);

[woodie2]

Yet another example of the problem.
We have 4 rectangles that are to be intersected.

It shouldn't matter which 2 rectangles we start with, so it's not a solution as it is, we start with this and that.

We'll start with the blue and orange. subtract blue from orange, and orange from blue and the intersection part.

so far everything is fine and works as expected.
we write back the 5 rectangles and erase the blue and orange origins.

Now we start again and take the green rectangle and an orange one.

Again subtract green from orange, and orange from green and the intersection part.
Normally we would now expect to get a green polygon and an intersection part, like that (right one):

but we get the full green rectangles and the orange one as hole of them, not the expected green polygon.

as a solution, you could enlarge the orange rectangle a little beforehand so that it goes over the edge of the green one, but that's not a good solution. Clippper should recognize parallel edge that are very close together as intersections.

[alexisnaveros]

Can you try what I suggested above?

Compute the intersection C from A and B, but then don't subtract C from A or B. Rather, subtract A from B, and B from A. That should fix the issue, without glitches.

I agree that a "wall" that is extremely thin, under the numerical accuracy of the code (thickness < 1.0), should be removed. Though I can see why that's kind of complicated in practice, even in post-processing. The solution just above should work though. Don't subtract from your shapes any computed difference, always subtract whole original input shapes.

[woodie2]

I did your Suggestion. blue A and orange B subtract each from another.
but after that I don't have the orange and blue rectangles anymore. I'll replace them with the 5 newly created ones. I can see that Clipper cannot solve this at the moment. I hope that it will soon be possible to recognize and correctly handle parallel search edges.

[alexisnaveros]

Yes well, you'll have to adjust your code to keep all the original input shapes until you are done processing all shapes. That shouldn't be a problem.

[woodie2]

It is not a problem in itself, only that it takes an unnecessarily long time with many hundreds of polygons. In addition, I would end up with a lot of identical polygons and would then have to test them to remove all duplicates.

[alexisnaveros]

Yeah, processing time will be pretty awful...

If that's a serious problem, it would be possible to change the code to do all of it in one pass, much more efficiently, but it's not easy. Each input shape would be assigned an unique ID, all regions would track the list of unique IDs they belong to (rather than just a winding count), and it would output multiple shapes, one shape for each unique list of IDs.

Let me know if you intend to do that.