1 /******************************************************************************* 2 * Copyright 2011 See AUTHORS file. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 ******************************************************************************/ 16 17 package com.badlogic.gdx.math; 18 19 import com.badlogic.gdx.utils.FloatArray; 20 import com.badlogic.gdx.utils.IntArray; 21 import com.badlogic.gdx.utils.ShortArray; 22 23 /** Computes the convex hull of a set of points using the monotone chain convex hull algorithm (aka Andrew's algorithm). 24 * @author Nathan Sweet */ 25 public class ConvexHull { 26 private final IntArray quicksortStack = new IntArray(); 27 private float[] sortedPoints; 28 private final FloatArray hull = new FloatArray(); 29 private final IntArray indices = new IntArray(); 30 private final ShortArray originalIndices = new ShortArray(false, 0); 31 32 /** @see #computePolygon(float[], int, int, boolean) */ 33 public FloatArray computePolygon (FloatArray points, boolean sorted) { 34 return computePolygon(points.items, 0, points.size, sorted); 35 } 36 37 /** @see #computePolygon(float[], int, int, boolean) */ 38 public FloatArray computePolygon (float[] polygon, boolean sorted) { 39 return computePolygon(polygon, 0, polygon.length, sorted); 40 } 41 42 /** Returns a list of points on the convex hull in counter-clockwise order. Note: the last point in the returned list is the 43 * same as the first one. */ 44 /** Returns the convex hull polygon for the given point cloud. 45 * @param points x,y pairs describing points. Duplicate points will result in undefined behavior. 46 * @param sorted If false, the points will be sorted by the x coordinate then the y coordinate, which is required by the convex 47 * hull algorithm. If sorting is done the input array is not modified and count additional working memory is needed. 48 * @return pairs of coordinates that describe the convex hull polygon in counterclockwise order. Note the returned array is 49 * reused for later calls to the same method. */ 50 public FloatArray computePolygon (float[] points, int offset, int count, boolean sorted) { 51 int end = offset + count; 52 53 if (!sorted) { 54 if (sortedPoints == null || sortedPoints.length < count) sortedPoints = new float[count]; 55 System.arraycopy(points, offset, sortedPoints, 0, count); 56 points = sortedPoints; 57 offset = 0; 58 sort(points, count); 59 } 60 61 FloatArray hull = this.hull; 62 hull.clear(); 63 64 // Lower hull. 65 for (int i = offset; i < end; i += 2) { 66 float x = points[i]; 67 float y = points[i + 1]; 68 while (hull.size >= 4 && ccw(x, y) <= 0) 69 hull.size -= 2; 70 hull.add(x); 71 hull.add(y); 72 } 73 74 // Upper hull. 75 for (int i = end - 4, t = hull.size + 2; i >= offset; i -= 2) { 76 float x = points[i]; 77 float y = points[i + 1]; 78 while (hull.size >= t && ccw(x, y) <= 0) 79 hull.size -= 2; 80 hull.add(x); 81 hull.add(y); 82 } 83 84 return hull; 85 } 86 87 /** @see #computeIndices(float[], int, int, boolean, boolean) */ 88 public IntArray computeIndices (FloatArray points, boolean sorted, boolean yDown) { 89 return computeIndices(points.items, 0, points.size, sorted, yDown); 90 } 91 92 /** @see #computeIndices(float[], int, int, boolean, boolean) */ 93 public IntArray computeIndices (float[] polygon, boolean sorted, boolean yDown) { 94 return computeIndices(polygon, 0, polygon.length, sorted, yDown); 95 } 96 97 /** Computes a hull the same as {@link #computePolygon(float[], int, int, boolean)} but returns indices of the specified points. */ 98 public IntArray computeIndices (float[] points, int offset, int count, boolean sorted, boolean yDown) { 99 int end = offset + count; 100 101 if (!sorted) { 102 if (sortedPoints == null || sortedPoints.length < count) sortedPoints = new float[count]; 103 System.arraycopy(points, offset, sortedPoints, 0, count); 104 points = sortedPoints; 105 offset = 0; 106 sortWithIndices(points, count, yDown); 107 } 108 109 IntArray indices = this.indices; 110 indices.clear(); 111 112 FloatArray hull = this.hull; 113 hull.clear(); 114 115 // Lower hull. 116 for (int i = offset, index = i / 2; i < end; i += 2, index++) { 117 float x = points[i]; 118 float y = points[i + 1]; 119 while (hull.size >= 4 && ccw(x, y) <= 0) { 120 hull.size -= 2; 121 indices.size--; 122 } 123 hull.add(x); 124 hull.add(y); 125 indices.add(index); 126 } 127 128 // Upper hull. 129 for (int i = end - 4, index = i / 2, t = hull.size + 2; i >= offset; i -= 2, index--) { 130 float x = points[i]; 131 float y = points[i + 1]; 132 while (hull.size >= t && ccw(x, y) <= 0) { 133 hull.size -= 2; 134 indices.size--; 135 } 136 hull.add(x); 137 hull.add(y); 138 indices.add(index); 139 } 140 141 // Convert sorted to unsorted indices. 142 if (!sorted) { 143 short[] originalIndicesArray = originalIndices.items; 144 int[] indicesArray = indices.items; 145 for (int i = 0, n = indices.size; i < n; i++) 146 indicesArray[i] = originalIndicesArray[indicesArray[i]]; 147 } 148 149 return indices; 150 } 151 152 /** Returns > 0 if the points are a counterclockwise turn, < 0 if clockwise, and 0 if colinear. */ 153 private float ccw (float p3x, float p3y) { 154 FloatArray hull = this.hull; 155 int size = hull.size; 156 float p1x = hull.get(size - 4); 157 float p1y = hull.get(size - 3); 158 float p2x = hull.get(size - 2); 159 float p2y = hull.peek(); 160 return (p2x - p1x) * (p3y - p1y) - (p2y - p1y) * (p3x - p1x); 161 } 162 163 /** Sorts x,y pairs of values by the x value, then the y value. 164 * @param count Number of indices, must be even. */ 165 private void sort (float[] values, int count) { 166 int lower = 0; 167 int upper = count - 1; 168 IntArray stack = quicksortStack; 169 stack.add(lower); 170 stack.add(upper - 1); 171 while (stack.size > 0) { 172 upper = stack.pop(); 173 lower = stack.pop(); 174 if (upper <= lower) continue; 175 int i = quicksortPartition(values, lower, upper); 176 if (i - lower > upper - i) { 177 stack.add(lower); 178 stack.add(i - 2); 179 } 180 stack.add(i + 2); 181 stack.add(upper); 182 if (upper - i >= i - lower) { 183 stack.add(lower); 184 stack.add(i - 2); 185 } 186 } 187 } 188 189 private int quicksortPartition (final float[] values, int lower, int upper) { 190 float x = values[lower]; 191 float y = values[lower + 1]; 192 int up = upper; 193 int down = lower; 194 float temp; 195 short tempIndex; 196 while (down < up) { 197 while (down < up && values[down] <= x) 198 down = down + 2; 199 while (values[up] > x || (values[up] == x && values[up + 1] < y)) 200 up = up - 2; 201 if (down < up) { 202 temp = values[down]; 203 values[down] = values[up]; 204 values[up] = temp; 205 206 temp = values[down + 1]; 207 values[down + 1] = values[up + 1]; 208 values[up + 1] = temp; 209 } 210 } 211 values[lower] = values[up]; 212 values[up] = x; 213 214 values[lower + 1] = values[up + 1]; 215 values[up + 1] = y; 216 217 return up; 218 } 219 220 /** Sorts x,y pairs of values by the x value, then the y value and stores unsorted original indices. 221 * @param count Number of indices, must be even. */ 222 private void sortWithIndices (float[] values, int count, boolean yDown) { 223 int pointCount = count / 2; 224 originalIndices.clear(); 225 originalIndices.ensureCapacity(pointCount); 226 short[] originalIndicesArray = originalIndices.items; 227 for (short i = 0; i < pointCount; i++) 228 originalIndicesArray[i] = i; 229 230 int lower = 0; 231 int upper = count - 1; 232 IntArray stack = quicksortStack; 233 stack.add(lower); 234 stack.add(upper - 1); 235 while (stack.size > 0) { 236 upper = stack.pop(); 237 lower = stack.pop(); 238 if (upper <= lower) continue; 239 int i = quicksortPartitionWithIndices(values, lower, upper, yDown, originalIndicesArray); 240 if (i - lower > upper - i) { 241 stack.add(lower); 242 stack.add(i - 2); 243 } 244 stack.add(i + 2); 245 stack.add(upper); 246 if (upper - i >= i - lower) { 247 stack.add(lower); 248 stack.add(i - 2); 249 } 250 } 251 } 252 253 private int quicksortPartitionWithIndices (final float[] values, int lower, int upper, boolean yDown, short[] originalIndices) { 254 float x = values[lower]; 255 float y = values[lower + 1]; 256 int up = upper; 257 int down = lower; 258 float temp; 259 short tempIndex; 260 while (down < up) { 261 while (down < up && values[down] <= x) 262 down = down + 2; 263 if (yDown) { 264 while (values[up] > x || (values[up] == x && values[up + 1] < y)) 265 up = up - 2; 266 } else { 267 while (values[up] > x || (values[up] == x && values[up + 1] > y)) 268 up = up - 2; 269 } 270 if (down < up) { 271 temp = values[down]; 272 values[down] = values[up]; 273 values[up] = temp; 274 275 temp = values[down + 1]; 276 values[down + 1] = values[up + 1]; 277 values[up + 1] = temp; 278 279 tempIndex = originalIndices[down / 2]; 280 originalIndices[down / 2] = originalIndices[up / 2]; 281 originalIndices[up / 2] = tempIndex; 282 } 283 } 284 values[lower] = values[up]; 285 values[up] = x; 286 287 values[lower + 1] = values[up + 1]; 288 values[up + 1] = y; 289 290 tempIndex = originalIndices[lower / 2]; 291 originalIndices[lower / 2] = originalIndices[up / 2]; 292 originalIndices[up / 2] = tempIndex; 293 294 return up; 295 } 296 } 297
