public void process ( Point2D_F64 [ ] input , int length , Polygon2D_F64 hull ) { // ahdnle special cases if ( length == 2 ) { hull . vertexes . resize ( length ) ; for ( int i = 0 ; i < length ; i ++ ) { hull . get ( i ) . set ( input [ i ] ) ; } return ; } sorter . sort ( input , length ) ; work . reset ( ) ; // construct the lower hull for ( int i = 0 ; i < length ; i ++ ) { Point2D_F64 p = input [ i ] ; //Contains at least 2 points and the last two points and 'p' do not make a counter-clockwise turn while ( work . size ( ) >= 2 && subtractThenCross ( p , work . getTail ( 0 ) , work . getTail ( 1 ) ) >= 0 ) { // remove the last points from the hull work . removeTail ( ) ; } // append p to the end work . add ( p ) ; } work . removeTail ( ) ; int minSize = work . size + 2 ; // construct upper hull for ( int i = length - 1 ; i >= 0 ; i -- ) // Finding top layer from hull { //Contains at least 2 points and the last two points and 'p' do not make a counter-clockwise turn Point2D_F64 p = input [ i ] ; while ( work . size ( ) >= minSize && subtractThenCross ( p , work . getTail ( 0 ) , work . getTail ( 1 ) ) >= 0 ) { work . removeTail ( ) ; } // append p to the end work . add ( p ) ; } work . removeTail ( ) ; // create a copy for the output // the work buffer contains references to the input points, but to be safe the output should have its // own instances hull . vertexes . resize ( work . size ) ; for ( int i = 0 ; i < work . size ( ) ; i ++ ) { hull . vertexes . data [ i ] . set ( work . get ( i ) ) ; } }
Computes the convex hull . The output will be in counter - clockwise order .