Dynamic Convex hull | Adding Points to an Existing Convex Hull | Java program to add given a point p to a given convext hull . The program assumes that the point of given convext hull are in anti - clockwise order . ; checks whether the point crosses the convex hull or not ; Returns the square of distance between two input points ; Checks whether the point is inside the convex hull or not ; Initialize the centroid of the convex hull ; Multiplying with n to avoid floating point arithmetic . ; if the mid and the given point lies always on the same side w . r . t every edge of the convex hull , then the point lies inside the convex hull ; Adds a point p to given convex hull a [ ] ; If point is inside p ; point having minimum distance from the point p ; Find the upper tangent ; Find the lower tangent ; Initialize result ; making the final hull by traversing points from up to low of given convex hull . ; Modify the original vector ; Driver code ; the set of points in the convex hull ; Print the modified Convex Hull
import java . io . * ; import java . util . * ; class GFG { static int orientation ( ArrayList < Integer > a , ArrayList < Integer > b , ArrayList < Integer > c ) { int res = ( b . get ( 1 ) - a . get ( 1 ) ) * ( c . get ( 0 ) - b . get ( 0 ) ) - ( c . get ( 1 ) - b . get ( 1 ) ) * ( b . get ( 0 ) - a . get ( 0 ) ) ; if ( res == 0 ) return 0 ; if ( res > 0 ) return 1 ; return - 1 ; } static int sqDist ( ArrayList < Integer > p1 , ArrayList < Integer > p2 ) { return ( p1 . get ( 0 ) - p2 . get ( 0 ) ) * ( p1 . get ( 0 ) - p2 . get ( 0 ) ) + ( p1 . get ( 1 ) - p2 . get ( 1 ) ) * ( p1 . get ( 1 ) - p2 . get ( 1 ) ) ; } static boolean inside ( ArrayList < ArrayList < Integer > > A , ArrayList < Integer > p ) { ArrayList < Integer > mid = new ArrayList < Integer > ( Arrays . asList ( 0 , 0 ) ) ; int n = A . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { mid . set ( 0 , mid . get ( 0 ) + A . get ( i ) . get ( 0 ) ) ; mid . set ( 1 , mid . get ( 1 ) + A . get ( i ) . get ( 1 ) ) ; } for ( int i = 0 , j ; i < n ; i ++ ) { j = ( i + 1 ) % n ; int x1 = A . get ( i ) . get ( 0 ) * n , x2 = A . get ( j ) . get ( 0 ) * n ; int y1 = A . get ( i ) . get ( 1 ) * n , y2 = A . get ( j ) . get ( 1 ) * n ; int a1 = y1 - y2 ; int b1 = x2 - x1 ; int c1 = x1 * y2 - y1 * x2 ; int for_mid = a1 * mid . get ( 0 ) + b1 * mid . get ( 1 ) + c1 ; int for_p = a1 * p . get ( 0 ) * n + b1 * p . get ( 1 ) * n + c1 ; if ( for_mid * for_p < 0 ) return false ; } return true ; } static void addPoint ( ArrayList < ArrayList < Integer > > a , ArrayList < Integer > p ) { if ( inside ( a , p ) ) return ; int ind = 0 ; int n = a . size ( ) ; for ( int i = 1 ; i < n ; i ++ ) { if ( sqDist ( p , a . get ( i ) ) < sqDist ( p , a . get ( ind ) ) ) { ind = i ; } } int up = ind ; while ( orientation ( p , a . get ( up ) , a . get ( ( up + 1 ) % n ) ) >= 0 ) up = ( up + 1 ) % n ; int low = ind ; while ( orientation ( p , a . get ( low ) , a . get ( ( n + low - 1 ) % n ) ) <= 0 ) low = ( n + low - 1 ) % n ; ArrayList < ArrayList < Integer > > ret = new ArrayList < ArrayList < Integer > > ( ) ; int curr = up ; ret . add ( a . get ( curr ) ) ; while ( curr != low ) { curr = ( curr + 1 ) % n ; ret . add ( a . get ( curr ) ) ; } ret . add ( p ) ; a . clear ( ) ; for ( int i = 0 ; i < ret . size ( ) ; i ++ ) { a . add ( ret . get ( i ) ) ; } } public static void main ( String [ ] args ) { ArrayList < ArrayList < Integer > > a = new ArrayList < ArrayList < Integer > > ( ) ; a . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 0 ) ) ) ; a . add ( new ArrayList < Integer > ( Arrays . asList ( 3 , - 1 ) ) ) ; a . add ( new ArrayList < Integer > ( Arrays . asList ( 4 , 5 ) ) ) ; a . add ( new ArrayList < Integer > ( Arrays . asList ( - 1 , 4 ) ) ) ; int n = a . size ( ) ; ArrayList < Integer > p = new ArrayList < Integer > ( Arrays . asList ( 100 , 100 ) ) ; addPoint ( a , p ) ; for ( ArrayList < Integer > e : a ) { System . out . print ( " ( " + e . get ( 0 ) + " , ▁ " + e . get ( 1 ) + " ) ▁ " ) ; } } }