Shortest Walk Across Planar Surface

Hello everybody,

Im currently trying to find the shortest walk/path along a surface to the center of polygons adjacent to this planar surface.

I am aware the shortest walk component uses a network of curves to work, but I got nothing like that in this option. Just a starting point, where to go, and along where to move.

I dont know.... is it even possible?

Im uploading the internalized geometry if anyone is willing to try.

Thanks for any ideas.

Shynn

Edit: Doing some digging I found this thread about extracting the axial curve of a 3D mesh: http://www.grasshopper3d.com/forum/topics/code-to-extract-center-cu...

Obviously this is much less complex as its just a planar surface. Hopefully this will illustrate better what Im trying to do.

Attachments:

Geometry2.gh, 144 KB

Replies to This Discussion

Permalink Reply by mark zirinsky on April 2, 2017 at 8:23pm

So, generate your networks of curves, and apply shortest walk. you could generate the network several ways, by hand, closests points compnents, and so on. You already have the centroid points. Pick a stating point, and where to go and where to move to limit your curves.

best

Permalink Reply by mark zirinsky on April 2, 2017 at 8:39pm

takes the list of points, flatten it, use the closest points component, then feed into shortest walk

Permalink Reply by ShynnSup on April 2, 2017 at 8:50pm

Mark, Im not sure I understand completely, I would still be needing a curve network.

Permalink Reply by Pirouz Nourian on April 3, 2017 at 11:19am

Hi Shynn, the network will be relatively big, consisted of about 1000 nodes. I can recommend you to use Cheetah tools, the latest version, for finding such shortest paths. Cheetah actually finds the easiest paths, that are easier to navigate compared to shortest paths. I view the surface in your file as a network of streets (corridors in reality) and model their network as below:

I can share a code snippet on Cheetah forum to make such networks. But there are problems to solve as in the left side of the image below:

Permalink Reply by ShynnSup on April 3, 2017 at 12:10pm

Pirouz, thats great!
I will definitely look into this add on. Indeed the idea is to generate a mid curve that goes across the surface and then use this as the curve network. It would be ideal if this curve could be more regular, like an offset or a scale of the boundry curves. But still thank you for your suggestion!

Permalink Reply by peter fotiadis on April 4, 2017 at 1:15am

Given the opportunity and theoretically speaking (since coding is required) other than using the Cheetah tools (I'm not familiar with these - mind) you can do that:

Either using some shortest route algorithm on a grid OR a grid of "street" points.

Or using classic Dijkstra routing (either on random prox line graphs in the streets + the parcel points or ... as you said ... using central spines ["mid" polylines] + the parcel points). That said Dijkstra type of solutions range from slow to very fast depending on the approach on duty.

For the "generic" Dijkstra case shown and for your specific requirements one needs some additional filters in the line graphs used (exclude lines that intersect the inner brep loops AND connect a given parcel point only to the closest random street point).

Anyway ... theoretically speaking.

Permalink Reply by ShynnSup on April 4, 2017 at 7:01am

Thanks Peter for your input!

I think the first method of dividing the surface into a grid of points ends up generating something like what Pirouz proposed, but it might just work with native components. The only thing needed would be to connect each point to generate a grid of curves. Im not so sure the Dijkstra routing might work... and it does not seem accurate enought in terms of efficient circulation.

My latest approach is simply trying to generate the medial axis of my surface.

The only problem right now is that my surface has "islands" or holes.

I did find a site that seems to have gone further into the definition of medial axis making it able to compute Genus shapes, but the download link seems broken...

https://codequotidien.wordpress.com/2011/11/17/medial-axis/

Permalink Reply by peter fotiadis on April 4, 2017 at 10:34am

Holes eh?

Like the "The Lord of Darkness" ?

BTW: The attached (A hybrid: a primitive C# + native components) is a rather naive implementation of the medial axis (aka: skeletonization (LOL), aka: tunnel center line) problem. The primitive C# (that does proportional divisions taking into account a given curve length VS the minimum length [the N is related with that minimum]) checks for curve contains curve conditions BUT NOT for nested containment (for instance the out boundary VS "e" VS the inner loop of "e"). If you need nested stuff there's a solution available on that matter but without native components.

BTW: Given a medial axis line graph the only thing that you need is to add lines from each parcel center to the closest node (well that's easy or nightmare depending on the topology) and ... then ... use a fast Dijkstra algo for the routing (but that requires advanced coding) - where "cost" node to node is the node to node distance (or any additional condition like: this portion of the graph is reported as dangerous at night, that has dogs that bite hard etc etc etc).

BTW: Other than that ... I would strongly suggest this (all times classic) book if you are after ... er ... mysterious/freaky/weird/whatever things:

Attachments:

Medial_Axis_V1A.3dm, 111 KB
Medial_Axis_V1A.gh, 126 KB

Permalink Reply by peter fotiadis on April 4, 2017 at 10:55am

Additionally ... well ... if your city is a real-life one you'll need a non planar Voronoi (As attached curves must lay in Plane.WordXY).

NOTE: If no medial stuff is around gradually increase N having always in mind that the N value affects the divisions on the shortest INNER loop curve (the rest are proportionally computed).

Permalink Reply by peter fotiadis on April 4, 2017 at 11:21am

And since all these things are more or less LOL I've added the round option that does LOL stuff.

Attachments:

Medial_Axis_V1B.gh, 131 KB

Permalink Reply by peter fotiadis on April 4, 2017 at 1:13pm

BTW: Reviewing this (using the strictly internal C# version) I recon that some lines of C# are required ASAP: getting rid of "tiny" lines and greatly simplifying the medial stuff and sampling into Lists of polylines (between open nodes and/or nodes with higher than 2 valence).

Easy ... but if I use Sandbox for the line graph connectivity trees and the likes ... that thing yields some freaky/faulty results: see node 11 (from Point to point connectivity) that reports that point 11 is connected ...er ... with itself (life sucks: but nothing serious, just another check is required).