A TARDIS does not break it, and neither does a DALEK. Sadly I can still break it with my coffee machine hopper extension - so some bug still lingering. However, it is usable now... I'll publish it when I have the last bug found :-)
Now, why was it so hard?
1. Odd/even vs winding number.
Getting the original design right was tricky. What should it actually do? Even when you know you want a polygon library you do not necessarily know what the spec is. The main issue is how you handle holes. Basically, there are two approaches - something one can see in the postscript language even. If you walk from infinity over the shape, you can consider each line you meet as an edge, i.e. inside, outside, inside, outside, etc... This is odd/even logic. In this case the direction of each line is unimportant. Alternatively you can have a counter, starting at zero, and count each line you passed which is going to your left is plus one and each line going to your right is minus one. When the counter is non zero you are inside. This second approach is winding number logic. To me it seems much more logical so that is what I went for.
However, even with winding number logic you have to think. I just said any non-zero is inside, which is what postscript does. But what happens if you do something to a shale that makes it self intersect or even turn inside out.
Above is an example of a simple shape. A is what you started with. B is inset a bit. C is inset more - see how part of the shape has turned inside out. D is what you wanted - the inside out bit removed. To fix this you do winding number logic but only consider positive number as inside. Negative winding number are thrown away.
In fact the whole logic for basic intersect and union type operation works well with winding number. Union is just keeping all winding number 1 or above. Intersect is keeping winding number 2 or above. You can use it on one polygon to clean up things like this going inside out issue. You could use on more than two polygons at once even.
So, this makes winding number definitely the right way to do it. Else you have lots of other problems to sort out. This is, I believe, the key difference to the general clipper library that I looked at originally. Interestingly Cliff's idea at the beer festival was to have a separate function to simplify each polygon and then have Boolean operation functions which work on two polygons that you know are cleaned up like this. That would work, of course, but is a totally different approach.
2. Floating point numbers.
I coded this all with a typedef for the co-ordinate system, so I could change later. I just knew floats would bite me, but given machines have floating point hardware I thought I would try. Yes, as expected it bit me. Whilst comparison of floats was not the issue as such, there were problems where line intersection logic would happily decide to slice 10^-18mm off a line repeatedly. I am sure it would have finished eventually, but was due to the unit steps of floats and in particular the fact the two floats can have different intervals as different magnitudes. In the end, I simply changed to 64 bit integer which for my 3D stuff I am doing as micrometres. That also made it a lot faster as it happens.
3. Intersection logic.
One issue I then seem to have is that when you break a line because you have decided it intersects another line, you change it. This is made worse in some ways by use of integer maths. Basically, the break point is not going to be exactly on the line - it will be the nearest whole co-ordinate. This should not be an issue as obviously both ends move to the same point. The problem is that intersections you have already checked (off to the left) may change because the angle of the line you have just split has changed. An obscure edge case, but it happened. It meant that the segments needed re-checking as you could end up with self intersecting results. I initially solved most of these simply by making sure the X/Y intersect point was rounded to nearest whole number, not just truncated, but even then it still breaks with some shapes (not surprised). Now I just run the intersect checking code again until no more line segments are chopped up. That got pretty much everything working. I am trying to see if I can improve that.
4. Final bug
Well, I still have one test case breaking it - I need to figure that out. It is clearly even more of an edge case as quite complex shapes (like TARDIS and DALEK) are just working now. Should be easy to track down I am sure.
However, now I can actually get the output, I can continue on the original challenge - new 3D libraries. I can see my inset algorithm is breaking with some shapes so that needs fixing. Then I have new challenges with working out the extrude path and filling over open space, and all sort... But that should be fun, and a lot easier with a working polygon library...
I wanted to improve our doorbell... Yes, that is dull. But the main change is not the bell (a nice, old style bell in the kitchen, which is ...
Broadband services are a wonderful innovation of our time, using multiple frequency bands (hence the name) to carry signals over wires (us...
For many years I used a small stand-alone air-conditioning unit in my study (the box room in the house) and I even had a hole in the wall fo...
It seems there is something of a standard test string for anti virus ( wikipedia has more on this). The idea is that systems that look fo...