Polygon difference - strange results from Clipperlib

Question

I am trying to create iso-area polygons ("donuts") from a set of contours. This is the process:

1. Generate the contours.
2. Sort the contours into a tree structure, such that all contours held within a specific contour are children of that contour.
3. For each contour, execute a difference operation with all of its children, using Clipperlib.

The resulting polygon(s) and holes constitute the iso-area "donut". These iso-areas can then be rendered as a contour map, or used for other purposes. Note that if all I wanted to do was render the contours, I could stop after the initial sort and render the contours in order, such that inner-most render on top. I do require the actual areas.

First up - Clipperlib is a fantastic library, and one that I would be very happy to pay good money for - thanks Angus!

My issue is that I seem to get some strange results from the difference operation in certain situations - I suspect this may be user error on my part, so I will illustrate the problem:

This image shows two polygons - the subject is outlined in red, and the children are filled in blue. I wish to subtract the children from the subject. Note the small area near the mouse-pointer. What I would expect from this diff is two outer polygons - the small one near the mouse pointer and the large one. I would further expect all of the "islands" to be holes within the second, large, polygon.

What I actually get is two outers (as expected), with children (holes) associated with each:

In the second image, the tiny polygon near the mouse pointer is the "outer", and all of the other filled polygons are "holes" belonging to it. Note that I show the outlines of both solutions in both images - just focus on the filled polygons.

I am executing clipperlib using the red polygon in the first image as the subject, and all of the children as clips. Clip type is ctDifference (I have also tried Xor with the same results - which they should be, given that all children are within the subject). I am requesting a PolyTree back, which has two Childs. I am using the c# library, and have also tried v6.

On one level, the results that I need are all there - all of the "holes" are designated such, the problem is that many of these holes are returned as children of the tiny outer area at the top-right of the image. Am I reading the PolyTree incorrectly, using ClipperLib incorrectly, or is this result simply wrong?

On a further note - I noticed that the new ClipperLib (v6) now accepts Z values. I'm wondering now if there may be a better method than I am using for generating these iso-areas from a given collection of un-ordered contour lines?

thanks, Matt

EDIT: I have uploaded the raw data for the polygons in a text file.

here is the link

The file has the subject polygon as the first set of vertices, followed by each of the children. Each polygon is represented as X/Y pairs on a single row, with a newline between each polygon.

Answer 1

In the second image, the tiny polygon near the mouse pointer is the "outer", and all of the other filled polygons are "holes" belonging to it. Note that I show the outlines of both solutions in both images - just focus on the filled polygons.

This sounds like there's a bug somewhere but it's hard to tell without the raw data.

Also, this isn't the best place for Clipper support, there is a discussion forum and a place to report suspected bugs at SourceForge. Anyhow, it's probably best now to post your raw data here (as little as possible please while still reproducing the problem).

Edit:

OK, I've had a look at the data and I don't understand why you believe ... "all of the other filled polygons are "holes" belonging to it".

      PolyTree solutiontree = new PolyTree();
      cpr.Execute(ClipType.ctDifference, solutiontree, 
          PolyFillType.pftNonZero, PolyFillType.pftNonZero);
      solution = new Polygons(solutiontree.ChildCount);
      foreach (PolyNode pn in solutiontree.Childs)
        solution.Add(pn.Contour);

Just filtering the top level PolyNodes of the solution PolyTree (and top level nodes must be 'outers') using the code snippet above, this is what I get (the solution is shaded green) ...

There's no way from this result that "the tiny polygon near the mouse pointer" can own the other polygons. Having said that, there are evidently still holes in the solution so there's a bug somewhere that needs fixing.

Edit 2: I've found and fixed the bug and uploaded Clipper version 6.0.2 to the SourceForge repository. I'll need to do a bit more error checking before I formally update the main Zip package.

Edit 3: Evidently still not right after all.

Edit 4: I think I've finally nailed this bug (see revision 420 in SourceForge repository). Follow up there.