title: Algorithms for Collision Detection between Arbitrarily sized Convex Polygons
body: <p>I am working on an asteroids clone. Everything is 2D, and written in C++.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <h2>Algorithm:</h2>
  
  <p>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,  <code>y=mx+b</code> 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.</p>
  
  <p>The two Issues I've discovered with this algorithm is that:</p>
  
  <ol>
  <li>it doesn't work on concave polygons, and</li>
  <li>It has problems with an Edge case where the Slope is Undefined.</li>
  </ol>
  
  <p>I have made sure all polygons are Convex, and have written code to handle the Undefined Slope issue  (doubles SHOULD return <code>NAN</code> if we divide by <code>0</code>, so it's pretty easy to test for that).</p>
  
  <p>So, should this work?</p>