-
Notifications
You must be signed in to change notification settings - Fork 0
/
nearest_neighbor.py
139 lines (108 loc) · 3.55 KB
/
nearest_neighbor.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
import cv2
import numpy as np
import math
import matplotlib.pyplot as plt
import time
best_distance = 0.0
best_tour = []
def display(img,d):
fig = plt.figure(figsize=(8,6))
ax = fig.add_subplot(111)
plt.title('Distance = '+str(d))
ax.imshow(img)
plt.show()
def draw_tsp(map,d,tsp,points):
copy_map = map.copy()
for line in range (0,len(tsp)-1):
last = line+1
# print(points[tsp[line]],points[tsp[last]])
if last == len(tsp)-1:
last = 0
cv2.line(copy_map,
pt1=points[tsp[line]],
pt2=points[tsp[last]],
color=(255,0,0),
thickness=4)
else:
cv2.line(copy_map,
pt1=points[tsp[line]],
pt2=points[tsp[last]],
color=(255,0,0),
thickness=4)
display(copy_map,d)
def nearest_neightbor(inputMap):
maps_dots = ['fountains_dots','memories_dots','shrines_dots']
maps = ['fountains.png','memories.png','shrines.png']
img = cv2.imread('outputs/'+str(maps_dots[int(inputMap)])+'.png',0)
dots = np.zeros(img.shape,dtype=np.uint8)
map = cv2.imread('maps/'+str(maps[int(inputMap)]))
map_rgb = cv2.cvtColor(map,cv2.COLOR_BGR2RGB)
#####################################
######## GET POINTS ###########
#####################################
image,contours,hierarchy = cv2.findContours(img,
cv2.RETR_CCOMP,
cv2.CHAIN_APPROX_SIMPLE)
# Centroids
mnts = [cv2.moments(cnt) for cnt in contours]
centroids = [( int(round(m['m10']/m['m00'])),int(round(m['m01']/m['m00'])) ) for m in mnts]
points = []
dots = np.zeros(img.shape)
for c in centroids:
cv2.circle(img=map_rgb,center=c,radius=8,color=(0,255,0),thickness=-1)
points.append(c)
f = 0
while f < len(points):
x = []
y = []
for i in points:
x.append(i[0])
y.append(i[1])
eu = []
tsp = []
for j in range (0,len(x)):
last = j+1
if last == len(x)-1:
last = 0
s = (pow(x[f]-x[j],2) + pow (y[f]-y[j],2)) #N
eu.append(math.sqrt(s))
else:
s = (pow(x[f]-x[j],2) + pow (y[f]-y[j],2)) #N
eu.append(math.sqrt(s))
# Sort indices
_indexSort = np.array(np.argsort(eu))
# Tour TSP
indexSort = list(_indexSort)
for x in range (0,len(indexSort)):
tsp.append(int(indexSort[x]))
# Insert
tsp.insert(len(tsp),f)
# Last distance
_lTour = points[tsp[len(tsp)-1]]
_lTour2 = points[tsp[len(tsp)-2]]
s = (pow(_lTour[0]-_lTour2[0],2) + pow (_lTour[1]-_lTour2[1],2))
eu.append(math.sqrt(s))
# Distance
distance = sum(eu)
# Draw lines (All routes)
#draw_tsp(map_rgb,distance,tsp,points)
# Best distance & tour
global best_distance, best_tour
if f == 0:
best_distance = distance
best_tour = tsp
if(distance < best_distance):
best_distance = distance
best_tour = tsp
# Feels
f += 1
print('\n')
print('Distance: ',best_distance)
print('Best tour: ',best_tour)
print('\n')
print('Tour coordinates:')
print('--------------------')
for r in best_tour:
print(points[r])
# Print optimal tour
draw_tsp(map_rgb,best_distance,best_tour,points)