Polygon to Polygon Collision Detection Issue

Question

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:

Have I screwed up the logic somewhere? Should I write my PolygonPolygon function differently?
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.
Should I be presenting my points in a particular order for the InsidePolygon test?

your test of point inside polygon will not detect a polygon overlap which has no points inside either polygon (think two triangles arranged like star of david). you could test each edge of one polygons intersection with each edge of the other polygon as well to be sure I think. but sounds like that is getting expensive... — Sam Holder, Jun 22 '10 at 12:44
You should replace `std::vector polygon1` with `const std::vector & polygon1` to increase the performance. What input data does give 1 as result? — Alexey Malistov, Jun 22 '10 at 12:47
@Sam Holder, Yes I have thought of that, an edge detection test is next on the agenda after I get this bit working. @Alexey Malistov, Any input I've fed it so far will result in that returning 1. the x and y values can be anywhere between -100 to 100. Thanks for the optimisation though. — Cetra, Jun 22 '10 at 13:05

score 3 · Answer 1 · edited May 23 '17 at 11:48

3

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.

edited May 23 '17 at 11:48

Community

1
1

answered Jun 22 '10 at 13:11

Jon Cage

36,366
38
137
215

I was thinking doing an intermediate step and splitting them into convex, I've had a look at the seperating axis theorem but I don't understand it as much. – Cetra Jun 22 '10 at 13:20
@Cetra SAT isn't difficult, and I've seen it on SO before -- but the non-convex-bit is still an issue. – Jun 23 '10 at 04:36

score -3 · Accepted Answer · answered Jun 24 '10 at 10:52

-3

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.

answered Jun 24 '10 at 10:52

Cetra

2,593
1
21
27

Polygon to Polygon Collision Detection Issue

2 Answers2