Well CWizard, thanks a lot.
But will your method work for convex polygons as well? And how do we split the vertex into two?

"A byte is a large bit to crunch!"

quote:Original post by CuteBug
Well CWizard, thanks a lot.
But will your method work for convex polygons as well?

Yes; any polygon (I think/hope). At least all my test cases have worked.

quote:And how do we split the vertex into two?

As you can see in the example above, the original polygon has 4 vertices and the clipped has 7. Every vertex that is outside the clip rectangle is splitted and then either moved or removed.

A quick summary of the algorithm:

Have a list/vector of the vertices, and have an index to the current vertex.

Each vertex is tested by 4 "clip regions", which represents one of the clip rectangle''s sides. In my paper and above, these are in order: 1) top, 2) bottom, 3) left, 4) right.

If the vertex is inside all of the "clip regions", and thereby the whole clip rectangle, we proceed to the next point by increasing our index to the current vertex.

Otherwise, we split the vertex into two on the same spot. As optimization trick we can remove the vertex instead, if both neighbor vertices are also outside the same "clip region".

1st "sub-vertex": If the previous vertex is outside the "clip region", or at its edge, remove the 1st sub-vertex. Otherwise we move it. This is simple, because we know either the X- or Y-coordinate of the target position, and solve this easily with the line equation.

2st "sub-vertex": If the next vertex is outside the "clip region", or at its edge, we remove this 2nd sub-vertrex. Otherwise we move it.

There are 3 possibles things that could have happened here:
1) both "sub-vertices" were moved,
2) one of them were move and the other removed, or
3) both removed.
In either case we need to restart the (clip region) testing of the current vertex. The current vertex is for case 1; the 1st sub-vertex, for case 2; the remaining sub-vertex, or for case 3 the next vertex.


Just pick out a paper and draw a clip region and a polygon to clip. Then, follow these steps (the ones in the document rather), and you should see how it all works and why.

Ok, I thought I should put up some nice code here, but couldn't figure out a way to get white background for it, and not using [ source ] tags.

Anyway, I made a C++ implementation of this algorithm. It is not optimized and its main purpose is to demonstrate how it works. You, CuteBug, can try to let it operate on one of your polys and see if the result is what you want:

Source, HTML formatted (gd-polyclip-src.cpp.html)
Source, original (gd-polyclip-src.cpp)

DISCLAIMER: Use it at your own risk. I'm not responsible if it causes your computer to blow up or anything.

EDIT: I had misnamed the source file on the server, so it was a 404. Fixed now.

[edited by - CWizard on May 4, 2003 12:43:08 PM]

Thanx a lot,CWizard.

"A byte is a large bit to crunch!"

Please let me know how it works. I did never implement it really before, so I''m not sure about that it works flawlessly, although it seems solid. Note that the code I provided may need some tweaking. For example, it will most likely crash if you have two vertices at the exact same position next to eachother, due to a division by zero.