TechArena Community Problem in Polygon Intersection Test
 User Name Remember Me? Password

#1
26-02-2009
 Member Join Date: Jan 2009 Posts: 69
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 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.
#2
26-02-2009
 Member Join Date: Apr 2008 Posts: 1,948
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
26-02-2009
 Member Join Date: May 2008 Posts: 2,008
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 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.
#4
26-02-2009
 Member Join Date: Apr 2008 Posts: 2,001
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
26-02-2009
 Member Join Date: May 2008 Posts: 2,293
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:

 Thread Tools Search this Thread Search this Thread: Advanced Search

 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 25-02-2012 11:19 AM How to use Polygon class? Fragant Software Development 5 05-03-2010 10:52 PM Intersection of two slots in java ISAIAH Software Development 5 17-02-2010 03:33 AM Cell intersection lookup in excel Sayam Windows Software 3 30-07-2009 10:51 PM DNS test fails with dcdiag /test:dns - TEST: Forwarders/Root hints (Forw) MartinH Windows Server Help 6 20-06-2006 07:20 PM

All times are GMT +5.5. The time now is 09:38 PM.

 Contact Us - TechArena - Privacy Statement - Terms of Service - SiteMap