# Shorter open polyline that passes through the points

#1

Hi All
Which is the best algorithm to draw the polyline shortest passing through a set of points?
Below my code in Python

``````#-*- encoding: UTF-8 -*-
import rhinoscriptsyntax as rs
def ordinaPunti(points):
pi=points[0]
hh=len(points)
k=1
newlist=[pi]  # lista dei punti ordinati per distanza minima
while True:
l=10000
np=len(points)  #numero punti
k=k+1
if k>hh:break
pi=points[0]
for i in range (1,np):
p=points[i]
distance=rs.Distance(pi,p)
if distance<l:
l=distance
pv=p
newlist.append(pv) # appendo il punto piu vicino nella nuova lista
points.remove(pv)  # e  lo tolgo dalla lista di partenza
points=points[1:]  #tolgo il primo punto dalla lista di partenza
points.insert(0,pv)# sostituisco il prmo punto della lista con quello più vicino
np=len(points)
print len(points),"   ",len(newlist)
return newlist
if __name__=='__main__':
punti=rs.GetPoints("get Points")
print "p1 =  ",rs.CurveLength(pl)
newpoints=ordinaPunti(punti)
for p in newpoints:
rs.Sleep(100)
print "pl2  =  ",rs.CurveLength(npl)
``````

Ciao Vittorio

#2

Saluti Vittorio,

Have you tried rs.SortPointList?

Ciao, --Mitch

#3

Hi Mitch
rs.SortPointList is OK Ok Ok.
Grazie Vittorio

(Steve Baer) #4

Are you trying to construct the shortest polyline from an unordered set of points? If so, that is a very hard problem to solve.

#5

Hi Steve
Hi Steve
my goal is to find the shortest polyline to minimize the tool path to drill on points with a CNC machine
Ciao Vittorio

#6

Hey Vittorio,

Most of the CAM sorting programs I know require you to choose a start point (or they just start in the lower left corner) and then you have a choice of how to sort: minimum distance to the next point, directional along X,Y, etc… Then the human needs to choose which sorting method is optimum…

–Mitch

(Steve Baer) #7

Ah, so it sounds like this is a 2D problem and that you are trying to find a minimal path to travel, but it is not necessary to be the absolute minimum of all the possible paths. In that case you may just want to call

``````rs.SortPointList(points)
``````