static int construct ( Point2D [ ] points , int count , int [ ] out_convex_hull ) { ConvexHull convex_hull = new ConvexHull ( points , count ) ; int t0 = 0 , tm = 1 ; Point2D pt_0 = points [ t0 ] ; while ( tm < count && points [ tm ] . isEqual ( pt_0 , NumberUtils . doubleEps ( ) ) ) tm ++ ; // We don't want to close the gap between t0 and tm. convex_hull . m_tree_hull . addElement ( t0 , - 1 ) ; if ( tm < count ) { convex_hull . m_tree_hull . addBiggestElement ( tm , - 1 ) ; for ( int tp = tm + 1 ; tp < count ; tp ++ ) { // Dynamically insert into the current convex hull. Point2D pt_p = points [ tp ] ; int p = convex_hull . treeHull_ ( pt_p ) ; if ( p != - 1 ) convex_hull . m_tree_hull . setElement ( p , tp ) ; // reset the place holder to the point index. } } // Extracts the convex hull from the tree. Reading the tree in order from first to last is the resulting convex hull. int out_count = 0 ; for ( int i = convex_hull . m_tree_hull . getFirst ( - 1 ) ; i != - 1 ; i = convex_hull . m_tree_hull . getNext ( i ) ) out_convex_hull [ out_count ++ ] = convex_hull . m_tree_hull . getElement ( i ) ; return out_count ; }
Static method to construct the convex hull from an array of points . The out_convex_hull array will be populated with the subset of index positions which contribute to the convex hull . Returns the number of points in the convex hull . \ param points The points used to create the convex hull . \ param count The number of points in the input Point2D array . \ param out_convex_hull An index array allocated by the user at least as big as the size of the input points array .