Dynamic Convex hull | Adding Points to an Existing Convex Hull | 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 ; 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 ; the set of points in the convex hull ; Print the modified Convex Hull
function orientation ( a , b , c ) { let res = ( b [ 1 ] - a [ 1 ] ) * ( c [ 0 ] - b [ 0 ] ) - ( c [ 1 ] - b [ 1 ] ) * ( b [ 0 ] - a [ 0 ] ) ; if ( res == 0 ) return 0 ; if ( res > 0 ) return 1 ; return - 1 ; } function sqDist ( p1 , p2 ) { return ( p1 [ 0 ] - p2 [ 0 ] ) * ( p1 [ 0 ] - p2 [ 0 ] ) + ( p1 [ 1 ] - p2 [ 1 ] ) * ( p1 [ 1 ] - p2 [ 1 ] ) ; } function inside ( A , p ) { let mid = [ 0 , 0 ] ; let n = A . length ; for ( let i = 0 ; i < n ; i ++ ) { mid [ 0 ] += A [ i ] [ 0 ] ; mid [ 1 ] += A [ i ] [ 1 ] ; } for ( let i = 0 , j ; i < n ; i ++ ) { j = ( i + 1 ) % n ; let x1 = A [ i ] [ 0 ] * n , x2 = A [ j ] [ 0 ] * n ; let y1 = A [ i ] [ 1 ] * n , y2 = A [ j ] [ 1 ] * n ; let a1 = y1 - y2 ; let b1 = x2 - x1 ; let c1 = x1 * y2 - y1 * x2 ; let for_mid = a1 * mid [ 0 ] + b1 * mid [ 1 ] + c1 ; let for_p = a1 * p [ 0 ] * n + b1 * p [ 1 ] * n + c1 ; if ( for_mid * for_p < 0 ) return false ; } return true ; } function addPoint ( a , p ) { if ( inside ( a , p ) ) return ; let ind = 0 ; let n = a . length ; for ( let i = 1 ; i < n ; i ++ ) { if ( sqDist ( p , a [ i ] ) < sqDist ( p , a [ ind ] ) ) { ind = i ; } } let up = ind ; while ( orientation ( p , a [ up ] , a [ ( up + 1 ) % n ] ) >= 0 ) up = ( up + 1 ) % n ; let low = ind ; while ( orientation ( p , a [ low ] , a [ ( n + low - 1 ) % n ] ) <= 0 ) low = ( n + low - 1 ) % n ; let ret = [ ] ; let curr = up ; ret . push ( a [ curr ] ) ; while ( curr != low ) { curr = ( curr + 1 ) % n ; ret . push ( a [ curr ] ) ; } ret . push ( p ) ; a = [ ] ; for ( let i = 0 ; i < ret . length ; i ++ ) { a . push ( ret [ i ] ) ; } return a ; } let a = [ ] a . push ( [ 0 , 0 ] ) ; a . push ( [ 3 , - 1 ] ) ; a . push ( [ 4 , 5 ] ) ; a . push ( [ - 1 , 4 ] ) ; let n = a . length ; let p = [ 100 , 100 ] ; a = addPoint ( a , p ) ; for ( let e = 0 ; e < a . length ; e ++ ) { document . write ( " " + a [ e ] [ 0 ] + " " + a [ e ] [ 1 ] + " " ) ; }