
package com.badlogic.gdx.math;

import com.badlogic.gdx.utils.FloatArray;
import com.badlogic.gdx.utils.IntArray;

/** Computes the convex hull of a set of points using the monotone chain convex hull algorithm (aka Andrew's algorithm).
 * @author Nathan Sweet */
public class ConvexHull {
	private final FloatArray hull = new FloatArray();
	private final IntArray quicksortStack = new IntArray();

	/** @see #computePolygon(float[], int, int, boolean) */
	public FloatArray computePolygon (FloatArray points, boolean sorted) {
		return computePolygon(points.items, 0, points.size, sorted);
	}

	/** @see #computePolygon(float[], int, int, boolean) */
	public FloatArray computePolygon (float[] polygon, boolean sorted) {
		return computePolygon(polygon, 0, polygon.length, sorted);
	}

	/** Returns a list of points on the convex hull in counter-clockwise order. Note: the last point in the returned list is the
	 * same as the first one. */
	/** Returns the convex hull polygon for the given point cloud.
	 * @param points x,y pairs describing points. Duplicate points will result in undefined behavior.
	 * @param sorted If false, the points will be sorted by the x coordinate then the y coordinate, which is required by the
	 *           triangulation algorithm. Note in this case the input array is modified.
	 * @return pairs of coordinates that describe the convex hull polygon in counterclockwise order. Note the returned array is
	 *         reused for later calls to the same method. */
	public FloatArray computePolygon (float[] points, int offset, int count, boolean sorted) {
		int end = offset + count;

		if (!sorted) sort(points, offset, count);

		// Lower hull.
		FloatArray hull = this.hull;
		hull.clear();
		for (int i = offset; i < end; i += 2) {
			float x = points[i];
			float y = points[i + 1];
			while (hull.size >= 4 && ccw(x, y) <= 0)
				hull.size -= 2;
			hull.add(x);
			hull.add(y);
		}

		// Upper hull.
		for (int i = end - 4, t = hull.size + 2; i >= offset; i -= 2) {
			float x = points[i];
			float y = points[i + 1];
			while (hull.size >= t && ccw(x, y) <= 0)
				hull.size -= 2;
			hull.add(x);
			hull.add(y);
		}

		return hull;
	}

	/** Returns > 0 if the points are a counterclockwise turn, < 0 if clockwise, and 0 if colinear. */
	private float ccw (float p3x, float p3y) {
		FloatArray hull = this.hull;
		int size = hull.size;
		float p1x = hull.get(size - 4);
		float p1y = hull.get(size - 3);
		float p2x = hull.get(size - 2);
		float p2y = hull.peek();
		return (p2x - p1x) * (p3y - p1y) - (p2y - p1y) * (p3x - p1x);
	}

	/** Sorts x,y pairs of values by the x value, then the y value.
	 * @param count Number of indices, must be even. */
	private void sort (float[] values, int offset, int count) {
		int lower = offset;
		int upper = offset + count - 1;
		IntArray stack = quicksortStack;
		stack.add(lower);
		stack.add(upper - 1);
		while (stack.size > 0) {
			upper = stack.pop();
			lower = stack.pop();
			if (upper <= lower) continue;
			int i = quicksortPartition(values, lower, upper);
			if (i - lower > upper - i) {
				stack.add(lower);
				stack.add(i - 2);
			}
			stack.add(i + 2);
			stack.add(upper);
			if (upper - i >= i - lower) {
				stack.add(lower);
				stack.add(i - 2);
			}
		}
	}

	private int quicksortPartition (final float[] values, int lower, int upper) {
		float x = values[lower];
		float y = values[lower + 1];
		int up = upper;
		int down = lower;
		float temp;
		while (down < up) {
			while (down < up && values[down] <= x)
				down = down + 2;
			while (values[up] > x || (values[up] == x && values[up + 1] > y))
				up = up - 2;
			if (down < up) {
				temp = values[down];
				values[down] = values[up];
				values[up] = temp;

				temp = values[down + 1];
				values[down + 1] = values[up + 1];
				values[up + 1] = temp;
			}
		}
		values[lower] = values[up];
		values[up] = x;

		values[lower + 1] = values[up + 1];
		values[up + 1] = y;
		return up;
	}
}

@@ -390,16 +390,47 @@
 Array();
+%0A%09private float%5B%5D sortedPoints;
 %0A%0A%09/** @
@@ -1247,24 +1247,31 @@
 uired by the
+ convex
 %0A%09 *        
@@ -1277,49 +1277,41 @@
     
-triangulation algorithm. Note in this cas
+hull algorithm. If sorting is don
 e th
@@ -1331,16 +1331,20 @@
  is 
+not 
 modified
 .%0A%09 
@@ -1339,16 +1339,62 @@
 modified
+ and count additional working memory is needed
 .%0A%09 * @r
@@ -1710,36 +1710,232 @@
 ed) 
-sort(points, offset, count);
+%7B%0A%09%09%09if (sortedPoints == null %7C%7C sortedPoints.length %3C count) sortedPoints = new float%5Bcount%5D;%0A%09%09%09System.arraycopy(points, offset, sortedPoints, 0, count);%0A%09%09%09points = sortedPoints;%0A%09%09%09offset = 0;%0A%09%09%09sort(points, count);%0A%09%09%7D
 %0A%0A%09%09
@@ -2995,28 +2995,16 @@
  values,
- int offset,
  int cou
@@ -3023,22 +3023,17 @@
 lower = 
-offset
+0
 ;%0A%09%09int 
@@ -3039,25 +3039,16 @@
  upper =
- offset +
  count -

Copy the points if not sorted.