Gift-Wrap Convex Hull Bounding Polygon

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

Gift-Wrap Convex Hull Bounding Polygon

Postby daniel.weck » Fri Jul 22, 2011 8:54 am

I ported a Java implementation of the gift-wrap algorithm to LibGDX. This basically takes a cloud of points (which could consist in a set of Box2D fixtures, for example) and it generates a bounding polygon that is a convex hull (with all the useful inherent properties of non-concave polygons).

Enjoy :)

Code: Select all
Array<Array<Vector2>> polygons; // e.g. existing Box2D fixtures

Array<Vector2> pointsCloud= new Array<Vector2>(polygons.size * 3); // capacity initialization, assuming 3 vertices per polygon (triangles)
for (int j = 0; j < polygons.size; j++) {
    Array<Vector2> polygon = polygons.get(j);
    for (int i = 0; i < polygon.size; i++) {
        Vector2 point = polygon.get(i);

        boolean pointAlreadyInCloud = false;
        for (int k = 0; k < pointsCloud.size; k++) {
            Vector2 pointInCloud = pointsCloud.get(k);
            if (pointInCloud.x == point.x && pointInCloud.y == point.y) {
                pointAlreadyInCloud = true;
                break;
            }
        }
        if (!pointAlreadyInCloud)
                pointsCloud.add(point);
    }
}

Array<Vector2> convexHull = BoundingPolygon.createGiftWrapConvexHull(pointsCloud);


Code: Select all
import com.badlogic.gdx.math.Vector2;
import com.badlogic.gdx.utils.Array;

public class BoundingPolygon {

   /**
    * Find the convex hull of a point cloud using "Gift-wrap" algorithm - start
    * with an external point, and walk around the outside edge by testing
    * angles. Runs in O(N*S) time where S is number of sides of resulting
    * polygon. Worst case: point cloud is all vertices of convex polygon ->
    * O(N^2). There may be faster algorithms to do this, should you need one -
    * this is just the simplest. You can get O(N log N) expected time if you
    * try, I think, and O(N) if you restrict inputs to simple polygons. Returns
    * null if number of vertices passed is less than 3. Results should be
    * passed through convex decomposition afterwards to ensure that each shape
    * has few enough points to be used in Box2d. May be buggy with colinear
    * points on hull, but we check angle with an equality resolver that always
    * picks the longer edge (this seems to be working, but it sometimes creates
    * an extra edge along a line).
    */
   public static Array<Vector2> createGiftWrapConvexHull(
         Array<Vector2> points) {
      assert (points.size > 2);

      int[] edgeList = new int[points.size];
      int numEdges = 0;
      float minY = Float.MAX_VALUE;
      int minYIndex = points.size;
      for (int i = 0; i < points.size; ++i) {
         Vector2 point = points.get(i);
         if (point.y < minY) {
            minY = point.y;
            minYIndex = i;
         }
      }
      int startIndex = minYIndex;
      int winIndex = -1;
      float dx = -1.0f;
      float dy = 0.0f;
      while (winIndex != minYIndex) {
         float newdx = 0.0f;
         float newdy = 0.0f;
         float maxDot = -2.0f;
         Vector2 point2 = points.get(startIndex);

         for (int i = 0; i < points.size; ++i) {
            if (i == startIndex)
               continue;
            Vector2 point1 = points.get(i);

            newdx = point1.x - point2.x;
            newdy = point1.y - point2.y;
            float nrm = (float) Math.sqrt(newdx * newdx + newdy * newdy);
            nrm = (nrm == 0.0f) ? 1.0f : nrm;
            newdx /= nrm;
            newdy /= nrm;
            float newDot = newdx * dx + newdy * dy;
            if (newDot > maxDot) {
               maxDot = newDot;
               winIndex = i;
            }
         }
         edgeList[numEdges] = winIndex;
         numEdges++;

         Vector2 point3 = points.get(winIndex);

         dx = point3.x - point2.x;
         dy = point3.y - point2.y;
         float nrm = (float) Math.sqrt(dx * dx + dy * dy);
         nrm = (nrm == 0.0f) ? 1.0f : nrm;
         dx /= nrm;
         dy /= nrm;
         startIndex = winIndex;
      }
      Array<Vector2> polygon = new Array<Vector2>(numEdges);

      for (int i = 0; i < numEdges; i++) {
         Vector2 point4 = points.get(edgeList[i]);
         polygon.add(point4.cpy());
      }

      if (polygon.size <= 3)
         return polygon;

      float tolerance = 2.0f / 180.0f * (float) Math.PI; // 2 degrees

      Array<Integer> toRemove = null;
      for (int i = 0; i < polygon.size; ++i) {
         int lower = (i == 0) ? (polygon.size - 1) : (i - 1);
         int middle = i;
         int upper = (i == polygon.size - 1) ? (0) : (i + 1);
         Vector2 pointMiddle = polygon.get(middle);
         Vector2 pointLower = polygon.get(lower);
         Vector2 pointUpper = polygon.get(upper);
         float dx0 = pointMiddle.x - pointLower.x;
         float dy0 = pointMiddle.y - pointLower.y;
         float dx1 = pointUpper.x - pointMiddle.x;
         float dy1 = pointUpper.y - pointMiddle.y;
         float norm0 = (float) Math.sqrt(dx0 * dx0 + dy0 * dy0);
         float norm1 = (float) Math.sqrt(dx1 * dx1 + dy1 * dy1);
         if (!(norm0 > 0.0f && norm1 > 0.0f)
               && (toRemove == null || (polygon.size - toRemove.size) > 3)) {
            // Merge identical points

            if (toRemove == null)
               toRemove = new Array<Integer>();
            toRemove.add(i);
         }
         dx0 /= norm0;
         dy0 /= norm0;
         dx1 /= norm1;
         dy1 /= norm1;
         float cross = dx0 * dy1 - dx1 * dy0;
         float dot = dx0 * dx1 + dy0 * dy1;
         if (Math.abs(cross) < tolerance && dot > 0
               && (toRemove == null || (polygon.size - toRemove.size) > 3)) {
            if (toRemove == null)
               toRemove = new Array<Integer>();
            toRemove.add(i);
         }
      }
      if (toRemove == null || toRemove.size == 0)
         return polygon;

      for (int i = 0; i < toRemove.size; ++i) {
         int index = toRemove.get(i);
         polygon.removeIndex(index - i);
      }

      return polygon;
   }
}
daniel.weck
 
