Least Cost Path on Mesh Python Script with NetworkX

Being able to use Python in Grasshopper opens up Grasshopper to tons of excellent scientific computation and simulation libraries, including NetworkX.

Using NetworkX for the first time, I was able to translate the topology of a Rhino Mesh into a NetworkX Graph object, and then I used a custom function to weight the edges between nodes. In this case, the weight between any two mesh vertices is the distance multiplied by the difference in height, causing a least cost path algorithm to find the shortest, flattest paths between two points.

The python code can be viewed here:

https://gist.github.com/1057297

▶ Reply to This

Replies to This Discussion

Permalink Reply by Boris Rüther on July 2, 2011 at 3:46pm

really interesting work!

thank you for shareing it!

▶ Reply

Permalink Reply by Aito Maui on April 7, 2012 at 10:32am

Hello Benjamin,

First, thank you very much for sharing thoses very interesting definitions.I was trying to make a definition with the same goal without sucess, and was realy pleased to discover your script.

But I am encountering a problem when the point choosen on the mesh are too low. The path calculated seems to be atracted toward the firsts (origin)points of the mesh. As soon as i choose higher points it works perfectly. Any idea how i could fix that ?

Cordialy

Maui COJAN

Attachments:

Pme SW.jpg, 545 KB

▶ Reply

Permalink Reply by Benjamin Golder on April 9, 2012 at 6:41am

Hi Maui,

It depends on what you used to input the indices of the mesh points for the from and to nodes. Can you post a screenshot of your grasshopper definition, and how you set up the inputs?

Best,

Ben

▶ Reply

Permalink Reply by Aito Maui on April 18, 2012 at 7:41pm

Thank you for your answer Benjamin.

Here is how i set up the inputs.i tried to find the (from and to)nodes by moving closest points.

tell me if you prefer to have the 3dm& ghx files.

Best

Maui

Attachments:

inputs.jpg, 416 KB

▶ Reply

Permalink Reply by Benjamin Golder on April 21, 2012 at 6:52am

When you create the delaunay mesh, then the mesh will have it's own internal order of points. In order to use an index that correctly corresponds to the order of the points in the mesh, you need to get index numbers from the mesh vertices.

When you create the delaunay mesh, it will not retain the same order of points.

Try using a mesh vertices component to get the index of the vertices you want to use from the delaunay mesh.

▶ Reply

Permalink Reply by Benjamin Golder on March 26, 2013 at 9:00pm

You can use weaverbird components to get all of your mesh edges, and then filter out the edges that don't match your criteria.

Once you do that, if the answer is not so obvious, then use the remaining edges to make a new mesh and run that through network x. Also, feel free to edit the code and use anything you like as a weight function.