Algorithms for Collision Detection between Arbitrarily sized Convex Polygons

6
votes

I am working on an asteroids clone. Everything is 2D, and written in C++.

For the asteroids, I am generating random N-sided polygons. I have guaranteed that they are Convex. I then rotate them, give them a rotspeed, and have them fly through space. It all works, and is very pretty.

For collision, I'm using an Algorithm I thought of myself. This is probably a bad idea, and if push comes to shove, I'll probably scrap the whole thing and find a tutorial on the internet.

I've written and implemented everything, and the collision detection works alright.... most of the time. It will randomly fail when there's obviously a collision on screen, and sometimes indicate collision when nothing is touching. Either I have flubbed my implementation somewhere, or my algorithm is horrible. Due to the size/scope of my implementation (over several source files) I didn't want to bother you with that, and just wanted someone to check that my algorithm is, in fact, sound. At that point I can go on a big bug hunt.

Algorithm:

For each Asteroid, I have a function that outputs where each vertex should be when drawing the asteroid. For each pair of adjacent Vertices, I generate the Formula for the line that they sit on, y=mx+b format. I then start with one of my ships vertices, testing that point to see whether it is inside the asteroid. I start by plugging in the X coordinate of the point, and comparing the output to the Actual Y value. This tells me if the point is above or below the line. I then do the same with the Center of the Asteroid, to determine which half of the line is considered "Inside" the asteroid. I then repeat for each pair of Vertices. IF I ever find a line for which my point is not on the same side as the center of the asteroid, I know there is no collision, and exit detection for that point. Since there are 3 points on my ship, I then have to test for the next point. If all 3 points exit early, then There are no collisions for any of the points on the ship, and we're done. If any point is bound on all sides by the lines made up by the asteroid, then it is inside the asteroid, and the collision flag is set.

The two Issues I've discovered with this algorithm is that:

  1. it doesn't work on concave polygons, and
  2. It has problems with an Edge case where the Slope is Undefined.

I have made sure all polygons are Convex, and have written code to handle the Undefined Slope issue (doubles SHOULD return NAN if we divide by 0, so it's pretty easy to test for that).

So, should this work?

2
c++algorithm2dcollision-detection
I would break down an asteroid in many triangles - or actually build the asteroid from (random) triangles. All triangles move at same speed, same direction to ensure the asteroid remains as a whole. To detect collisions, it would be a simpler triangles intersection calculation, with some added optimization to avoid the O(n*m) complexity for two asteroids of n and m triangles. Also, that would allow both concave and convex forms. (triangles may overlap, that would probably make things easier) – Breaking not so bad

2 Answers

2
votes

I did something similar to compute polygon intersections, namely finding if a vertex sits within a given polygon.

Your algorithm is sound, and indeed does not work for concave polys. The line representation you chose is also problematic at slopes approaching infinity. I chose to use a couple of vectors for mine, one for the line direction, and one for a reference point on the line. From these, I can easily derive a parameterized equation of the line, and use that in various ways to find intersections with other shapes.

P = S +  t * D

Any point P of the line can be caracterized by its coordinate t on the the line, given the above relation, where S is the reference point, and D the direction vector.

This representation lets you easily define which parts of the plane is the positive and the negative one (ie. above and below the line), thanks to the direction orientation. Now, any region of the plane can be defined as an intersection of several lines' negative or positive subplanes. So your "point within polygon" algorithm could be slightly changed to use that representation, with the added constraint of all the direction pointing clockwise, and testing for the point being in the negative subplane of all the lines (so you don't need the centre of the polygon anymore).

The formula to compute the side of a point wrt a line I used is the following:

(xs - xp) * yd - (ys - yp) * xd

The slope issue appears here when point P is close to S.

That representation can be computed using the edge vertices, but in order to have correct subplanes, you must keep your vertices in your polygon in condecutive orders.

For concave polygons, the problem is a bit more complicated: briefly, you have to test that the point is between two consecutive convex edges. This can be achieved by checking the coordinate of the point on the edge when projected on it, and ensuring it stands between 0 and length(edge) (assuming that the direction is normalized). Note that it boils down to check if the point belongs to a triangle within the polygon.

7
votes

The standard solution to this problem is using the separating axis theorem (SAT). Given two convex polygons, A and B, the algorithm basically goes like this:

for each normal N of the edges of A and B
    intervalA = [min, max] of projecting A on N
    intervalB = [min, max] of projecting B on N
    if intervalA doesn't overlap intervalB
        return did not collide
return collided