Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Copyright (c) 2007 Alexander Hristov.
- * http://www.ahristov.com
- *
- * Feel free to use this code as you wish, as long as you keep this copyright
- * notice. The only limitation on use is that this code cannot be republished
- * on other web sites.
- *
- * As usual, this code comes with no warranties of any kind.
- *
- *
- */
- public ArrayList<Point> quickHull(ArrayList<Point> points) {
- ArrayList<Point> convexHull = new ArrayList<Point>();
- if (points.size() < 3) return (ArrayList)points.clone();
- // find extremals
- int minPoint = -1, maxPoint = -1;
- int minX = Integer.MAX_VALUE;
- int maxX = Integer.MIN_VALUE;
- for (int i = 0; i < points.size(); i++) {
- if (points.get(i).x < minX) {
- minX = points.get(i).x;
- minPoint = i;
- }
- if (points.get(i).x > maxX) {
- maxX = points.get(i).x;
- maxPoint = i;
- }
- }
- Point A = points.get(minPoint);
- Point B = points.get(maxPoint);
- convexHull.add(A);
- convexHull.add(B);
- points.remove(A);
- points.remove(B);
- ArrayList<Point> leftSet = new ArrayList<Point>();
- ArrayList<Point> rightSet = new ArrayList<Point>();
- for (int i = 0; i < points.size(); i++) {
- Point p = points.get(i);
- if (pointLocation(A,B,p) == -1)
- leftSet.add(p);
- else
- rightSet.add(p);
- }
- hullSet(A,B,rightSet,convexHull);
- hullSet(B,A,leftSet,convexHull);
- return convexHull;
- }
- /*
- * Computes the square of the distance of point C to the segment defined by points AB
- */
- public int distance(Point A, Point B, Point C) {
- int ABx = B.x-A.x;
- int ABy = B.y-A.y;
- int num = ABx*(A.y-C.y)-ABy*(A.x-C.x);
- if (num < 0) num = -num;
- return num;
- }
- public void hullSet(Point A, Point B, ArrayList<Point> set, ArrayList<Point> hull) {
- int insertPosition = hull.indexOf(B);
- if (set.size() == 0) return;
- if (set.size() == 1) {
- Point p = set.get(0);
- set.remove(p);
- hull.add(insertPosition,p);
- return;
- }
- int dist = Integer.MIN_VALUE;
- int furthestPoint = -1;
- for (int i = 0; i < set.size(); i++) {
- Point p = set.get(i);
- int distance = distance(A,B,p);
- if (distance > dist) {
- dist = distance;
- furthestPoint = i;
- }
- }
- Point P = set.get(furthestPoint);
- set.remove(furthestPoint);
- hull.add(insertPosition,P);
- // Determine who's to the left of AP
- ArrayList<Point> leftSetAP = new ArrayList<Point>();
- for (int i = 0; i < set.size(); i++) {
- Point M = set.get(i);
- if (pointLocation(A,P,M)==1) {
- leftSetAP.add(M);
- }
- }
- // Determine who's to the left of PB
- ArrayList<Point> leftSetPB = new ArrayList<Point>();
- for (int i = 0; i < set.size(); i++) {
- Point M = set.get(i);
- if (pointLocation(P,B,M)==1) {
- leftSetPB.add(M);
- }
- }
- hullSet(A,P,leftSetAP,hull);
- hullSet(P,B,leftSetPB,hull);
- }
- public int pointLocation(Point A, Point B, Point P) {
- int cp1 = (B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x);
- return (cp1>0)?1:-1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement