Announcements

Starting in December, we will archive content from the community that is 10 years and older. This FAQ provides more information.

Visual LISP, AutoLISP and General Customization
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 

Fastest Way Through Every Line

31 REPLIES 31
Reply
Message 1 of 32
rpajounia
1790 Views, 31 Replies

Fastest Way Through Every Line

So i know people have the traveling sales man theory but that has to do with end points. My problem has to do with lines. I need a function that will tell me the fastest way through each line. i always start at ( 3048, 1828.8 ). I setup a drawing with an example output. My output is not the fastest or shortest distance traveled but that is what im trying to figure out

Start X3048.000000000000 Y1828.800000000000
Go To X4267.200000000002 Y1828.800000000000
Go To X6096.000000000001 Y1828.800000000001
Go To X6096.000000000001 Y2362.200000000001
Go To X5537.200000000002 Y2362.200000000001
Go To X4267.200000000002 Y2362.200000000000
Go To X4267.200000000002 Y1828.800000000000
Go To X4267.200000000002 Y2362.200000000000
Go To X4267.200000000000 Y3632.200000000002
Go To X5537.200000000002 Y3632.200000000002
Go To X5537.200000000002 Y3225.800000000003
Go To X5537.200000000002 Y2768.600000000001
Go To X5537.200000000002 Y2362.200000000001
Go To X5537.200000000002 Y2768.600000000001
Go To X5994.400000000003 Y2768.600000000001
Go To X6096.000000000003 Y2768.600000000001
Go To X6096.000000000001 Y2362.200000000001
Go To X6096.000000000003 Y2768.600000000001
Go To X5994.400000000003 Y2768.600000000001
Go To X5994.400000000003 Y3225.800000000003
Go To X5537.200000000000 Y3225.800000000003
Go To X5537.200000000002 Y3632.200000000002
Go To X4267.200000000002 Y3632.200000000002
Go To X4267.200000000000 Y3657.600000000001
Go To X3048.000000000000 Y3657.600000000001
Go To X3048.000000000000 Y1828.800000000000

31 REPLIES 31
Message 2 of 32
john.uhden
in reply to: rpajounia

@rpajounia ,

Is that list of line coming from a .TXT file?  If so, we can easily read the lines and convert them to the format...

'((x1 y1)(x2 y2)(x3 y3) ... (xn yn)).

The fastest way depends on your processor(s).

So do you want to just connect the points in order, say with a new polyline?

The "fastest way through each line" is probably the same for each line because the processing doesn't care about its length (or the distance between points).  It's not like a pen plotter.

So I presume you mean the fastest method fof processing the data.

If you're talking about creating just lines from the list of points (say Plist), then the command method is probably the fastest:

  (command "_.LINE")
  (foreach P Plist (command "_non" P))
  (command "")
If you're talking about creating a LWPolyline, then there are three (3) methods:

1.  would be just like the Line command

  (setvar "plinetype" 2) ;; to create a LWPolyline
  (command "_.PLINE")
  (foreach P Plist (command "_non" P))
  (command "")
2.  would be to use the ACTIVEX method of vla-addlightweight polyline which requires specifying the space in which to create the object and converting the Plist into a variant, with which I have minimal knowledge but others here can explain.

3.  would be to create the simplest LWPolyline you can and then slam-dunking in the coordinate list:

  (setvar "plinetype" 2) ;; to create a LWPolyline
  (command "_.PLINE" '(0 0)'(1 0) "")
  (setq obj (vlax-ename->vla-object (entlast)))
  (vlax-put obj 'coordinates (apply 'append Plist)) ;; must be a flat list

 

I personally prefer #3, but time tests would reveal which method is fastest.

But there are people here much wiser than I who will probably suggest a few more methods.
 

John F. Uhden

Message 3 of 32
rpajounia
in reply to: john.uhden

So i have a cnc machine that cuts for me and it always starts at the same starting point, i need to tell it the most efficient way in going around the whole diagram with the least amount of crossing the same path twice

Message 4 of 32
john.uhden
in reply to: rpajounia

@rpajounia ,

That's a problem given a list of apparently random points.

How is any of us going to determine which point should connect with which?

This seems well beyond nesting.  There are no patterns whatsoever, or did I miss something?

John F. Uhden

Message 5 of 32
rpajounia
in reply to: john.uhden

I provided a lisp that has the plines and these points are the ends of all the plines

Message 6 of 32
Sea-Haven
in reply to: rpajounia

So this is another part of your nesting question ? Like John no idea what your dwg looks like, hint post dwg.

Message 7 of 32
rpajounia
in reply to: Sea-Haven

i attached the dwg in my initial post im not sure if you can see it there but here it is in a picture format and file, pretty much i start at the bottom left corner and need to find the fastest way through each line. starting point is always ( 3048, 1828.8 ) Screenshot 2024-01-18 224037.png

