Well, I did a bit more on the 3D modeling stuff.
I found an interesting general polygon clipper library. So I figured it would do as an interim step until I made my own. I re-coded everything to use it, and then banged my head against the wall a lot. I then used svn to rewind everything about 5 hours...
Basically it is quite a nice library. It seems to work. It has a good simple interface.
However, looking at it, it seems complicated. It seems to classify each vertex in one of 16 different ways and have code for handling each. That seems wrong to me - the algorithm should be simpler and neater than that. It just feels wrong.
So I slept on it and worked out how the logic should - I think.
Step 1: Find mid-line intersections and create new point
Step 2: Find points that intersect
This comes out of the finding crossing lines basically. Each endpoint that intersects will be part of two joined segments, one or more times.
Step 3: Work out if the intersecting endpoints cross
This can be done with angles. Imagine AXB and CXD are the possibly crossed lines, X is the point they cross. So it appears in line segments AX then XB, and CX then DX. You can look at the angles of each of the four points (A, B, C, D) around X and work out if the paths cross.
Thankfully you don't need real angles for this (slow atan logic) you just need something you can compare, and that can be done by calculating the relative position of B, C and D relative to AB using multiplication and division only so nice and quick.
Step 4: Uncross them
The end result means turning crossed over polygons in to a set of simple polygons that do not cross. You need data structures such that you can easily splice lists of points, and can mop up loops you create and would be left over. That is not too hard to do.
Step 5: Winding number
Then work out if each path is clockwise or anti -clockwise and the winding number. I think the logic here is the winding number on your right as you traverse the path, (so the winding number of the inside of a clockwise path, or outside of an anti-clockwise path) which means a clockwise path and an anti-clockwise hole within it have the same winding number and so stay together when we do Boolean operations (see below). Winding number is not too hard to work out especially knowing the paths no longer intersect.
Step 6: Boolean maths
So, the plan is to make a new polygon library of my own. I am making it as a general purpose library and will probably open source it.