Starting in December, we will archive content from the community that is 10 years and older. This FAQ provides more information.
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
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
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
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
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 )
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 ?
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)
@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:
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.
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
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
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
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
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
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
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.
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.