package Algorithms;
import Utils.*;
public class ConvexHull{ public static double findConvexHull(IntVector points, byte[] image, int width, int height) { points.size = 0;
boolean hasEqualLowestHeight = false; int firstY = height;
for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { if (image[x + width * y] == -1) { hasEqualLowestHeight = hasEqualLowestHeight || y == firstY; firstY = Math.min(y, firstY); points.addTwo(x, y); } } }
final int n = points.size;
if (n >= 2) points.addTwo(points.buf[0], points.buf[1]);
int[] xy = points.buf;
int min = 0; int m = -2; double minAngle = hasEqualLowestHeight ? -1.0 : 0.0;
while (min != n) { m += 2; int temp = xy[m]; xy[m] = xy[min]; xy[min] = temp; temp = xy[m+1]; xy[m+1] = xy[min+1]; xy[min+1] = temp;
min = n; double v = minAngle; minAngle = 4.0; int h2 = 0;
for (int i = m + 2; i < n + 2; i += 2) { int dx = xy[i] - xy[m]; int ax = Math.abs(dx); int dy = xy[i+1] - xy[m+1]; int ay = Math.abs(dy); double t; if (dx == 0 && dy == 0) { t = 0.0; } else { t = (double)dy / (double)(ax + ay); }
if (dx < 0) { t = 2.0 - t; } else if (dy < 0) { t += 4.0; }
if (t > v) { if (t < minAngle) { min = i; minAngle = t; h2 = dx * dx + dy * dy; } else if (t == minAngle) { int h = dx * dx + dy * dy; if (h > h2) { min = i; h2 = h; } } } } }
points.resize(m + 2);
double signedArea = 0.0; for (int i = 0; i < points.size; i += 2) { int next = (i+2) % points.size; signedArea += (double)(points.buf[i] * points.buf[next+1]) - (double)(points.buf[i+1] * points.buf[next]); }
double area = Math.abs(0.5 * signedArea); return area; }}
