I have used “the traveling salesman” algorithm to get the optimale order to connect the points for get the shortest route along this network of curves marked with black lines:
I need to connect the points but only by using the network. Any ideas on how to do this?
I have tried using these packages but to no avail: Topology, VASA, LunchBox and Refinery.
I don’t have your model and I’m using sandbox version of Dynamo - so this below is something to try, however it may not work - not sure if Topologic Vertex translates to a Dynamo vertex so have done alternative.
I just tried you solution, but it only connects the start/endpoint to the curve network, not all the others. The red line is the outcome from your idea. Thanks for the idea, i will keep trying working in that direction to see if i can find a working idea
Do you have a simplified model you can construct in Dynamo directly? If not can you put a Data.Remember node on canvas to serialize the geometry into the dyn? Or post the sample model?
Have you deleted everything that isn’t needed (i.e. all but one new 3d view, all view templates, every material, most families, etc.) and purged unused (in a detached model if that wasn’t clear)? Perhaps build a simplified model with less content in it to allow a generic way of illustrating the point? If that still doesn’t get things small enough, youc an use a 3rd party site for file sharing such as box, dropbox, onedrive, google drive, wetransfer, etc… Just be sure the link is open to anyone who might want to help.
I have come pretty close now, i had a problem where the points weren’t place perfect on the wire network, which i now have fixed. Now i just need to find out why two of the six points does not work:
Seems like you’re making this extra hard on yourself.
VASA to get the shortest path from each point in a series to every other point. You then remove all the point structures in favor of building a new set of paths which are no longer connected, so your data structure is shot. I don’t understand why. You then try to rebuild the nurbs curves, but as they no longer intersect you’ve had to extend them all in the hopes of making them reconnect again, but now you have start points which don’t reside on the paths so topologic won’t work again.
A copy-pasted traveling salesman tool to get the shortest sequence among a series of 2D points. Not sure why as your paths aren’t necessarily 2d straight so you can’t use this in reality anyway; your ‘sequence’ needs to be weighted by the length between points, not the nearest distance. Also your points aren’t on the curve network (see #1), and your order is something like “entrance point, exit point, door 3 point, door 4 point, door 1 point, door 2 point”. I’m pretty sure the exit wants to come last based on series.
Topologic to get… actually I’m lost by the time you get here, but I think you’re trying to get the least amont of travel path between the points found by the traveling salesman sequence?
I feel like it’s I’d go about this in a different way entirely.
Build the VASA model as you were before.
Flatten the list of points from the path network and prune any duplicates.
Get the start point of the first path in each path group of paths from your path points. This will be the entrance, doors 1-4, and exit point (assuming you have 6 groups based on what I am seeing for list structure, but you’re missing a remember node so I am not sure).
Build a cell from each point, and use those to build the wire network for topologic.
Build the minimum spanning tree from the cell network that connects the points (from step 3).
That minimum spanning tree is the ‘least travel distance possible’ to access all the points of interest (entry, exit, doors).
2) Build the minimum spanning tree of the path network
Thanks! I will be trying to build this up with your suggestions.
I will admit that it has gotten a bit out of hand, and since posting, I have tried to simplify it because I have noticed some of the issues you pointed out. This is by far the most complicated I have gotten with Dynamo, so I really appreciate the feedback.
You are correct in assuming I am trying to get the least amount of travel path between points. My logic (which is really flawed) was that if I set the shortest path node lacing to cross product and made that my network of curves to be traveled by, I would be able to get the overall shortest path between all those points (if that makes any sense).
Once again, thank you so much. I will be trying a different approach.
Vasa_version_V2.dyn (1.3 MB)
I have done a lot of cleaning up an trying to use your approach, though i did not understand what you ment by “Build a cell from each point”.
I think it looks and works much cleaner now, but i still have an issue with the Graph.ShortestPath node…
Shortest path isn’t relevant as you don’t know the order of the points; you just want the minimum spanning tree instead. I know it’s been done with topologic before but I am not sure where it is offhand. Look for that shortly.
First look for how to build a graph from a series of cells instead of a series of curves. I believe the demo files for Topologic include such an example.
Thanks for the help so far, i have applied the minimum spanning tree instead. I found the sample file from Topologic’s own website, and have applied the python script from that one to my own now.
I think the poblem i got now is that in the sample file the edges is compiled as one edge and mine is multiple edges and i cannot figure out a way to make them one.
The python node in my script works in the samplefile.
I think you need to take the curves from the polycurves, then join those into one flat list, then build topologies from the flat list of lines, then build a wire from the resulting edges.
There needs to be a rethink on the method - Lets review
You have a series of points, and travel paths. Each of these paths have a length.
So now we have all the components of a graph - nodes, edges and weights
Instead of removing duplicates by length it’s likely better to group the curves by start and end point, sort the groups by length, and take out the first one. Fairly easy to do with in Python with a defaultdict object. Better still is to only produce on path per point pair and reducing the number of paths which you build with VASA as when you pack enough paths in you wind up with a bit of a conundrum. This is a concern as if we have doors evenly spaced in a sequence the paths will have matching lengths between each door and you’ll only keep ‘one’ of the paths right now. Edit: Here’s a sample showing how to reduce the paths you calculate to the minimum in VASA using only OOTB list management:
The one issue I have with this is that the dataset is ‘nice’ in that few if any paths overlap each other. When they do the graph fails to create as you get multiple edges at each centroid so you can’t associate the weights to the graph.
Personally when I’ve run into this type of problem I have just permutated the interest points list and joined the entry point, interest points and exit point into one list, and then built the paths in sequence. Get the length of all the paths and set that as an output. Then we move to Generative Design. From there I let GD find the ‘optimal’ permutation. This works well for up to about 20 interest points.
I like this better for a few reasons:
As any graph can have multiple minimum spanning trees you might want to select one of those over the other.
As the ‘traveler’ has to ‘walk backwards’ on the MST the reported length of the MST doesn’t necessarily ensure the minimum travel distance or illustrate ‘two way’ streets which are less effective than ‘one way’ streets.
It’s less problematic across versions as you only have to fight VASA (working from 2.13 to 3.1 for me) instead of VASA, Topologic (haven’t tested post 3.0), and Python (last I checked the Python in the Topologic MST node requires IronPython2 which is problematic as it’s WELL outside of the support window).
Generally, from experience using the built in path tools works for escape routes and fire hose range. I’m looking at this as an exercise to improve the current graph.
If I were to do this I would use python and NetworkX which can use any hashable object as a node, digest all the start/end points and lengths in one go. Then you have the full library of algorithms to slice and dice the graph. (After processing in VASA, of course)
Apropos of nothing, here’s shortest paths
Jacob, I have tried using your idea for the path model to create fewer curves to be analyzed, and it works. Thank you for the help from the start.
Mike, I have tried setting up your suggestion, and it works fantastically. I tried shuffling the points around to different locations, and that works as well. Thanks.
I’m not at my workstation at the moment, you could load the polycurve path into the edge dictionary say with ‘path’ key and grab it from there to make things easier Edit Unfortunately Topologic dictionaries can’t hold arbitrary values
