I would like to draw a network that connects a set of specific points while following an existing street network and while following “the shortest walk” component.
(1) My first step is to create a Delaunay network between points to find out pairs of points (end and start points):
(2) I would like to transpose these paths into the real street network by using shortest walk. However I don’t manage to get all the paths, but only once per pair. Is there a way to do all pairs at once? I get this error message “1. The start and end positions are equal”
(3) I would like to store all the shortest paths and merge them to get one network that connects all points and follow the existing street network. Finally I will use a minimum spanning tree to ensure that the overall length of the network is minimized.
Your final goal is shortest paths between certain points? This seems like a complicated way to approach it.
What’s step #1 for? You seem to be adding diagonals not part of the original graph, which you would then have to figure out cost information for and then translate back to the real network.
Your points are sitting on an existing graph, so I would think you want to consider just adding them to the existing graph and modifying the path costs accordingly. Find the closest point on the existing graph (edge or vertex). If it’s a vertex, it’s already part of the graph. If its an edge, cut the edge and add a vertex, splitting the cost along the edge as appropiate (proportional to distance if that’s your metric.
The points you want to travel between are now part of the graph. Compute shortest paths, which it seems like you already know how to do.
Thank you for the reply! I want to create a network that connects a set of predefined points in a way that the overall network length is minimized (minimum spanning tree). This network needs to follow existing streets.
I have detailed below my process a bit better: 1. Delaunay triangulation of the predefined points: The output from this is multiple pairs of points connected by the Delaunay triangulation. (Euclidean distance) 2. Routing (what I am trying but fail to do in the example graph): I want to find the shortest path between each pair of points, taking into account the road network. This step outputs the real distance between the pair of points, including the geometry of all the shortest paths between the pair of points. 3. Remove edges of the initial street network which are not being used by the shortest paths of step 2. This outputs the “useful” edges of the original street network. 4. Apply minimum spanning tree to the “useful” street network to find the final MST network that connects all points and where the overall length is minimized.
I am now trying to do step 2 but don’t manage to compute all shortest paths at once.
If I understand you correctly, take a look at this and let me know what you think.
Not quite finished yet but you can see it in it’s current state.
-Need to have the starting points split the road network to make perfectly complete “path” possiblilities.
-This uses a modified C# script based on the work of @w.radaczynski from his Megrachne plugin component (currently only Rhino 8, sorry) you could use Megrachne components themselves to produce this, I just found it was easier in this case to combine it into one single component.
Thank you @PeterFotiadis PFotiad0! Unfortunately I don’t know C# so it’s difficult for me to reproduce such a logic.
@michaelvollrath: I am looking at ways to reproduce the A* component you have used in your logic using Megrachne plugin but do not get through “1. Solution exception:Index was outside the bounds of the array.”:
Is there another way to reproduce this step without Rhino8?
Thank you!
EDIT: I cleaned my street network better on QGIS to have smoother lines and ensured that all intersections have a point. Then reapplied your flow, but get the error message:
I came across this as well and couldn’t remember if it was user error on my end or if the Megarachne solver didn’t have logic in place for handling nulls/impossible paths. In the modified version I share we have the logic we need to hopefully not throw that error.
But in actuality I had some issue trying to set it up with Megarachne and it was a lot slower setting up the graph than the single component with the Megarachne logic combined inside of it and data tree access.
Here’s the same script but with the R7 C# script component so it should work in Rhino 7 now.
The R7 version is about 2 seconds slower in the A* solver but still works as expected.
In the Frankenstein C# component of your work, I switched it to Tree Access for this one since he has 52 possible starting points each with 52 possible paths to solve resulting in 2,704 unique paths to solve for
Since I need to also apply the minimum spanning tree to link all points (eg. see my initial post), I ended up with one more solution, using SpiderWeb component DataTreetoGraph, which allows me to allocate the real costs (road network) of each edge connecting pairs.
See below:
The process is a very clumsy though, because I need compute two times the shortest path component, which slows down tremendously the workflow when I look at larger areas… slow_solution_forum.gh (52.0 KB)
If I understand you correctly… You are grouping each possible point into its minimal spanning tree and then want to solve the shortest path within each MST, is that correct?
I guess my question is, why solve shortest path on the front end? Is this because the MST needs all possible connections first?
OR
Are you trying to create “waypoints” along a route, where you need to solve the shortest path from 0 to 1, then 1 to 2, then 2 to 3, continuing on until you’ve exhausted the waypoints within each MST list?
yes exactly (your first option) - I need to first compute the shortest path with the “real” road network to use the real costs of the paths when using the MST. Running a second time the shortest path is not really necessary but I could not find a more elegant way of retranslating the MST network back to the real road network.
in Megarachne the input for the A* component shouldn’t be a whole tree, but:
