-
Notifications
You must be signed in to change notification settings - Fork 2
/
shortest_distance2.py
70 lines (63 loc) · 4.23 KB
/
shortest_distance2.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
import math
#finding lenght between points
def lenght(a,b):
return (math.sqrt( ((a[0]-b[0])**2)+ ((a[1]-b[1])**2)) )
#bruteforce for searching shortest disance for halves.
def halves_search(a,p,q,m):
#if array include two points we find distance, and compare it to shortest one
if len(a)==2:
dist=lenght(a[0],a[1])
if dist<m:
p,q=a[0],a[1]
m=dist
#if array include more then two points we find distances between all of them and compare it to shortest one
else:
for x in range(0,len(a)-1):
for y in range (x+1, len(a)):
if m>lenght(a[x],a[y]):
m=lenght(a[x],a[y])
p,q = a[x],a[y]
return p,q,m
#searching shortest distance (main function) (-array of points, p, q - points with shortest distance and m shortest distance)
def search_pair(a,p,q,m):
l=len(a) #saving lenght of array in l
if l<=(3): return (halves_search(a,p,q,m)) #if array lenght 3 or less we use bruteforce
#finding middle of array, x position of this middle point and splitting array to two (L-left part, R-right part)
midl=l//2
midx=a[midl][0]
L=a[:midl]
R=a[midl:]
#searching points and shorting distances in left side, right side and finally at strip
p,q,m=search_pair(L,p,q,m)
p,q,m=search_pair(R,p,q,m)
p,q,m=get_strip(a,midx,p,q,m)
#returning points and distance
return (p,q,m)
#getting strip for counting
def get_strip(a,xcoordinate,p,q,m):
#initialize empty array for strip and setting borders
strip = []
right,left = xcoordinate+int(m), xcoordinate-int(m)
#searching for points that fits to strip till a[x] not bigger then right border of strip, otherwise there is no more points
for x in a:
if x[0]>right: break
elif left<=x[0]<=right: strip.append(x)
#sorting strip according y coordinate
strip.sort(key=lambda x:x[1])
#checking distances in strip and compare to shortest one. And we need to check out only 6 closest points.
for x in range (0,len(strip)):
for y in range (x+1, len(strip)):
dist= lenght(strip[x],strip[y])
if dist<m:
p,q=strip[x],strip[y]
m=dist
return (p,q,m)
#main function/program
points = [(637, -932), (-993, 176), (693, 817), (418, -676), (-266, -531), (-179, -874), (-926, -332), (-379, 757), (-8, 183), (-991, 262), (880, 978), (-346, 528), (-258, -852), (-41, -124), (806, 901), (-189, -707), (393, -95), (905, -461), (127, -367), (-236, -204), (-527, 538), (-519, 552), (259, 330), (506, -730), (818, 821), (337, 283), (856, -879), (-511, 907), (-450, -145), (960, -344), (237, 338), (-38, -236), (-142, -238), (-95, 941), (-920, 764), (-464, 506), (-506, 636), (-153, 318), (-537, 826), (322, -616), (134, 561), (-13, 49), (-633, 179), (273, 289), (559, -67), (825, -477), (220, 830), (595, 736), (-329, 783), (447, 428), (451, 473), (929, 4), (281, -1000), (-695, 714), (-272, 15), (353, -92), (718, 3), (-697, -320), (-308, 304), (-46, -21), (464, -456), (395, -240), (-563, 569), (-126, 483), (150, -397), (-277, -522), (955, 960), (906, -576), (-960, 710), (37, -12), (-785, -988), (875, 311), (-538, -288), (-21, -836), (-961, -88), (-355, -211), (171, 835), (859, -420), (-300, -252), (178, -751), (385, 254), (-808, -114), (-895, -453), (-574, 167), (330, -750), (-496, -386), (-17, -416), (-756, -195), (832, 36), (-566, 123), (294, -449), (-366, 754), (431, 565), (9, -29), (-398, -214), (248, -236), (669, -700), (-794, -181), (-391, -855), (-45, -775), (391, -176), (694, -205), (569, 704), (-348, -110), (-669, 343), (933, -642), (226, 393), (223, -667), (763, 727), (739, -901), (-390, 771), (660, 393), (620, -71), (167, -624), (-325, 697), (584, 90), (-751, -574), (-73, -569), (938, -647), (-179, 598), (-681, 566), (-511, 520), (-258, -331), (13, 930), (656, -995), (907, -377), (634, -691), (89, -982), (-408, -816), (-544, 168), (804, -599), (-544, -401), (108, -30), (217, -166), (298, 405), (-773, -102), (-853, -370), (15, 629), (83, 944), (441, -484), (232, 381), (901, 80), (-819, -657), (-886, -665), (-691, 61), (-140, -271), (106, 20), (-156, 119), (726, -148), (-922, 448)]
points.sort() #sorting points
p,q = points[0],points[1] #taking first p,q
m=lenght (points[0],points[1]) #and first distance (as current minimum)
pt,pt2,distance=search_pair(points,p,q,m) #finding and printing results
print (distance)
print (pt)
print (pt2)