#-*- coding: utf-8 -*-
import math
class PointInfo :
startPoint =0;
includeY = []
def __init__(self, x, dis):
self.x = x
self.dis = dis
self.min = -1
self.minIndex = -1
self.NotY = []
self.initMin()
self.include = False
def initMin(self):
self.min = -1
self.minIndex = -1
for y in range(len(self.dis)) :
if self.dis[y] == 0 :
continue
if self.checkY(y) :
continue
if self.min == -1 :
self.min = self.dis[y]
self.minIndex = y
elif self.min > self.dis[y] :
self.min = self.dis[y]
self.minIndex = y
def getMinTo(self):
return self.minIndex
def getMinDistance(self):
self.initMin()
return self.min
def getFinalDistance(self):
return self.min
def setInclude(self, include = True):
self.include = include
def getInclude(self):
return self.include
def checkY(self, y):
return y in PointInfo.includeY or y in self.NotY
def addNotYList(self, y_list):
for y in y_list :
if not y in self.NotY :
self.addNotY(y)
self.NotY.sort()
def addNotY(self, y):
self.NotY.append(y)
def delNotY(self, y):
self.NotY.remove(y)
def getNotYList(self):
return self.NotY
point = [(50 ,50),(26 ,23),(50 ,95),(85 ,66),(67 ,40),(46 ,12),(6 ,2),(51 ,12),(44 ,30),(4 ,56),(61 ,14),(73 ,6),(74 ,72),(51 ,52),
(7 ,40),(31 ,66),(8 ,16),(62 ,70),(87 ,19),(32 ,77),(56 ,67),(86 ,50),(0 ,74),(65 ,42),(19 ,97),(49 ,14),(4 ,11),(0 ,19),(17 ,37),(46 ,33),(12 ,90)]
PointInfo.startPoint = 0
dis_list = []
min_order = [] #[from, to]
def distance(x, y):
dis = (x[0]-y[0])**2 + (x[1]-y[1])**2
return math.sqrt(dis)
def checkCircle(x, y):
count = 0
temp_y = y
const = False
while True :
const = False
for p in min_order :
if temp_y == p[0]:
temp_y = p[1]
count += 1
const = True
break
if x == temp_y and const == True:
break
if const == False :
break
if count <= len(min_order) :
if count == len(point) -1 :
return True
elif x == temp_y and const == True:
return False
else :
return True
if const == False :
return True
return True
def getMinOrder(dis):
temp_min = -1
temp_x = -1
for i in range(len(dis)) :
if dis[i].getInclude() :
continue
if temp_min == -1 :
temp_min = dis[i].getMinDistance()
temp_x = i
elif temp_min > dis[i].getMinDistance() :
temp_min = dis[i].getMinDistance()
temp_x = i
if checkCircle(temp_x, dis[temp_x].getMinTo()) :
dis[temp_x].setInclude()
dis[dis[temp_x].getMinTo()].addNotYList(dis[temp_x].getNotYList())
dis[dis[temp_x].getMinTo()].addNotY(temp_x)
#print("true",temp_x, " , " , dis[temp_x].getMinTo())
return [temp_x, dis[temp_x].getMinTo()]
else:
dis[temp_x].addNotY(dis[temp_x].getMinTo())
#print("false",temp_x, " , " , dis[temp_x].getMinTo())
return [-1,-1]
#return dis[temp_x].getMinTo()
for i in range(len(point)):
temp_dis = []
for j in range(len(point)):
temp_dis.append(distance(point[i], point[j]))
dis_list.append(PointInfo(i, temp_dis))
while True :
temp = getMinOrder(dis_list)
if temp[0] == -1 and temp[1] == -1 :
continue
min_order.append(temp)
PointInfo.includeY.append(temp[1])
if len(min_order) > len(point)-1:
break
from_p = PointInfo.startPoint
sorted_p = []
while True :
for i in range(len(min_order)) :
if min_order[i][0] == from_p :
sorted_p.append(min_order[i])
from_p = min_order[i][1]
if len(sorted_p) == len(point) :
break
dis_sum = 0
for dis in dis_list :
dis_sum += dis.getFinalDistance()
print(sorted_p)
print(dis_sum)