<commit_before>
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 <NAME> */
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();<commit_msg>Copy the points if not sorted.<commit_after>
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 <NAME> */
public class ConvexHull {
	private final FloatArray hull = new FloatArray();
	private final IntArray quicksortStack = new IntArray();
	private float[] sortedPoints;

	/** @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 convex
	 *           hull algorithm. If sorting is done the input array is not modified and count additional working memory is needed.
	 * @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) {
			if (sortedPoints == null || sortedPoints.length < count) sortedPoints = new float[count];
			System.arraycopy(points, offset, sortedPoints, 0, count);
			points = sortedPoints;
			offset = 0;
			sort(points, 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 count) {
		int lower = 0;
		int upper = count - 1;
		IntArray stack = quicksortStack;
		stack.add(lower);
		stack.add(upper - 1);
		while (stack.size > 0) {
			upper = stack.pop();
			lower = stack.pop();
{'fraction_non_alphanumeric': 0.1211683517894399, 'fraction_numerical': 0.01203659123736158, 'mean_word_length': 3.225084745762712, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6951204', 'n_tokens_mistral': 2254, 'n_tokens_neox': 2000, 'n_words': 777}