-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathShortest-distance-between-two-points.py
233 lines (195 loc) · 6.28 KB
/
Shortest-distance-between-two-points.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
import math
import random
def dist(p1, p2):
"""
Find the euclidean distance between two 2-D points
Args:
p1: (p1_x, p1_y)
p2: (p2_x, p2_y)
Returns:
Euclidean distance between p1 and p2
"""
return (((p1[0]) - (p2[0]))**2 + ((p1[1]) -(p2[1]))**2)**0.5
def sort_points_by_x(points):
"""
Sort a list of points by their X coordinate
Args:
points: List of points [(p1_x, p1_y), (p2_x, p2_y), ...]
Returns:
List of points sorted by X coordinate
"""
s = []
m = []
for num in points:
s.append(num[0])
s.sort()
for num in s:
for dum in points:
if num == dum[0]:
m.append(dum)
unique_d = []
for num in m:
if num not in unique_d:
unique_d.append(num)
return unique_d
#print(sort_points_by_x([(3, 4), (1, 1), (7, 5),(3, 5)]))
def sort_points_by_y(points):
"""
Sort a list of points by their Y coordinate
Args:
points: List of points [(p1_x, p1_y), (p2_x, p2_y), ...]
Returns:
List of points sorted by Y coordinate
"""
s = []
m = []
for num in points:
s.append(num[1])
s.sort()
for num in s:
for dum in points:
if num == dum[1]:
m.append(dum)
unique_d = []
for num in m:
if num not in unique_d:
unique_d.append(num)
return unique_d
#print(sort_points_by_y([(3, 4), (1, 8), (7, 6), (3, 5)]))
def naive_closest_pair(plane):
"""
Find the closest pair of points in the plane using the brute
force approach
Args:
plane: List of points [(p1_x, p1_y), (p2_x, p2_y), ...]
Returns:
Distance between closest pair of points and closest pair
of points: [dist_bw_p1_p2, (p1_x, p1_y), (p2_x, p2_y)]
"""
s = []
for num in plane:
for dum in plane:
h = (num, dum , dist(num, dum))
s.append(h)
unique = []
for num in s:
if num[0] != num[1]:
unique.append(num)
values = []
for num in unique:
values.append(num[2])
values.sort()
for num in unique:
if values[0] in num:
return num
#print(naive_closest_pair([(5, 4), (3, 2), (9, 10)]))
#print(naive_closest_pair([(5, 4), (6, 3), (3, 2)]))
def closest_pair_in_strip(points, d):
"""
Find the closest pair of points in the given strip with a
given upper bound. This function is called by
efficient_closest_pair_routine
Args:
points: List of points in the strip of interest.
d: Minimum distance already found found by
efficient_closest_pair_routine
Returns:
Distance between closest pair of points and closest pair
of points: [dist_bw_p1_p2, (p1_x, p1_y), (p2_x, p2_y)] if
distance between p1 and p2 is less than d. Otherwise
return -1.
"""
s = []
l = []
for num in points:
for dum in points:
h = (num, dum , dist(num, dum))
s.append(h)
unique = []
for num in s:
if num[0] != num[1] and num[2] < d:
unique.append((num[0]))
unique.append(num[1])
for num in unique:
if num not in l:
l.append(num)
values = []
t = sort_points_by_y(l)
if len(l) != 0:
return naive_closest_pair(l)
else:
return -1
#print(closest_pair_in_strip([(5, 4), (6, 6), (3, 2), (1, 1), (6, 7), (11, 13), (15, 16), (16, 18)], 16))
def efficient_closest_pair_routine(points):
s = []
l = []
for num in points:
for dum in points:
h = (num, dum , dist(num, dum))
s.append(h)
for num in s:
if num[0] != num[1]:
l.append(num[2])
t = min(l)
for num in s:
if num[2] == t:
return num
print(efficient_closest_pair_routine([(5, 4), (6, 6), (3, 2), (1, 1), (6, 7), (11, 13), (15, 16), (16, 18)]))
def efficient_closest_pair(points):
"""
Find the closest pair of points in the plane using the divide
and conquer approach by calling efficient_closest_pair_routine.
Args:
plane: List of points [(p1_x, p1_y), (p2_x, p2_y), ...]
Returns:
Distance between closest pair of points and closest pair
of points: [dist_bw_p1_p2, (p1_x, p1_y), (p2_x, p2_y)]
"""
q = len(points)
if q == 3:
distance = (10**9)**3
s = efficient_closest_pair_routine(points)
if s[2] <= distance:
return s[2]
else:
return distance
elif q == 2:
distance = (10**9)**3
s = efficient_closest_pair_routine(points)
if s[2] <= distance:
return distance
else:
return distance
else:
distance = (10**9)**3
middlevalue = points[q//2]
m = efficient_closest_pair(points[:q//2])
n = efficient_closest_pair(points[q//2:])
d = distance
if closest_pair_in_strip(points, d) == -1:
return distance
else:
return closest_pair_in_strip(points, distance)
print(efficient_closest_pair([(4.10, 4),(4.15, 4),(4.25, 4),(4.5, 4),(5, 4), (8, 2), (9, 10)]))
def generate_plane(plane_size, num_pts):
"""
Function to generate random points.
Args:
plane_size: Size of plane (X_max, Y_max)
num_pts: Number of points to generate
Returns:
List of random points: [(p1_x, p1_y), (p2_x, p2_y), ...]
"""
gen = random.sample(range(plane_size[0]*plane_size[1]), num_pts)
random_points = [(i%plane_size[0] + 1, i//plane_size[1] + 1) for i in gen]
return random_points
if __name__ == "__main__":
#number of points to generate
num_pts = 10
#size of plane for generation of points
plane_size = (10, 10)
plane = generate_plane(plane_size, num_pts)
print(plane)
#naive_closest_pair(plane)
#efficient_closest_pair(plane)
print(generate_plane((100, 100), 10))