List < Integer > convexhull ( List < Float > pts ) { int npts = pts . size ( ) / 3 ; List < Integer > out = new ArrayList <> ( ) ; // Find lower-leftmost point. int hull = 0 ; for ( int i = 1 ; i < npts ; ++ i ) { float [ ] a = new float [ ] { pts . get ( i * 3 ) , pts . get ( i * 3 + 1 ) , pts . get ( i * 3 + 2 ) } ; float [ ] b = new float [ ] { pts . get ( hull * 3 ) , pts . get ( hull * 3 + 1 ) , pts . get ( hull * 3 + 2 ) } ; if ( cmppt ( a , b ) ) { hull = i ; } } // Gift wrap hull. int endpt = 0 ; do { out . add ( hull ) ; endpt = 0 ; for ( int j = 1 ; j < npts ; ++ j ) { float [ ] a = new float [ ] { pts . get ( hull * 3 ) , pts . get ( hull * 3 + 1 ) , pts . get ( hull * 3 + 2 ) } ; float [ ] b = new float [ ] { pts . get ( endpt * 3 ) , pts . get ( endpt * 3 + 1 ) , pts . get ( endpt * 3 + 2 ) } ; float [ ] c = new float [ ] { pts . get ( j * 3 ) , pts . get ( j * 3 + 1 ) , pts . get ( j * 3 + 2 ) } ; if ( hull == endpt || left ( a , b , c ) ) { endpt = j ; } } hull = endpt ; } while ( endpt != out . get ( 0 ) ) ; return out ; }
returns number of points on hull .