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.
  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) quicksortPairs(points, offset, end - 1);
  35
  36                 // Lower hull.
  37                 FloatArray hull = this.hull;
  38                 for (int i = offset; i < end; i += 2) {
  39                         float x = points[i];
  40                         float y = points[i + 1];
  41                         while (hull.size >= 4 && ccw(x, y) <= 0)
  42                                 hull.size -= 2;
  43                         hull.add(x);
  44                         hull.add(y);
  45                 }
  46
  47                 // Upper hull.
  48                 for (int i = end - 4, t = hull.size + 2; i >= offset; i -= 2) {
  49                         float x = points[i];
  50                         float y = points[i + 1];
  51                         while (hull.size >= t && ccw(x, y) <= 0)
  52                                 hull.size -= 2;
  53                         hull.add(x);
  54                         hull.add(y);
  55                 }
  56
  57                 return hull;
  58         }
  59
  60         /** Returns > 0 if the points are a counterclockwise turn, < 0 if clockwise, and 0 if colinear. */
  61         private float ccw (float p3x, float p3y) {
  62                 FloatArray hull = this.hull;
  63                 int size = hull.size;
  64                 float p1x = hull.get(size - 4);
  65                 float p1y = hull.get(size - 3);
  66                 float p2x = hull.get(size - 2);
  67                 float p2y = hull.peek();
  68                 return (p2x - p1x) * (p3y - p1y) - (p2y - p1y) * (p3x - p1x);
  69         }
  70
  71         /** Sorts x,y pairs of values by the x value, then the y value.
  72          * @param lower Start x index.
  73          * @param upper End x index. */
  74         private void quicksortPairs (float[] values, int lower, int upper) {
  75                 IntArray stack = quicksortStack;
  76                 stack.add(lower);
  77                 stack.add(upper - 1);
  78                 while (stack.size > 0) {
  79                         upper = stack.pop();
  80                         lower = stack.pop();
  81                         if (upper <= lower) continue;
  82                         int i = quicksortPartition(values, lower, upper);
  83                         if (i - lower > upper - i) {
  84                                 stack.add(lower);
  85                                 stack.add(i - 2);
  86                         }
  87                         stack.add(i + 2);
  88                         stack.add(upper);
  89                         if (upper - i >= i - lower) {
  90                                 stack.add(lower);
  91                                 stack.add(i - 2);
  92                         }
  93                 }
  94         }
  95
  96         private int quicksortPartition (final float[] values, int lower, int upper) {
  97                 float x = values[lower];
  98                 float y = values[lower + 1];
  99                 int up = upper;
 100                 int down = lower;
 101                 float temp;
 102                 while (down < up) {
 103                         while (down < up && values[down] <= x)
 104                                 down = down + 2;
 105                         while (values[up] > x || (values[up] == x && values[up + 1] > y))
 106                                 up = up - 2;
 107                         if (down < up) {
 108                                 temp = values[down];
 109                                 values[down] = values[up];
 110                                 values[up] = temp;
 111
 112                                 temp = values[down + 1];
 113                                 values[down + 1] = values[up + 1];
 114                                 values[up + 1] = temp;
 115                         }
 116                 }
 117                 values[lower] = values[up];
 118                 values[up] = x;
 119
 120                 values[lower + 1] = values[up + 1];
 121                 values[up + 1] = y;
 122                 return up;
 123         }
 124 }