Posts: 57
Joined: Mon Mar 21, 2011 8:18 am

Re: Gift-Wrap Convex Hull Bounding Polygon

Postby daniel.weck » Fri Jul 22, 2011 9:06 am

Original source code:

http://farseerphysics.codeplex.com/Sour ... 41#1436512

http://farseerphysics.codeplex.com/license


License: Microsoft Permissive License (Ms-PL) v1.1
Microsoft Permissive License (Ms-PL)

This license governs use of the accompanying software. If you use the software, you accept this license. If you do not accept the license, do not use the software.

1. Definitions

The terms "reproduce," "reproduction," "derivative works," and "distribution" have the same meaning here as under U.S. copyright law.

A "contribution" is the original software, or any additions or changes to the software.

A "contributor" is any person that distributes its contribution under this license.

"Licensed patents" are a contributor's patent claims that read directly on its contribution.

2. Grant of Rights

(A) Copyright Grant- Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free copyright license to reproduce its contribution, prepare derivative works of its contribution, and distribute its contribution or any derivative works that you create.

(B) Patent Grant- Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free license under its licensed patents to make, have made, use, sell, offer for sale, import, and/or otherwise dispose of its contribution in the software or derivative works of the contribution in the software.

3. Conditions and Limitations

(A) No Trademark License- This license does not grant you rights to use any contributors' name, logo, or trademarks.

(B) If you bring a patent claim against any contributor over patents that you claim are infringed by the software, your patent license from such contributor to the software ends automatically.

(C) If you distribute any portion of the software, you must retain all copyright, patent, trademark, and attribution notices that are present in the software.

(D) If you distribute any portion of the software in source code form, you may do so only under this license by including a complete copy of this license with your distribution. If you distribute any portion of the software in compiled or object code form, you may only do so under a license that complies with this license.

(E) The software is licensed "as-is." You bear the risk of using it. The contributors give no express warranties, guarantees or conditions. You may have additional consumer rights under your local laws which this license cannot change. To the extent permitted under your local laws, the contributors exclude the implied warranties of merchantability, fitness for a particular purpose and non-infringement.
daniel.weck
 
Posts: 57
Joined: Mon Mar 21, 2011 8:18 am


Return to Libgdx Contributions

Who is online

Users browsing this forum: No registered users and 1 guest