Printable View
hi there
After a massive search and going through more material I had no success. I have the verticies of two simple polygons (which can be convex) and I wish to do a test to see whether the two polygons intersect (i.e return a boolean value). I've looked at the Shamos-Hoey Algorithm and had no luck understanding it - I'm trying to implement this in transact SQL but any c++ or java code (pref Java) which I can look at to better get a grip of the concept would be much appreciated.
I guess I should expand a bit... The way you detect collision between complex polygons and meshes is splitting the polygon into smaller triangles. Any shape can be split into triangles about an arbitrary center point if need be. (Or they can just be partioned off individual triangles from points, either way works) Then you can use those triangles and detect for intersection with other shapes on the same plane or intersecting planes. The thing you would do with Thomas Moller's algorithm is exculde calculation of intersection from a single triangle in the polygon in question with the other triangles from that shape. This would leave you with a tree structure or linked list of triangles in your complex polygon. Thus do not parse that linked list that the item you are currently calcuating is from.
You can further optimize this algorithm by only calculating intersection with outer triangles because with complex concave polygons you might end up with internal triangles. These need not be calcualted.
The only algorithm I found on the web was the one described by Kevin Weiler
in "Polygon Comparison using a Graph Representation" published in SIGGRAPH
1980. This algorithm uses a winged-edge data structure and handles all the
cases I wanted and more. Unfortunately I don't really have a background in
computational geometry and I tried without success to find on the web and in various text books the way in which the winged-edge structure was supposed to be modified for the various types of intersection. Eventually I found out about the Half-Edge structure and switching to use it made the
transverse intersection (midpoint-midpoint) case fairly simple to implement
and I was able to get some useful output from the algorithm.
If your polygons have a huge number of triangles, you might be able to space partition them. If they don't, I wouldn't worry about it and just test against every triangle. Calling a function "several times per frame" generally isn't a concern unless that function is astronomically slow... or if by "several" you mean "several thousand".
Break it into convex polygons and do a SAT test. If you don't need a collision point or normal and your geometry is rigid, this is really easy and relatively fast.