Results 1 to 5 of 5

Thread: Problem in Polygon Intersection Test

  1. #1
    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. #2
    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. #3
    Join Date
    May 2008
    Posts
    2,012

    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. #4
    Join Date
    Apr 2008
    Posts
    2,005

    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. #5
    Join Date
    May 2008
    Posts
    2,297

    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.

Similar Threads

  1. Replies: 1
    Last Post: 25-02-2012, 11:19 AM
  2. How to use Polygon class?
    By Fragant in forum Software Development
    Replies: 5
    Last Post: 05-03-2010, 10:52 PM
  3. Intersection of two slots in java
    By ISAIAH in forum Software Development
    Replies: 5
    Last Post: 17-02-2010, 03:33 AM
  4. Cell intersection lookup in excel
    By Sayam in forum Windows Software
    Replies: 3
    Last Post: 30-07-2009, 10:51 PM
  5. Replies: 6
    Last Post: 20-06-2006, 07:20 PM

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Page generated in 1,685,746,954.51777 seconds with 17 queries