Iphone

Question: After an extensive search and going through alot of material I've had very little 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 tro 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.

Iphone

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.

If you need any further help please do ask but I believe this should easily solve your problem.