Dynamic Convex hull | Adding Points to an Existing Convex Hull | Python 3 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 copy NEW_LINE def orientation ( a , b , c ) : NEW_LINE INDENT res = ( ( b [ 1 ] - a [ 1 ] ) * ( c [ 0 ] - b [ 0 ] ) - ( c [ 1 ] - b [ 1 ] ) * ( b [ 0 ] - a [ 0 ] ) ) NEW_LINE if ( res == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( res > 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT return - 1 ; NEW_LINE DEDENT def sqDist ( p1 , p2 ) : NEW_LINE INDENT return ( ( p1 [ 0 ] - p2 [ 0 ] ) * ( p1 [ 0 ] - p2 [ 0 ] ) + ( p1 [ 1 ] - p2 [ 1 ] ) * ( p1 [ 1 ] - p2 [ 1 ] ) ) ; NEW_LINE DEDENT def inside ( a , p ) : NEW_LINE INDENT mid = [ 0 , 0 ] NEW_LINE n = len ( a ) NEW_LINE p [ 0 ] *= n ; NEW_LINE p [ 1 ] *= n ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT mid [ 0 ] += a [ i ] [ 0 ] ; NEW_LINE mid [ 1 ] += a [ i ] [ 1 ] ; NEW_LINE a [ i ] [ 0 ] *= n ; NEW_LINE a [ i ] [ 1 ] *= n ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT j = ( i + 1 ) % n ; NEW_LINE x1 = a [ i ] [ 0 ] NEW_LINE x2 = a [ j ] [ 0 ] NEW_LINE y1 = a [ i ] [ 1 ] NEW_LINE y2 = a [ j ] [ 1 ] NEW_LINE a1 = y1 - y2 ; NEW_LINE b1 = x2 - x1 ; NEW_LINE c1 = x1 * y2 - y1 * x2 ; NEW_LINE for_mid = a1 * mid [ 0 ] + b1 * mid [ 1 ] + c1 ; NEW_LINE for_p = a1 * p [ 0 ] + b1 * p [ 1 ] + c1 ; NEW_LINE if ( for_mid * for_p < 0 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT return True ; NEW_LINE DEDENT def addPoint ( a , p ) : NEW_LINE INDENT arr = copy . deepcopy ( a ) NEW_LINE prr = p . copy ( ) NEW_LINE if ( inside ( arr , prr ) ) : NEW_LINE INDENT return ; NEW_LINE DEDENT ind = 0 ; NEW_LINE n = len ( a ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( sqDist ( p , a [ i ] ) < sqDist ( p , a [ ind ] ) ) : NEW_LINE INDENT ind = i NEW_LINE DEDENT DEDENT up = ind ; NEW_LINE while ( orientation ( p , a [ up ] , a [ ( up + 1 ) % n ] ) >= 0 ) : NEW_LINE INDENT up = ( up + 1 ) % n ; NEW_LINE DEDENT low = ind ; NEW_LINE while ( orientation ( p , a [ low ] , a [ ( n + low - 1 ) % n ] ) <= 0 ) : NEW_LINE INDENT low = ( n + low - 1 ) % n NEW_LINE DEDENT ret = [ ] NEW_LINE curr = up ; NEW_LINE ret . append ( a [ curr ] ) ; NEW_LINE while ( curr != low ) : NEW_LINE INDENT curr = ( curr + 1 ) % n ; NEW_LINE ret . append ( a [ curr ] ) ; NEW_LINE DEDENT ret . append ( p ) ; NEW_LINE a . clear ( ) ; NEW_LINE for i in range ( len ( ret ) ) : NEW_LINE INDENT a . append ( ret [ i ] ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ ] NEW_LINE a . append ( [ 0 , 0 ] ) ; NEW_LINE a . append ( [ 3 , - 1 ] ) ; NEW_LINE a . append ( [ 4 , 5 ] ) ; NEW_LINE a . append ( [ - 1 , 4 ] ) ; NEW_LINE n = len ( a ) NEW_LINE p = [ 100 , 100 ] NEW_LINE addPoint ( a , p ) ; NEW_LINE for e in a : NEW_LINE INDENT print ( " ( " , e [ 0 ] , " , ▁ " , e [ 1 ] , " ) ▁ " , end = " ▁ " ) NEW_LINE DEDENT DEDENT