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.
