Hi Luke,
Thomas Klimpel wrote:
The mapping to the original coordinates might still be useful, but I think that modifying some of the original coordinates might be OK in cases where the alternative would be to introduce overlapping segments.
I realize after giving the matter more thought that there is not necessarily a 1:1 mapping from fixed point back to floating point coordinates, this makes the idea of a mapping back to floating point less workable. I suppose I could use a multi-map and map back to the centroid of multiple points. I was already aware that converting back to floating point would cause some small movement of line segments which could result in non-reported intersections. These would not be an issue if fed back into my algorithm, but could pose problems for other code. As you point out, there is no way to output the correct topology without ignoring intersections that are artifacts of approximation of the intersection points and there is no way to report those intersections without modifying the output top ology. In some circumstances the output topology is paramount, such as the straight skeleton. In my case I think topology is secondary to the output being free of non-reported intersection s. If I convert fixed point output to floating point coordinates I cannot guarentee either output topology or absence of unreported intersections, as you also observe. Topologically the thing that must be true about the output of my algorithm is that it is closed polygons. That invariant cannot be harmed by introducing vertices as artifacts of snapping, or even by merging vertices that are too close. The other invariant that must be true about my output is that it contains no intersecting line segments. My own code relies upon that invariant, and it is a requirement at the input to all the commercial software we use downstream from my code.
For all that I would recommend that you simply NOT support booleans of floating point polygons at all, and let that one be later on added via an algorithm that considers whatever is appropiate for floats from the ground up. Without any benchmark I would imagine that your integer based solution is faster than, say, CGAL's clipper, which is robust for floating points but uses the floating-point filtering I outlined before, which as I said has some overhead likely higher than yours. Best -- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com