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 peter fotiadis on April 6, 2017 at 12:12am

Well (V1C is required ASAP) ...

... this means simply:

(a) Sync (Array or rather better Dictionary) sort the possible candidate pts pairs (mid edge + closest pt on path: these yield candidate paths (center pt is common so forget it for the moment)).

(b) Then for each pair/line (mid edge - closest pt) check for Curve/Curve intersection events (like in the image of yours) and if events != null > check the next pair/line > until a null intersection event occurs (Karma is a must).

Easy to correct I must say.

BUT ... for the left most building in the above image (L shaped) the yellow route intersects the neighbor building ... and that is 100 times more challenging to address properly.

Moral: I hate computers

Permalink Reply by peter fotiadis on April 6, 2017 at 6:39am

And here's the reason why I hate computers (plus .NET, .NOT, .WHATEVER etc etc):

Circle = edge mid point

Rectangle = path closest to circle

Triangle = CoG

Cyan is Ok

Yellow (given the cyan) yields a variety of solutions and the most reasonable is the one that violates the mid point rule (life sucks).

Yellow (given the cyan and magenta) yields only one reasonable solution that MUST violate the mid point rule (life sucks).

Moral: Life sucks (plus: I hate computers and captcha)

Permalink Reply by Anders Holden Deleuran on April 6, 2017 at 1:08am

Side note: There are also other/similar algorithms (such as the straight skeleton) that may be more performant/stable depending on the input data. A former colleague of mine implemented the CGAL library in C++ and it was certainly wildly performant compared to anything I came up with in RhinoCommon/GH ;)

Permalink Reply by peter fotiadis on April 6, 2017 at 1:25am

Indeed.

The only real-life usage of the Voronoi skeleton approach (in cases like this) is when you have some irregular areas (say: some connected green areas/parks with no pathways) and you want absolutely to find/work with skeleton/medial stuff.

But when in a "free" park the medial axis has very little sense anyway. A Dijkstra routing on random points could be visually way more "realistic".

Permalink Reply by ShynnSup on April 13, 2017 at 11:10am

Anders, that paper is really insightful. I think I am trying to achieve something similar.

About the script you attached, I haven't been able to make it work... I copy the text to the py gh component and >> appear in my command bar in Rhino, but I cant select any surface. Any ideas?

Permalink Reply by Anders Holden Deleuran on April 14, 2017 at 2:55am

That file is just the Voronoi library I implemented in my MedialAxis2D GHPython component (as I was having precision issues with using the GH Voronoi library).

Permalink Reply by Anders Holden Deleuran on April 6, 2017 at 7:27am

The two papers I linked to might clear up some of these questions, might ;)

Permalink Reply by peter fotiadis on April 6, 2017 at 7:42am

Well Tom

Some puzzles are indeed invented for nothing but some others not so: For instance differentiate a bit from finding the route/walk to Paradise from building N666 to N66 and think some other "similar" puzzle:

For instance if you use some "space syntax" to solve some topology (correlating classic room schedules/adjacency matrices/etc) by what means can you validate a given solution (out of N) with regard the "economy" of all walks? (for a house: utterly pointless, for a big hospital not so).

But truth is that getting lost in translation is tres a la mode these days.

Permalink Reply by ShynnSup on April 6, 2017 at 7:34pm

Peter, thats incredibly smart!

The mid point rule can totally be violated for these purposes.

Permalink Reply by peter fotiadis on April 6, 2017 at 11:46pm

I was ready to post the wonder thing (using a new complex recursive Method: ValidateLinkAndBeAHappyBunny) ... only to discover that other rules must violated as well > update > ValidateLinkAndBeAnUnHappyBunny.

But other rules discovered as well > upgrade > ValidateLinkAndBeAMiserableBunny.

Permalink Reply by ShynnSup on April 11, 2017 at 3:38pm

Peter, with the geometry Im working with (surface and boxes position) it should be posible to have all shortest paths without them crossing the boxes. So no worry about creating a scrip that works globally. The geometry copies an existing building so in theory it should be possible to access each box without having to go inside a box to get to the other one.

Permalink Reply by ShynnSup on April 11, 2017 at 3:41pm

I belive that having the medial axis is much more accurate than drawing a path by hand. At least the medial axis is a sort of average of all the possible paths across that hall way.