gdx/src/com/badlogic/gdx/math/ConvexHull.java

   1
   2 package com.badlogic.gdx.math;
   3
   4 import com.badlogic.gdx.utils.FloatArray;
   5 import com.badlogic.gdx.utils.IntArray;
   6
   7 /** Computes the convex hull of a set of points using the monotone chain convex hull algorithm (aka Andrew's algorithm).
   8  * @author Nathan Sweet */
   9 public class ConvexHull {
  10         private final FloatArray hull = new FloatArray();
  11         private final IntArray quicksortStack = new IntArray();
  12
  13         /** @see #computePolygon(float[], int, int, boolean) */
  14         public FloatArray computePolygon (FloatArray points, boolean sorted) {
  15                 return computePolygon(points.items, 0, points.size, sorted);
  16         }
  17
  18         /** @see #computePolygon(float[], int, int, boolean) */
  19         public FloatArray computePolygon (float[] polygon, boolean sorted) {
  20                 return computePolygon(polygon, 0, polygon.length, sorted);
  21         }
  22
  23         /** Returns a list of points on the convex hull in counter-clockwise order. Note: the last point in the returned list is the
  24          * same as the first one. */
  25         /** Returns the convex hull polygon for the given point cloud.
  26          * @param points x,y pairs describing points. Duplicate points will result in undefined behavior.
  27          * @param sorted If false, the points will be sorted by the x coordinate then the y coordinate, which is required by the
  28          *           triangulation algorithm. Note in this case the input array is modified.
  29          * @return pairs of coordinates that describe the convex hull polygon in counterclockwise order. Note the returned array is
  30          *         reused for later calls to the same method. */
  31         public FloatArray computePolygon (float[] points, int offset, int count, boolean sorted) {
  32                 int end = offset + count;
  33
  34                 if (!sorted) sort(points, offset, count);
  35
  36                 // Lower hull.
  37                 FloatArray hull = this.hull;
  38                 hull.clear();
  39                 for (int i = offset; i < end; i += 2) {
  40                         float x = points[i];
  41                         float y = points[i + 1];
  42                         while (hull.size >= 4 && ccw(x, y) <= 0)
  43                                 hull.size -= 2;
  44                         hull.add(x);
  45                         hull.add(y);
  46                 }
  47
  48                 // Upper hull.
  49                 for (int i = end - 4, t = hull.size + 2; i >= offset; i -= 2) {
  50                         float x = points[i];
  51                         float y = points[i + 1];
  52                         while (hull.size >= t && ccw(x, y) <= 0)
  53                                 hull.size -= 2;
  54                         hull.add(x);
  55                         hull.add(y);
  56                 }
  57
  58                 return hull;
  59         }
  60
  61         /** Returns > 0 if the points are a counterclockwise turn, < 0 if clockwise, and 0 if colinear. */
  62         private float ccw (float p3x, float p3y) {
  63                 FloatArray hull = this.hull;
  64                 int size = hull.size;
  65                 float p1x = hull.get(size - 4);
  66                 float p1y = hull.get(size - 3);
  67                 float p2x = hull.get(size - 2);
  68                 float p2y = hull.peek();
  69                 return (p2x - p1x) * (p3y - p1y) - (p2y - p1y) * (p3x - p1x);
  70         }
  71
  72         /** Sorts x,y pairs of values by the x value, then the y value.
  73          * @param count Number of indices, must be even. */
  74         private void sort (float[] values, int offset, int count) {
  75                 int lower = offset;
  76                 int upper = offset + count - 1;
  77                 IntArray stack = quicksortStack;
  78                 stack.add(lower);
  79                 stack.add(upper - 1);
  80                 while (stack.size > 0) {
  81                         upper = stack.pop();
  82                         lower = stack.pop();
  83                         if (upper <= lower) continue;
  84                         int i = quicksortPartition(values, lower, upper);
  85                         if (i - lower > upper - i) {
  86                                 stack.add(lower);
  87                                 stack.add(i - 2);
  88                         }
  89                         stack.add(i + 2);
  90                         stack.add(upper);
  91                         if (upper - i >= i - lower) {
  92                                 stack.add(lower);
  93                                 stack.add(i - 2);
  94                         }
  95                 }
  96         }
  97
  98         private int quicksortPartition (final float[] values, int lower, int upper) {
  99                 float x = values[lower];
 100                 float y = values[lower + 1];
 101                 int up = upper;
 102                 int down = lower;
 103                 float temp;
 104                 while (down < up) {
 105                         while (down < up && values[down] <= x)
 106                                 down = down + 2;
 107                         while (values[up] > x || (values[up] == x && values[up + 1] > y))
 108                                 up = up - 2;
 109                         if (down < up) {
 110                                 temp = values[down];
 111                                 values[down] = values[up];
 112                                 values[up] = temp;
 113
 114                                 temp = values[down + 1];
 115                                 values[down + 1] = values[up + 1];
 116                                 values[up + 1] = temp;
 117                         }
 118                 }
 119                 values[lower] = values[up];
 120                 values[up] = x;
 121
 122                 values[lower + 1] = values[up + 1];
 123                 values[up + 1] = y;
 124                 return up;
 125         }
 126 }