Polygon to Polygon Collision Detection Issue

Question

Hey guys,

I have been having a few issues implementing my narrow phase collision detection. Broadphase is working perfectly.

I have a group of polygons, that have a stl::vector array of points for their vertices in clockwise order. Every cycle, I check to see whether they're colliding.

I have borrowed the following Point in Polygon test from here and changed it using my Point data structures:

int InsidePolygon(std::vector <Point> poly, Point p) {
  int i, j, c = 0;
  int nvert = poly.size();

  for (i = 0, j = nvert-1; i < nvert; j = i++) {

    if ( ((poly[i].y> p.y) != (poly[j].y> p.y)) && (p.x < (poly[j].x-poly[i].x) * (p.y-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) )
       c = !c;

  }
  return c;
}

I have extended that to include a PolygonPolygon function, which check all the points of 1 polygon against another and then reverse it to check the other way around.

int PolygonPolygon(std::vector <Point> polygon1, std::vector <Point> polygon2) {

    for(int i=0; i<polygon1.size();i++) {    
     if(InsidePolygon(polygon2, polygon1[i])) {
         return 1;
     }
    }
    for(int j=0; j<polygon2.size();j++) {       
     if(InsidePolygon(polygon1, polygon2[j])) {
         return 1;
     }
    }

  return 0;

}

The strange thing is that my PolygonPolygon function is always returning 1. So I have a few questions:

1. Have I screwed up the logic somewhere? Should I write my PolygonPolygon function differently?

2. Are there any better methods for a PolygonPolygon test, the polygons themselves are not guaranteed to be convex, which is why I went for the point in polygon method. I also hope to determine which point is colliding eventually, if I can get past this bit.

3. Should I be presenting my points in a particular order for the InsidePolygon test?

Answer 1

You may want to consider trying to draw a line between polygons as an alternative collision detection method.

[edit] Oops, I missed the fact that you have non-convex polys in there too. Maybe "Determining if a point lies on the interior of a polygon" would be better? Either that or you could break your non-convex polygons up into convex polygons first.

Also, there's at least one similar question here on StackOverflow.

Answer 2

Thanks for your help guys! But i've managed to sort it out on my own.

The importance of translating your vertices to world space and rotating them should not be overlooked, especially if you're colliding them.