Fastest Way Through Every Line

[rpajounia]

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

[daniel_cadext]

As I mentioned above, IMHO, you should consider using a graph library.

Like network https://networkx.org/  , like in my python sample PyRxCmd_doit2

Even if you hack your way through it, the algorithms are fast.

It’s a cyclic graph, so I’d start with finding the longest cycle

simple_cycles

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles....

https://or.stackexchange.com/questions/9786/number-of-simple-cycles-on-the-graph

[rpajounia]

Unfortunately there is no penup situation. I think my best bet since my starting point is always the same is make a variation of all the possible routes it can take to visit all the lines and see which is the shortest route

[john.uhden]

@rpajounia ,

That way, my friend, is a daunting task in itself, but probably the correct answer.

How about if you remove the governor from the machine to speed it up? 🤔

When I was a youngster a friend lent me his 3hp outboard to use on my 8' pram (dinghy).

I bent back the governor and got that little boat up on a plane (no, not an aircraft).

[Sea-Haven]

Given no pen up maybe trace over with a new pline. Just try to minimize double runs. Use a bright color and say a width so obvious if a line is missed.

[john.uhden]

@Sea-Haven ,

Yep, often times the eye is better than the app.

[rpajounia]

i agree im currently looking into TSP and trying to see if there is a way to modify it to do plines instead of points and work with edges plus if its going from 1 point to another see if its a pline if its not a pline that has the same start/end points then use the shortest route function which i found a script for to get to that point but any help on this would be lovely

[john.uhden]

@rpajounia ,

Okay, I give up.  What is TSP...

• teaspoon?
• Thrift Saving Plan?
• Theatrical Stage Production?
• Tongue Sensory Perception?
• TriSodiumPhosphate?
• Tremendously Sharp Pencil?
• Torn Solar Plexus?
• Tough Spouse Proclamation?
• Tertiary Sewage Pretreatment?
• Temporary Sanity Psychosis?
• Terribly Stupid Pun?

WHAT?!

[daniel_cadext]

https://en.wikipedia.org/wiki/Travelling_salesman_problem

[john.uhden]

@daniel_cadext ,

I think that's like my ROUTE.lsp function I responded with some time ago, except as you pointed out, it doesn't allow you to visit any city (point) more than once.  In this case we may have to visit Peoria a few times just to get to Kalamazoo.

[daniel_cadext]

this is networkx TSP solver applied.  toggling the cycle flag

import traceback
from pyrx_imp import Rx, Ge, Gi, Db, Ap, Ed
import networkx as nx

def PyRxCmd_doit():
    try:
        filter = [(Db.DxfCode.kDxfStart, "LWPOLYLINE")]
        ssres: tuple[Ed.PromptStatus, Ed.SelectionSet] = Ed.Editor.select(filter)
        if ssres[0] != Ed.PromptStatus.eOk:
            raise Exception("Oops {}: ".format(ssres[0])) 
        
        G = nx.Graph()
        
        plines = [Db.Polyline(id) for id in ssres[1].objectIds()]
        for pline in plines:
            sp = pline.getStartPoint()
            ep = pline.getEndPoint()
            G.add_edge(sp,ep,weight=sp.distanceTo(ep))
            
        tsp = nx.approximation.traveling_salesman_problem
        tsppath = tsp(G, cycle=False)
        
        #Ed.Core.grDrawPoly3d(tsppath)
        db = Db.curDb()
        plPath = Db.Polyline(tsppath)
        plPath.setColorIndex(1)
        db.addToModelspace(plPath)
    except Exception as err:
        traceback.print_exception(err)
        

 

[rpajounia]

so pretty much your almost there just missing 2 lines from the diagram. i think the main issue is were cycling through end points instead of plines. See if there is a way to set a unvisited factor

[daniel_cadext]

Not using points, only edges. (G.add_edge(sp,ep,weight=sp.distanceTo(ep)))

I suppose it would be possible to create a map of the edges to find edges not traveled

I read the Depth First Search might be better suited.

https://networkx.org/documentation/stable/reference/algorithms/traversal.html#module-networkx.algori...

Got side tracked though