Message 8 of 32
Sea-Haven
in reply to: rpajounia

Only comment is sounds like spiral out from centre cutting lines. I don't know with CNC cutters if do outline 1st sheet will move ?

Message 9 of 32
rpajounia
in reply to: rpajounia

i have all the sheets being redone all i need is for it to figure out whats the best path without using too much pc power

Message 10 of 32
daniel_cadext
in reply to: rpajounia

A couple of options in Python if you’re interested. (see my signature)


1st, you might try Google’s OR tools. It has various routing solvers
https://developers.google.com/optimization/routing

I tried here, (function doit), but I don’t know how to add edge constraints, this is the shortest path though the collection of vertexes, which is not what you want, however you may be able to compute a very heavy weight if from_index and to_index are not on the same edge. PyGe.Point3d is hashable, so you can create an edge map with weights

 

2nd Networkx, has various graph solvers
https://networkx.org/documentation/stable/index.html

you may be able to build a graph and run it though their TSP solver. Again, using the heavy weight technique PyGe.Point3d is hashable so you can plug it with into their graph (function doit2) is dijkstra

Sorry, I can’t be more helpful, leaving for vacation

 

# import
import PyRx as Rx
import PyGe as Ge
import PyGi as Gi
import PyDb as Db
import PyAp as Ap
import PyEd as Ed
import traceback
import networkx
 
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
 
# define our command
def PyRxCmd_doit():
    try:
 
        db = Db.curDb()
        filter = [(Db.DxfCode.kDxfStart, "POINT")]
        ssres: tuple[Ed.PromptStatus,
                     Ed.SelectionSet] = Ed.Editor.select(filter)
 
        if ssres[0] != Ed.PromptStatus.eOk:
            return
 
        #this is the distance map
        locs = []
        for id in ssres[1].objectIds():
            pntObj = Db.Point(id)
            locs.append(pntObj.position())
 
        manager = pywrapcp.RoutingIndexManager(len(locs), 1, 0)
        routing = pywrapcp.RoutingModel(manager)
 
        def dist_func(from_index, to_index):
            # scale and convert to int
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            return int(locs[from_node].
                       distanceTo(locs[to_node]) * 100)
 
        dist_callback = routing.RegisterTransitCallback(dist_func)
        
        # Define cost of each arc.
        routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
 
        # Setting first solution heuristic.
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
        
        # you can change the algorithm here
        # https://developers.google.com/optimization/routing/routing_options#first_solution_strategy
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
        )
        
        solution = routing.SolveWithParameters(search_parameters)
        if solution:
            print_solution(manager, routing, solution,locs,db)
 
    except Exception as err:
        traceback.print_exception(err)
        
def print_solution(manager, routing, solution, locs, db):
    pnts = []
    index = routing.Start(0)
    while not routing.IsEnd(index):
        idx1 = manager.IndexToNode(index)
        index = solution.Value(routing.NextVar(index))
        idx2 = manager.IndexToNode(index)
        pnts.append(locs[idx1])
        pnts.append(locs[idx2])
    model = Db.BlockTableRecord(db.modelSpaceId(),Db.OpenMode.kForWrite)
    model.appendAcDbEntity(Db.Polyline(pnts))
   
def PyRxCmd_doit2():
    try:
        graph = networkx.Graph()
 
        filter = [(Db.DxfCode.kDxfStart, "LWPOLYLINE")]
        ssres: tuple[Ed.PromptStatus, Ed.SelectionSet] = Ed.Editor.select(filter)
 
        if ssres[0] != Ed.PromptStatus.eOk:
            return
 
        for id in ssres[1].objectIds():
            pline = Db.Polyline(id)
            pointList = pline.toPoint3dList()
            for idx in range(1, len(pointList)):
                graph.add_edge(
                    pointList[idx - 1], 
                    pointList[idx], 
                    weight=pointList[idx - 1].distanceTo(pointList[idx]))
 
        #make sure it's a vertex 
        sp = Ed.Editor.getPoint("Get start point: ")
        ep = Ed.Editor.getPoint("Get end point: ")
    
        path = networkx.shortest_path(graph, sp[1], ep[1])
        for idx in range(1, len(path)):
            Ed.Core.grDraw(path[idx - 1], path[idx], 1, 0)
 
    except Exception as err:
        traceback.print_exception(err)

paths.png

Python for AutoCAD, Python wrappers for ARX https://github.com/CEXT-Dan/PyRx
Message 11 of 32
Kent1Cooper
in reply to: john.uhden


@john.uhden wrote:

.... a list of apparently random points. ....


They're not random.  I made a single Polyline following them in order -- here is the sequence of them, including duplicate points and retracings:

path.gif

