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.

Textbook

What are your input contours? Is it something like a mesh? – Goodoh

The input contours are a series of coordinates that describe closed paths. They are specified in geographic coordinates - WGS84 degrees. They are scaled by 10e7 so that they can be supplied to ClipperLib as integers. – Textbook

Aaaah, now I see. Funny how it all makes sense now. Great to learn about clipperlib, that might come in handy some day.... – Goodoh

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.

Odometer

Thanks Angus - I wasn't sure where to post, as I did a search and SO popped up with a few clipperlib questions. Great library btw. The raw data for this has a thousand or so points in the subject - I'll see if I can create a simple case that reproduces this issue. – Textbook

Link to raw data (in a text file) has been added. I did try (for a little while) to reproduce this problem using simpler polygons, but I could not. – Textbook

OK, I now have the coordinates for 27 polygons, but it's not clear which is/are the subject polygons and which is/are the clipping polygons. – Odometer

Am I right in assuming the first polygon only is the subject and all the rest are the clipping polygons? Sorry, I can now see that you've indicated that in your amended post. – Odometer

Hi Angus, Thanks for taking the time to look at this. I get two outers in my solution, and both of these have holes associated (i.e. two top level nodes in the PolyTree, both of which have children with IsHole==true). Do you get a different result? Edit to add: I have been using pftEvenOdd during the clipping operation. – Textbook

Hi Angus, I've just run it again with a few other fill types, but the results I get are the same: two top level nodes (outers), both of which have children. The first outer has just 7 vertices, and 16 children, whilst the second outer has 8 children. It definitely is the case in my solution that the tiny area near the mouse pointer is being returned as an outer with children.. – Textbook

What version and what language are you using? Anyhow, evidently something is borked in Clipper that needs fixing (which I'm working on slowly). – Odometer

Angus, I am using the c# library, latest version - although I get the same results with the version prior. Seems I get different results to you, although the split of "islands" is the same, as far as I can tell from your image. Thanks for your help - it is much appreciated. – Textbook

OK, I've just uploaded Clipper version 6.0.2 to the repository with the bugfix. – Odometer

Thanks Angus for the prompt update! Above and beyond the call of duty for a free product and most appreciated. – Textbook