

 Thread Tools  Search this Thread 
#1
 
 
Problem in Polygon Intersection Test 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 ShamosHoey 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. 
#2
 
 
Re: Problem in Polygon Intersection Test 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. 
#3
 
 
Re: Problem in Polygon Intersection Test 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 wingededge 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 wingededge structure was supposed to be modified for the various types of intersection. Eventually I found out about the HalfEdge structure and switching to use it made the transverse intersection (midpointmidpoint) case fairly simple to implement and I was able to get some useful output from the algorithm. 
#4
 
 
Re: Problem in Polygon Intersection Test 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". 
#5
 
 
Re: Problem in Polygon Intersection Test 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. 

Tags: intersection, polygon, problem, test 
Thread Tools  Search this Thread 

Similar Threads for: "Problem in Polygon Intersection Test"  
Thread  Thread Starter  Forum  Replies  Last Post 
Need help to locate point of intersection in two line graph in Excel  Iyyappan  MS Office Support  1  25022012 11:19 AM 
How to use Polygon class?  Fragant  Software Development  5  05032010 10:52 PM 
Intersection of two slots in java  ISAIAH  Software Development  5  17022010 03:33 AM 
Cell intersection lookup in excel  Sayam  Windows Software  3  30072009 10:51 PM 
DNS test fails with dcdiag /test:dns  TEST: Forwarders/Root hints (Forw)  MartinH  Windows Server Help  6  20062006 07:20 PM 