package Lacunarity;
import java.awt.Point;import java.awt.Polygon;import java.awt.Rectangle;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.Iterator;
class CHull { static int distance(Point p1, Point p2, Point p3) { int x1 = p1.x; int x2 = p2.x; int x3 = p3.x; int y1 = p1.y; int y2 = p2.y; int y3 = p3.y; return x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3; }
static Rectangle getBounds(ArrayList<Point> array) { return getPolygon(array).getBounds(); }
static Polygon getPolygon(ArrayList<Point> array) { Polygon p = new Polygon(); ArrayList<Point> hull = cHull(array); Iterator<Point> itr = hull.iterator(); Point curr = null;
while(itr.hasNext()) { curr = itr.next(); p.addPoint(curr.x, curr.y); }
return p; }
static ArrayList<Point> cHull(ArrayList<Point> array) { Collections.sort(array, new Comparator<Point>() { public int compare(Point pt1, Point pt2) { int r = pt1.x - pt2.x; return r != 0 ? r : pt1.y - pt2.y; } }); int size = array.size(); if (size < 2) { return null; } else { Point l = array.get(0); Point r = array.get(size - 1); ArrayList<Point> path = new ArrayList<>(); path.add(l); cHull(array, l, r, path); path.add(r); cHull(array, r, l, path); return path; } }
static void cHull(ArrayList<Point> points, Point l, Point r, ArrayList<Point> path) { if (points.size() >= 3) { int maxDist = 0; Point p = null;
for(Point pt : points) { if (pt != l && pt != r) { int tmp = distance(l, r, pt); if (tmp > maxDist) { maxDist = tmp; p = pt; } } }
ArrayList<Point> left = new ArrayList<>(); ArrayList<Point> right = new ArrayList<>(); left.add(l); right.add(p);
for(Point pt : points) { if (distance(l, p, pt) > 0) { left.add(pt); } else if (distance(p, r, pt) > 0) { right.add(pt); } }
left.add(p); right.add(r); cHull(left, l, p, path); path.add(p); cHull(right, p, r, path); } }}
