Geometry for Games

Convex Hull (Quick Hull)

The convex hull problem in geometry tries to find the smallest convex set containing the points, or more informally, finding those 'border' points that, when united, form a convex polygon that includes all other points.

There are many approaches for handling this problem:

• Gift Wrap algorithm
• Graham Scan
• Marriage-before-Conquest
• Chan's algorithm
• Quickhull

Here we'll talk about the Quick Hull algorithm, which is one of the easiest to implement and has a reasonable expected running time of O(n log n). (Unfortunately,it has a worst case scenario of O(n²) )

Let's assume a random set of points:

As a start for the algorithm, we need a chord that we know as belonging to the final convex hull. One such chord can be the segment between the leftmost and the rightmost points, which are known to be on the hull:

This chord will be our initial "set of hull points".

We now proceed to divide the set of the remaining points into two sets, depending on which side of the chord they fall. Let's call S1 the set of the points above the chord in our example, and S2 the set of the points below the chord. For each of the sets, we proceed recursively as follows:

1) We find the point that is furthest away from the chord. Let's call this point P. This point will belong to the hull, so we insert it in our "set of hull points" between A and B:

2) We now remove from the S1 set all points that fall inside the triangle:

3) Again, we form two sets : The set of points above AP and the set of points above PB (in the example above, this set is empty). We replace the original chord AB with the segments AP and PB, and apply the algorithm from step 1 recursively on the two sets. We stop when a set is empty or has only one point, in which case it's known to be on the hull

The remaining steps would be as follows:

Ok, if you are new to geometry algorithms, you might wonder how to check whethera point lies on one side of a segment or on the other side. The notion of vector cross product comes to help us. The cross product v x w of two vectors v and w is a vector whose length is |v||w|sin φ, (where |v| is the length of v and φ is the angle between the vectors), and who is orthogonal (perpendicular) to both v and w.  Since there are two such possible vectors, the definition arbitrarily selects the one that matches the direction in which a screw would move if rotated from v to w:

Mathematically, if the coordinates of vectors v and w are (v_x,v_y) and (w_x,w_y) respectively, the cross produt will be (v_xw_y - w_yw_x). So now, if you have a segment defined by points A B and want to check on which side of AB a third point P falls, you only need to compute the cross product AB x AP and check its sign: If it's negative, it will be on the "right" side of AB (when standing on A and looking towards B). If positive, it will be on the left side:

This Java function performs the check for two points:

  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;
  }
  

The second thing you might find trouble with is computing the distance between a point and a segment. Check the related article here, and consider that when we are trying to find -in step 1 of the algorithm - the point P that is farthest away from AB, the segment AB never changes. And since we need only to know the biggest distance and not its exact value, we need not divide by the length of the AB segment, and we needn't take the square root either. Thus, we only need to be concerned by the following "pseudodistance" when looking for the farthest point:

  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;
  }  

0001  public ArrayList<Point> quickHull(ArrayList<Point> points) {
0002    ArrayList<Point> convexHull = new ArrayList<Point>();
0003    if (points.size() < 3) return (ArrayList)points.clone();
0004    // find extremals
0005    int minPoint = -1, maxPoint = -1;
0006    int minX = Integer.MAX_VALUE;
0007    int maxX = Integer.MIN_VALUE;
0008    for (int i = 0; i < points.size(); i++) {
0009      if (points.get(i).x < minX) {
0010        minX = points.get(i).x;
0011        minPoint = i;
0012      } 
0013      if (points.get(i).x > maxX) {
0014        maxX = points.get(i).x;
0015        maxPoint = i;       
0016      }
0017    }
0018    Point A = points.get(minPoint);
0019    Point B = points.get(maxPoint);
0020    convexHull.add(A);
0021    convexHull.add(B);
0022    points.remove(A);
0023    points.remove(B);
0024    
0025    ArrayList<Point> leftSet = new ArrayList<Point>();
0026    ArrayList<Point> rightSet = new ArrayList<Point>();
0027    
0028    for (int i = 0; i < points.size(); i++) {
0029      Point p = points.get(i);
0030      if (pointLocation(A,B,p) == -1)
0031        leftSet.add(p);
0032      else
0033        rightSet.add(p);
0034    }
0035    hullSet(A,B,rightSet,convexHull);
0036    hullSet(B,A,leftSet,convexHull);
0037    
0038    return convexHull;
0039  }
0040  
0041  public void hullSet(Point A, Point B, ArrayList<Point> set, ArrayList<Point> hull) {
0042    int insertPosition = hull.indexOf(B);
0043    if (set.size() == 0) return;
0044    if (set.size() == 1) {
0045      Point p = set.get(0);
0046      set.remove(p);
0047      hull.add(insertPosition,p);
0048      return;
0049    }
0050    int dist = Integer.MIN_VALUE;
0051    int furthestPoint = -1;
0052    for (int i = 0; i < set.size(); i++) {
0053      Point p = set.get(i);
0054      int distance  = distance(A,B,p);
0055      if (distance > dist) {
0056        dist = distance;
0057        furthestPoint = i;
0058      }
0059    }
0060    Point P = set.get(furthestPoint);
0061    set.remove(furthestPoint);
0062    hull.add(insertPosition,P);
0063    
0064    // Determine who's to the left of AP
0065    ArrayList<Point> leftSetAP = new ArrayList<Point>();
0066    for (int i = 0; i < set.size(); i++) {
0067      Point M = set.get(i);
0068      if (pointLocation(A,P,M)==1) {
0069        //set.remove(M);
0070        leftSetAP.add(M);
0071      }
0072    }
0073    
0074    // Determine who's to the left of PB
0075    ArrayList<Point> leftSetPB = new ArrayList<Point>();
0076    for (int i = 0; i < set.size(); i++) {
0077      Point M = set.get(i);
0078      if (pointLocation(P,B,M)==1) {
0079        //set.remove(M);
0080        leftSetPB.add(M);
0081      }
0082    }
0083    hullSet(A,P,leftSetAP,hull);
0084    hullSet(P,B,leftSetPB,hull);
0085  }
0086

You can try this implementation interactively using the following applet. Click anywhere to drop a point. Once placed, you can drag it with the mouse.

Source code

Comments

(c) 2006-2007 Alexander Hristov. Todos los derechos reservados
Más información sobre cursos de java, cursos de ajax, cursos de .NET,