Two convex polygons collision detection

Any community contributions to libgdx go here! Some may get included in the core API when permission is granted.

Two convex polygons collision detection

Postby jan.stria » Wed Nov 09, 2011 12:36 pm

I have implemented algorithm for detecting collision of two convex polygons based on the Separating Axis Theorem. It is intended to be added to a class com.badlogic.gdx.math.Intersector. The license is Apache 2.

Code: Select all
/**
 * Check whether specified convex polygons overlap.
 *
 * @param p1 The first polygon.
 * @param p2 The second polygon.
 * @return Whether polygons overlap.
 */
public static boolean overlapConvexPolygons(Polygon p1, Polygon p2)
{
   return overlapConvexPolygons(p1, p2, null);
}

/**
 * Check whether specified convex polygons overlap. If they don't optionally obtain a normalized
 * direction of the separation axis.
 *
 * @param p1 The first polygon.
 * @param p2 The second polygon.
 * @param separation Normalized vector defining a direction of the separation axis (optional).
 * @return Whether polygons overlap.
 */
public static boolean overlapConvexPolygons(Polygon p1, Polygon p2, Vector2 separation)
{
   final float[] verts1 = p1.getVertices();
   final float[] verts2 = p2.getVertices();
   return !separateConvexPolygons(verts1, verts2, separation) &&
      !separateConvexPolygons(verts2, verts1, separation);
}

/**
 * Check whether some of the first polygon's edges defined forms a separation axis of two polygons
 * defined by the lists of vertices. Optionally obtain a normalized direction of the separation axis.
 *
 * @param verts1 Vertices of the first polygon whose edges will be examined as separation axes.
 * @param verts2 Vertices of the second polygon.
 * @param separation Normalized vector defining a direction of the separation axis (optional).
 * @return Whether some of the first polygon's edges forms a separation axis.
 */
static boolean separateConvexPolygons(float[] verts1, float[] verts2, Vector2 separation)
{
   final int length1 = verts1.length;
   final int length2 = verts2.length;
   
   for (int i = 0; i < length1; i += 2)
   {
      // index of the next vertex
      final int j = (i + 1) % length1;
      
      // projection axis is perpendicular to potential separation axis edge i->j
      float projX = verts1[j + 1] - verts1[i + 1];
      float projY = verts1[i] - verts1[j];
      
      // normalize projection axis
      final float length = (float)Math.sqrt(projX * projX + projY * projY);
      projX /= length;
      projY /= length;
      
      // project the first vertices to the projection axis
      float min1 = Float.POSITIVE_INFINITY, max1 = Float.NEGATIVE_INFINITY;
      for (int k = 0; k < length1; k += 2)
      {
         final float dot = projX * verts1[k] + projY * verts1[k + 1];
         if (dot < min1) min1 = dot;
         if (dot > max1) max1 = dot;
      }
      
      // project the second vertices to the projection axis
      float min2 = Float.POSITIVE_INFINITY, max2 = Float.NEGATIVE_INFINITY;
      for (int k = 0; k < length2; k += 2)
      {
         final float dot = projX * verts2[k] + projY * verts2[k + 1];
         if (dot < min2) min2 = dot;
         if (dot > max2) max2 = dot;
      }
      
      // if projections do not overlap we have found the separation axis
      if ((max1 < min2) || (max2 < min1))
      {
         if (null != separation) separation.set(projY, -projX);
         return true;
      }
   }
   
   return false;
}
jan.stria
 
Posts: 3
Joined: Thu May 19, 2011 10:49 am

Re: Two convex polygons collision detection

Postby mzechner » Sat Nov 12, 2011 10:54 am

Wow, that's awesome. I'll add this to libgdx core with your permission (you'll get a cosy place in the contributors file of course).
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm


Return to Libgdx Contributions

Who is online

Users browsing this forum: No registered users and 1 guest