Polygon overlap tests

The clever way to do it is with a separating plane or axis test. I've never done it in 2d, but I think Dave Eberly has a paper on his Magic Software site somewhere that deals with it in 2d before moving on to 3d. His paper deals with dynamic collision detection between moving polyhedra, but you'll only be concerned with the static case.

Basically, for any two disjoint polyhedra, there will be a plane that separates the two, or an axis on which the projections of the polyhedra are disjoint. It's two ways of looking at the same thing (sort of) - the separating axis is the normal of the plane.

For 3d polyhedra, the axes to be tested are the normals of each face of each polyhedra, and the cross products of each pair or edges - or something like that. In 2d it might just be the normals of the sides, but I'm not sure - you'd have to check.

Anyway, once you've found a separating plane or axis, you know there's no intersection. If you can't find one, you know there is an intersection.

If speed is not an issue then an easy way to approach this problem is to simply test each line segment on polygon A for intersection with each line segment on polygon B. In fact, even if speed was an issue this would probably be fast enough anyhow, and getting the point of intersection is a simple task.
There may occur a situation in which one polygon is conformed entirely within another, and the intersection code thereby misses the overlap. This can be easily resolved by, in the case that the line-segment intersection tests return false, checking if the first point on polygon A is inside polygon B and visa versa. If so then there is of course an overlap.

bool PolyPolyIntersection( Polygon PolyA, Polygon PolyB ){ if( !Poly[ A ].size() || !Poly[ B ].size() ) return false; //Be sure that these polygons actually have verticies on them //Check each segment on polyB for intersection with each segment of PolyB int pA0 = polyA.size() - 1; int pA1 = 0; do { int pB0 = polyB.size() - 1; int pB1 = 0; do { if( SegmentSegmentIntersection( polyA[ pA0 ], polyA[ pA1 ], polyB[ pB0 ], polyB[ pB1 ] ) ) return true; pB0 = pB1; pB1++; } while( pB1 < polyB.size() ); pA0 = pA1; pA1++; } while( pA1 < polyA.size() ); //Determine if one polygon lies entierly within the other if( PointInPoly( polyA[ 0 ], polyB || PointInPoly( polyB[ 0 ], polyA ) return true; return false;}

Note: I just threw this code together then... untested and bugs may be apparent. The code assumes that you are using C++ and STL vectors (or something similar) of 2d points as polygons - this is more-or-less standard but can be changed with relative ease. I am also assuming that you have a SegmentSegmentIntersection function to detect intersection between two 2D line segments and a PointInPoly function to determine if a point lies inside a polygon. I can help you out with either of these if it be needed.

Hope this helps,
Jackson Allan

[Edited by - jack_1313 on June 29, 2004 6:33:40 AM]

I've got a method (that separation axis thing), but it's only for convex polyons. dunno if it suits you.

http://www.gamedev.net/community/forums/topic.asp?topic_id=251638

you can always try to split the polygon into convex parts, or a simple list of triangles, then do the test above.

the simplest is basically to do the edge-crossing-edge check and the vertex-in-polygon check.

if you want to be really smart, with non convex polygons, you can BSP-tree each polygons, and intersect the two BSP trees. You can do operations like.

'or' (giving you the space covered by both polygons)
'nor' (the space not covered by any polygons)
'and' (the space covered by only where the polygons overlap)
'xor' (the space that is covered by only one polygon)
ect...

you can also split the polys into convex parts, and do similar operations like above.

Thanks for your suggestions. The intersecting-lines one seems to be best for my problem; I can't be sure my polygons are convex, since they're user-defined. I'll have a go at the segment-intersection test myself; if I can't get it to work, I'll be back. :)

I'm using code from oliii site in a proof of concept demo - haven't profiled it yet but it works a treat. Includes some docs explaing how it works as well.

Also stumbled across a link to this site on flipcode.

site:
http://www.harveycartel.org/metanet/tutorials.html

flipcode post:
http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00006029&forum=general&id=-1