public static double[] convexHull(double[] pts,int len,float[] angles,int[] idx,int[] stack){
  int plen=len / 2 - 1;
  if (len < 6) {
    throw new IllegalArgumentException("Input must have at least 3 points");
  }
  if (angles.length < plen || idx.length < plen || stack.length < len / 2) {
    throw new IllegalArgumentException("Pre-allocated data structure too small");
  }
  int i0=0;
  for (int i=2; i < len; i+=2) {
    if (pts[i + 1] < pts[i0 + 1]) {
      i0=i;
    }
 else     if (pts[i + 1] == pts[i0 + 1]) {
      i0=(pts[i] < pts[i0] ? i : i0);
    }
  }
  for (int i=0, j=0; i < len; i+=2) {
    if (i == i0)     continue;
    angles[j]=(float)Math.atan2(pts[i + 1] - pts[i0 + 1],pts[i] - pts[i0]);
    idx[j++]=i;
  }
  ArrayLib.sort(angles,idx,plen);
  float angle=angles[0];
  int ti=0, tj=idx[0];
  for (int i=1; i < plen; i++) {
    int j=idx[i];
    if (angle == angles[i]) {
      double x1=pts[tj] - pts[i0];
      double y1=pts[tj + 1] - pts[i0 + 1];
      double x2=pts[j] - pts[i0];
      double y2=pts[j + 1] - pts[i0 + 1];
      double d1=x1 * x1 + y1 * y1;
      double d2=x2 * x2 + y2 * y2;
      if (d1 >= d2) {
        idx[i]=-1;
      }
 else {
        idx[ti]=-1;
        angle=angles[i];
        ti=i;
        tj=j;
      }
    }
 else {
      angle=angles[i];
      ti=i;
      tj=j;
    }
  }
  int sp=0;
  stack[sp++]=i0;
  int j=0;
  for (int k=0; k < 2; j++) {
    if (idx[j] != -1) {
      stack[sp++]=idx[j];
      k++;
    }
  }
  for (; j < plen; j++) {
    if (idx[j] == -1)     continue;
    while (isNonLeft(i0,stack[sp - 2],stack[sp - 1],idx[j],pts)) {
      sp--;
    }
    stack[sp++]=idx[j];
  }
  double[] hull=new double[2 * sp];
  for (int i=0; i < sp; i++) {
    hull[2 * i]=pts[stack[i]];
    hull[2 * i + 1]=pts[stack[i] + 1];
  }
  return hull;
}

public static double [ ] convexHull ( double [ ] pts , int len , float [ ] angles , int [ ] idx , int [ ] stack ) { int plen = len / 2 - 1 ; if ( len < 6 ) { throw new IllegalArgumentException ( "Input must have at least 3 points" ) ; } if ( angles . length < plen || idx . length < plen || stack . length < len / 2 ) { throw new IllegalArgumentException ( "Pre-allocated data structure too small" ) ; } int i0 = 0 ; for ( int i = 2 ; i < len ; i += 2 ) { if ( pts [ i + 1 ] < pts [ i0 + 1 ] ) { i0 = i ; } else if ( pts [ i + 1 ] == pts [ i0 + 1 ] ) { i0 = ( pts [ i ] < pts [ i0 ] ? i : i0 ) ; } } for ( int i = 0 , j = 0 ; i < len ; i += 2 ) { if ( i == i0 ) continue ; angles [ j ] = ( float ) Math . atan2 ( pts [ i + 1 ] - pts [ i0 + 1 ] , pts [ i ] - pts [ i0 ] ) ; idx [ j ++ ] = i ; } ArrayLib . sort ( angles , idx , plen ) ; float angle = angles [ 0 ] ; int ti = 0 , tj = idx [ 0 ] ; for ( int i = 1 ; i < plen ; i ++ ) { int j = idx [ i ] ; if ( angle == angles [ i ] ) { double x1 = pts [ tj ] - pts [ i0 ] ; double y1 = pts [ tj + 1 ] - pts [ i0 + 1 ] ; double x2 = pts [ j ] - pts [ i0 ] ; double y2 = pts [ j + 1 ] - pts [ i0 + 1 ] ; double d1 = x1 * x1 + y1 * y1 ; double d2 = x2 * x2 + y2 * y2 ; if ( d1 >= d2 ) { idx [ i ] = - 1 ; } else { idx [ ti ] = - 1 ; angle = angles [ i ] ; ti = i ; tj = j ; } } else { angle = angles [ i ] ; ti = i ; tj = j ; } } int sp = 0 ; stack [ sp ++ ] = i0 ; int j = 0 ; for ( int k = 0 ; k < 2 ; j ++ ) { if ( idx [ j ] != - 1 ) { stack [ sp ++ ] = idx [ j ] ; k ++ ; } } for ( ; j < plen ; j ++ ) { if ( idx [ j ] == - 1 ) continue ; while ( isNonLeft ( i0 , stack [ sp - 2 ] , stack [ sp - 1 ] , idx [ j ] , pts ) ) { sp -- ; } stack [ sp ++ ] = idx [ j ] ; } double [ ] hull = new double [ 2 * sp ] ; for ( int i = 0 ; i < sp ; i ++ ) { hull [ 2 * i ] = pts [ stack [ i ] ] ; hull [ 2 * i + 1 ] = pts [ stack [ i ] + 1 ] ; } return hull ; }
computes the 2d convex hull of a set of points using graham ' s scanning algorithm . the algorithm has been implemented as described in cormen , leiserson , and rivest ' s introduction to algorithms . the running time of this algorithm is o ( n log n ) , where n is the number of input points .
