Multiple shortest walk

Replies to This Discussion

Permalink Reply by Hugh Groves on June 23, 2014 at 10:01am

OK playing with it I have come up with a definition that works. In the above problem I compare the SpiderWeb graph search to the normal voronoi. The answers are not the same :/ Is this because the graph search is effectively doing manhattan distance calcs? Is there a way to evaluate it as an actual distance?

Permalink Reply by Richard Schaffranek on June 23, 2014 at 2:00pm

Made my own file find attached.

Three things to remark (maybe you are aware of some of them):

If you have a quad mesh and turn it into a graph, it uses "manhatten distance" because the graph is a grid. So there is one part of the error. This you can overcome in making the mesh denser. Or don't relay on the mesh structure and connect the nodes also diagonal and over a larger distance than just to the neighbours defined by the mesh structure. This of course comes with the error that there might be errors if the mesh is not flat.

Second: SpiderWeb uses the drawing tolerance for calculation. So if this is set to large e.g.: to 1 and you have two edges one 1.5 meters and the other 1.9999 both will be viewed as 2 for calculations.

Third: You have to use the nodes of the graph from which you search from to generate the voronoi diagram.

However if you are familier with coding then I would like to point you to this example, it might make your definition way, way way, faster and gives you more options with SpiderWeb...

Scripting with SipderWeb

Any further questions are welcomed, and please keep us posted would be very very interested...

BEst Richard

Attachments:

• Mesh_VoronoiTest.gh, 15 KB

Permalink Reply by Hugh Groves on June 24, 2014 at 3:06am

I created a definition that linked the diagonals and this seemed to give a good approximation to the voronoi.

Might you be able to explain/share the single shortest path algorithm? My ideal would be to package up the entire definition below into a single component that I could share with my colleagues (and they not have to worry about all the details going on in the background!).

Attachments:

• 140623_test_3.gh, 19 KB
• 140623_test_1.3dm, 25 KB

Permalink Reply by Richard Schaffranek on June 24, 2014 at 6:19am

Well, it is basically a Dijkstra-Algorithm but with a few modifications:

First you can collect "all" shortest path, meaning that if you select this options the previous Graph sometimes has two or more possibilities in which you can walk. If you are only interested in distance this is without any concern to you + if you have a regular grid computation time will increase.

A further modification is that if a graph edge has +Infinity as cost, nodes discovered over this edge will not be used to search further and they are reached with the same costs than the nodes from where they where discovered. This was implemented for some things with the "dualGraphVertex" - Component.

Does that help? Or any other explaination?

And a further remark on the solution quality:

Since the distances are measured from a vertex point of the graph the points generating the Voronoi diagram have to be the same... 

Another remark:

Can't this be solved within the UV coordinate system of a surface? this would make things way easier and quicker. Or...

Maybe it would be a good idea to have a look at the wikipedia entry and the different proposed algorithms there?

Richard

 

Permalink Reply by Hugh Groves on June 24, 2014 at 7:14am

Firstly, thank you very much for your replies!

If I might take a moment to explain the purpose behind my project, my proposed algorithm, and then hopefully you may be able to appraise it and see any problems.

I am a structural engineer. One part of the design process is deciding how much of a floorplate an individual column supports. For something like a rectanglur floorplate this can be approximated with a voronoi diagram, where the rectangular boundary is the floorplate, and the voronoi nodes are the columns. However when we introduce irregular floor plates with voids the approximation is less obvious. One solution is to use engineering finite element software, however setting up the models can be relatively time consuming and not very reactive to change.

The benefit of spiderweb is that it only requires a mesh. That means appropriate areas can be assigned to columns for complex floorplates based on shortest walking distance.

I would like to package up the definition I have created above and use it as an input to some components that I have written that a user can use to assign loads to the floorplate, and thus work out the loads in the columns.
 I would propose:

Inputs

Surface (floorplate), points (columns), number (mesh density)

Output

Surface for each input point that covers its area

Process

• Construct quad mesh from input surface and density settings
• Extract lines representing mesh edges
• Add additional lines connecting corners of quads to get closer approximation of distance than 'manhattan'
• Turn into a graph
• Find vertex's on graph closest to input points
• Solve shortest path from each start point to every vertex on graph
• Compare distances to starting points for each vertex. Assign vertex's to start points based on minimum distance.
• Construct surface for each start point (I note that this is not trivial as they will not form convex hulls. I think the graph could provide enough information to find out which points lie on the boundary, then it would be a case of joining them to one another.)

Does this seem reasonable? One thing I am having trouble with is getting started with the SpiderWeb code. Could you point me in the right direction of functions that can replicate the components? Can the functions in SpiderWeb do most of the heavy lifting for me? Is there an equivalent function in SpiderWeb.dll that can do SingleSourceshortestPath and spit out lists like the GH component or would I have to reimplement it? Some more example code would be incredibly helpful.

Again thanks!

Permalink Reply by Richard Schaffranek on June 24, 2014 at 7:37am

Okay, now I understand... 

There are two dll that ship with SpiderWeb, the first SpiderWebLibrary.dll takes care of all the graph functions. The second GH_SpiderWebLibrary.dll extends them to incorperate things from Gh and Rhino.

All components that can be found in SpiderWeb Basic are related to methodes from GH_SpiderWebLibrary.GH_graphRepresentaions Namespace.

All components that can be found in SpiderWeb Tools can be found within the

SpiderWebLibrary.graphTools Namespace.

So to preform a SingleSourceShortest Path you would need to take a lock at SSSP class, which is derived from the searchGraph class. However if your edges are of equal length -> your floor area is subdivided in square then you could also use BFS class, which is as well a derived from search Graph class.

I think this example will give you a good introduction:

http://www.gbl.tuwien.ac.at/_docs/GrasshopperScriptum/lib/002_Spide...

Something to mention: all algorithms work in 3d so it should be possible to considere multible floors at once.

Richard

Permalink Reply by Hugh Groves on June 25, 2014 at 8:29am

Thank you for the help, that was enough to get me started. I have made an attempt at combining some parts of the code into one C# component. It attempts to: create graph from line, determine which vertexes of the graph are closest to the input points, determine shortest path to every node from each of them, output answers.

I get results which look alllmost right, however they are slightly different to the ones I get using SpiderWeb components (which I feel match the voronoi better). Would you please be able to take a look at my code and correct my mistakes please?

Attachments:

• 140625_coding_test_1.gh, 24 KB
• 140623_test_2.3dm, 35 KB

Permalink Reply by Richard Schaffranek on June 25, 2014 at 9:15am

As suspected:

The problem was the tolerance setting, As with the inprecition of floating point number representation SpiderWeb uses tolerance setting, normaly they are taken from the rhino.document in the components, when scripting you have to set the tolerance.

Attached a file.

p.S.: had to make a slight change because the upcoming version will has some different outputs..

Attachments:

• 140625_coding_test_1.gh, 34 KB

Permalink Reply by Hugh Groves on June 25, 2014 at 9:48am

Ah-ha I see my mistake. Thank you for the help.