So the adjacencies in the list define where the path needs to go, preventing a result with [for example] diagonal connections such as in the lower part of the image at Message 10.  Or there might be other orthogonal arrangements that would hit all the points but not make all the right connections.

It's hard to imagine how to optimize a route when there are potential pieces of what could be the ideal [such as the closer-to-the-middle full-height vertical] that are not defined overall by any pair of adjacent points in the list, but are made up of pieces defined in different areas of the list entirely.

I don't have a suggestion, but I just wanted to point out that the points are not random, and the order of them in the list is meaningful and would need to be taken into consideration somehow.

Kent Cooper, AIA
Message 12 of 32
daniel_cadext
in reply to: rpajounia

It’s actually debatable whether this is the best method.

 

A, tell the CNC to take a shortest path through all the edges. But this will mean the machine must backtrack over certain paths. Depending on the material and the cutting speed, head repositioning may actually be much faster.

 

B, it’s not clear if all the outside edges need to be traversed I.e. if the blank is cut on a panel saw

  

Interesting though

Python for AutoCAD, Python wrappers for ARX https://github.com/CEXT-Dan/PyRx
Message 13 of 32
rpajounia
in reply to: rpajounia

sorry just got back to this. The main issue with TSP is its fastest route to each dot but i need the fastest route through each line. Does any1 have a script that they can write for me to help with this. I looked into the OR tools but thats a TSP solution

Message 14 of 32
john.uhden
in reply to: rpajounia

@rpajounia ,

I am not familiar with a CNC cutting machine, but I am with an Eastman vinyl cutting machine.  It makes sense to me that part of its path should be with a "pen up" rather than cutting twice or more over parts of the path.  Do you have control of that?  I'm guessing that your head doesn't travel as fast as the Eastman, thus the reason for minimizing the length of the total run.  It's too bad that AutoCAD doesn't provide for differing linetypes per segment, 'cause I was thinking that "pen down" would be continuous and "pen up" would be hidden (or vice versa) yet all part of the same polyline with 1 start and 1 end.  Actually, with "pen up" capability you could design a path that travels diagonally without cutting anything.  Am I close?

BTW, I thought this was related to your "Nesting" topic which I see you have rejuvenated.

John F. Uhden

Message 15 of 32
rpajounia
in reply to: rpajounia

so pretty much i can tell the CNC machine which way to go and if its up down left or right but im trying to figure out the best way to cut this unit that saves time in cutting while removing as much as overlay cut as possible

Message 16 of 32
john.uhden
in reply to: rpajounia

@rpajounia ,

My apologies for not being clear.

By "pen up" vs. "pen down" I didn't mean movement of the cutter in a positive or negative Y direction.

I meant if the machine can raise and lower its cutting blade along the Z axis (above or plunged into the material surface) as part of its instructions.  For example, swimming pool liner panels are mostly not rectangular, so the Eastman cutting head is automatically raised to get from the end of one panel to the start of the next, meaning no cut in between.

John F. Uhden

Message 17 of 32
rpajounia
in reply to: rpajounia

Ahh i see unfortunately it can not lift the cutter it needs to retrace what it has cut to get to another point

Message 18 of 32
john.uhden
in reply to: rpajounia

@rpajounia ,

I hope the machine is very accurate.  Otherwise it sounds like it might do a sloppy job.

Anyway, thanks for providing the clarification.

John F. Uhden

Message 19 of 32
Sea-Haven
in reply to: rpajounia

I dont do CNC but would you not make say largest pline is a rectang, then check if overlapping a side then pline becomes a 3 sided or 2 side object. Then like John if you can do a pen up it will not cut a precut line. 

 

SeaHaven_1-1712793884959.png

 

 

Message 20 of 32
john.uhden
in reply to: Sea-Haven

Alan,

Sadly, his CNC machine does not have "pen up" capabilities.

He said it would have to cut over previous cuts.

I wonder if Eastman has a cutter that can handle his material.  It would probably require only a bigger circular blade.

I wouldn't be surprised if every sailmaker used an Eastman.

I have a good friend I used to sail against.  He was invited to sail his iceboat in the 1980 Winter Olympics, but it was boycotted.  He used to be in some of those Chapstick ads.  He started his own sailmaking business (very popular on Barnegat Bay) and got acquired by North Sails, but I doubt they ever provided him with an Eastman before his back went out and he retired.

But I think their system requires dealing with bolts (rolls) of material.

But then again if the cut pattern is confined to a rectangular area then there's no problem.

But, again, they ain't cheap, but neither is a leaf blower compared to a rake, and neither is a nail gun compared to a hammer and nail set, and neither is a chain saw compared to a hand saw.  (Enough.  I think you get the idea.)

John F. Uhden

Can't find what you're looking for? Ask the community or share your knowledge.

Post to forums  

AutoCAD Inside the Factory


Autodesk Design & Make Report