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")
    pl=rs.AddPolyline(punti)   
    print "p1 =  ",rs.CurveLength(pl)
    newpoints=ordinaPunti(punti)
    for p in newpoints:
        rs.AddCircle(p,5)
        rs.Sleep(100)
    npl=rs.AddPolyline(newpoints)
    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… :smile:

–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)