Simonson, Lucanus J wrote:
My main concern isn't whether the scanline is maintained properly, it is whether spurious intersections are introduced when snapping an intersection point to the floating point coordinate grid. Because snapping moves the edge laterally by some small ammount it may cause it to cross to the other side of a vertex than the original segment, leading to the invariant that all output segments are non-intersecting and touch only at their end points being violated, which breaks downstream code.
Let me see if I understand this correctly. Say you have two line segments AB and CD that cross at E: A D \ / \ /F \ / E / \ / \ C B Due to the floating point approximation, C-E-D is not perfectly straight and there is some other vertex F which lies one one side of CD but the other side of ED. This can also happen with integer co-ordinates, but it's easier to reason about in that case. Right? It seems to me that the fix must be to forget about C-D as soon as E has been found, and only use the new edges CE and ED from then on. If this is true, what are the implications for the interfaces to the algorithms that do this? Does it mean that if I have: polygon P; polygon Q; polygon R = intersection(P,Q); then intersection() should be allowed to modify P and Q to add new points? Otherwise, we may end up with points that are inside R but not inside P or Q. Thinking about it from the application requirements point of view it may be acceptable to have algorithms that are guaranteed to err one way and not the other, e.g. union1(A,B) contains every point in A and B and perhaps some extra ones union2(A,B) contains most points from A and B and no points not in A or B I would like to think that this has all been considered many timed before.... Phil.