Optimum location of point to minimize total distance | A Python3 program to find optimum location and total cost ; Class defining a point ; Class defining a line of ax + by + c = 0 form ; Method to get distance of point ( x , y ) from point p ; Utility method to compute total distance all points when choose point on given line has x - coordinate value as X ; Calculating Y of chosen point by line equation ; Utility method to find minimum total distance ; Loop until difference between low and high become less than EPS ; mid1 and mid2 are representative x co - ordiantes of search space ; If mid2 point gives more total distance , skip third part ; If mid1 point gives more total distance , skip first part ; Compute optimum distance cost by sending average of low and high as X ; Method to find optimum cost ; Converting 2D array input to point array ; Driver Code
import math NEW_LINE class Optimum_distance : NEW_LINE INDENT class Point : NEW_LINE INDENT def __init__ ( self , x , y ) : NEW_LINE INDENT self . x = x NEW_LINE self . y = y NEW_LINE DEDENT DEDENT class Line : NEW_LINE INDENT def __init__ ( self , a , b , c ) : NEW_LINE INDENT self . a = a NEW_LINE self . b = b NEW_LINE self . c = c NEW_LINE DEDENT DEDENT def dist ( self , x , y , p ) : NEW_LINE INDENT return math . sqrt ( ( x - p . x ) ** 2 + ( y - p . y ) ** 2 ) NEW_LINE DEDENT def compute ( self , p , n , l , x ) : NEW_LINE INDENT res = 0 NEW_LINE y = - 1 * ( l . a * x + l . c ) / l . b NEW_LINE for i in range ( n ) : NEW_LINE INDENT res += self . dist ( x , y , p [ i ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT def find_Optimum_cost_untill ( self , p , n , l ) : NEW_LINE INDENT low = - 1e6 NEW_LINE high = 1e6 NEW_LINE eps = 1e-6 + 1 NEW_LINE while ( ( high - low ) > eps ) : NEW_LINE INDENT mid1 = low + ( high - low ) / 3 NEW_LINE mid2 = high - ( high - low ) / 3 NEW_LINE dist1 = self . compute ( p , n , l , mid1 ) NEW_LINE dist2 = self . compute ( p , n , l , mid2 ) NEW_LINE if ( dist1 < dist2 ) : NEW_LINE INDENT high = mid2 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid1 NEW_LINE DEDENT DEDENT return self . compute ( p , n , l , ( low + high ) / 2 ) NEW_LINE DEDENT def find_Optimum_cost ( self , p , l ) : NEW_LINE INDENT n = len ( p ) NEW_LINE p_arr = [ None ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT p_obj = self . Point ( p [ i ] [ 0 ] , p [ i ] [ 1 ] ) NEW_LINE p_arr [ i ] = p_obj NEW_LINE DEDENT return self . find_Optimum_cost_untill ( p_arr , n , l ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT obj = Optimum_distance ( ) NEW_LINE l = obj . Line ( 1 , - 1 , - 3 ) NEW_LINE p = [ [ - 3 , - 2 ] , [ - 1 , 0 ] , [ - 1 , 2 ] , [ 1 , 2 ] , [ 3 , 4 ] ] NEW_LINE print ( obj . find_Optimum_cost ( p , l ) ) NEW_LINE DEDENT