divide_and_conquer.closest_pair_of_points¶
The algorithm finds distance between closest pair of points in the given n points. Approach used -> Divide and conquer The points are sorted based on Xco-ords and then based on Yco-ords separately. And by applying divide and conquer approach, minimum distance is obtained recursively.
>> Closest points can lie on different sides of partition. This case handled by forming a strip of points whose Xco-ords distance is less than closest_pair_dis from mid-point’s Xco-ords. Points sorted based on Yco-ords are used in this step to reduce sorting time. Closest pair distance is found in the strip of points. (closest_in_strip)
min(closest_pair_dis, closest_in_strip) would be the final answer.
Time complexity: O(n * log n)
Attributes¶
Functions¶
|
|
|
divide and conquer approach |
|
|
|
closest pair of points in strip |
|
brute force approach to find distance between closest pair points |
|
Module Contents¶
- divide_and_conquer.closest_pair_of_points.closest_pair_of_points(points, points_counts)¶
>>> closest_pair_of_points([(2, 3), (12, 30)], len([(2, 3), (12, 30)])) 28.792360097775937
- divide_and_conquer.closest_pair_of_points.closest_pair_of_points_sqr(points_sorted_on_x, points_sorted_on_y, points_counts)¶
divide and conquer approach
Parameters : points, points_count (list(tuple(int, int)), int)
Returns : (float): distance btw closest pair of points
>>> closest_pair_of_points_sqr([(1, 2), (3, 4)], [(5, 6), (7, 8)], 2) 8
- divide_and_conquer.closest_pair_of_points.column_based_sort(array, column=0)¶
>>> column_based_sort([(5, 1), (4, 2), (3, 0)], 1) [(3, 0), (5, 1), (4, 2)]
- divide_and_conquer.closest_pair_of_points.dis_between_closest_in_strip(points, points_counts, min_dis=float('inf'))¶
closest pair of points in strip
Parameters : points, points_count, min_dis (list(tuple(int, int)), int, int)
Returns : min_dis (float): distance btw closest pair of points in the strip (< min_dis)
>>> dis_between_closest_in_strip([[1,2],[2,4],[5,7],[8,9],[11,0]],5) 85
- divide_and_conquer.closest_pair_of_points.dis_between_closest_pair(points, points_counts, min_dis=float('inf'))¶
brute force approach to find distance between closest pair points
Parameters : points, points_count, min_dis (list(tuple(int, int)), int, int)
Returns : min_dis (float): distance between closest pair of points
>>> dis_between_closest_pair([[1,2],[2,4],[5,7],[8,9],[11,0]],5) 5
- divide_and_conquer.closest_pair_of_points.euclidean_distance_sqr(point1, point2)¶
>>> euclidean_distance_sqr([1,2],[2,4]) 5
- divide_and_conquer.closest_pair_of_points.points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]¶