Operations on polygons

OK, after a chat with Cliff I have taken a step back.

The idea I had at the top level was (a) simplify the polygons to non overlapping simple contours, (b) work out how they are nested, (c) cut out the ones I want.

The main reason for that logic is that the final stage allows a variety of operations such as union, intersection, difference and so on, very simply. I had assumed the second stage of finding the nesting would be easy (and quick).

I now find that working out which polygon is inside which is complex in the sense you have to walk around the edge to find where they diverge. This is not very efficient. The first stage was fun as well as it meant working our how the overlaps worked, and multiple overlaps, so as to ensure creating simple polygons even when lots intersected at a point.

So, thinking about it from scratch, I realise how the general clipping library probably does it. They take an operation as part of the clipping logic (the first stage). The problem I have is they did not seem to care which way around the input polygons went and only seem to use an odd/even logic where I want proper winding number logic.

Even so, the way to do it is to take the ordered list of line segments and process them. It is a sweep over the polygons left to right. In doing so you may well encounter multiple line segments, one top of each other. The nice thing is you do not care which segment is from which polygon - they are just edges that you are encountering. I do care what direction they are going, but that just affects the way you count them. Basically you know if they represent an edge you are interested in or not by how they move the winding number as you pass them. If looking for an intersection, for example, you are looking for winding number crossing 2, so it matters not if they go from 0 to 10 in one go (lots of polygons on top of each other), that means put just one line there as the edge of your intersection. For union you look for the edge on winding number 1.

It solves the issue of working out which polygon is inside which. As you sweep you create the new set of polygons from the output. You actually have a set of fragments that you add line segments to either end of and they end up closing neatly. This works well for union or intersection. For difference you need to reverse the layer 2 that you find to make it a hole but still, at each line segment, you only make one line to add to your output. I suspect vertical lines on the horizontal sweep need some additional care, but still, not that complex.

It also works to simplify a single, possibly self intersecting, polygon by doing a union on it.

I'll ponder that design as a new approach. Shame, as I liked the general idea with the winding rule type logic. However, this is a better approach for overall speed and reliable output.

Thanks for asking the questions, Cliff. I was too deep in my idea of finding the nesting level to take a step back.