Naxos's last proposed algorithm (which I affectionately named Naxos2) works just fine with two simple additions:
1) If the intersection hits an existing vertex, do not add a new point.
2) The polygon must remain rectilinear at all times. The important part of that definition here is that "useless" vertices, ones that lie in between two other vertices, must be removed.
(1)------(2)-------(3) | | | | | | (5)----------------(4)I.E., vertex 2 needs to be removed in this example because it lies on the line segment between vert 1 and vert 3.
You could probably create some logic to detect and remove these useless verts when they are created, but I simply scan the entire polygon every time a rectangle is "clipped" from it.
Much thanks to Naxos!
-Dave
