Help! Shortest walk from points to curves

Grasshopper
, , ,
#1

HELP: How to find the shortest distance from the selected point clouds to curves, without hitting the buildings?
I have drawn a simple diagram. The shortest distance from point A to curve should be the blue line (B) without consideration of the C-shaped building. I simply wish to get the red line ( C ) as the shortest path which takes building into account.

all
all1451×816 12.8 KB

The current ‘pull-point-to-curve’ battery can calculate the blue line, but not the red line. I’m desperately looking for the solution.
Many thanks!
gh
gh782×321 25.7 KB

shortest walk.3dm (175.8 KB) shortest walk.gh (4.4 KB)

#2

Hi Kyle,

I don’t think something like this is included in Grasshopper. Maybe one of the pathfinding plugins like Mouse can help you?

#3

Thank you, Pierre, for sharing the Mouse function, and I find it is interesting. However, Mouse only calculates the shortest distances between points and points, rather than points to curves.

The difficulty of my task lies in an uncertain destination, unlike the route algorithms in google map. Trying to imagine the green line in my diagram as a seashore, we need to find the shortest travel to the coastline, regardless of which point on that coastline. The destination on the curve will move once redirected by the building corners.

Some people suggest me to combine the ‘curve closest point’ battery with the ‘shortest path’ battery. The first step is to pull all points of building corners to the targeted curve. The second step is to generate all the route options by linking all the points of building corners. The last step is to find the shortest path between the starting point to the first turning point around the building corner. The three steps will provide the route network. Before running the shortest path battery, many routes hitting the building need to be filtered out.

I consider their suggestion, but still, worry about the huge computation tasks if there are thousands of hundreds of input of starting points, building corner points and curves.

Desperately looking for fast computation algorithms, I’d appreciate it as fast as ‘curve closest point’!

#4

These kind of problems -almost- always end up in the answer to the question “how much tolerance you are willing to accept in your results” :slight_smile:

One possible way to attack this problem would be to [over]simplify the “world” on which the agents on “start point” can wander:
usually you want to create a virtual 2D grid of points, all points connected with their adjacent ones in a graph, then the agent starts exploring them until it finds the “end point”, for each node it leaves a trail indicating the node it came from
now that you have “mapped” all the possible nodes, the strategy is to start from the end point, and revert back your path to the start point using the trail left on each node
this is time consuming :slight_smile:

this is just a random thought:
let’s say that we reduce a bit for our agent the possibility of moving, in such a way the are always forced to move only on the corners of the obstacles
this would for sure reduce the possibilities to be computed, but would also offer no solutions like A (which is the real shortest path) in the following picture: it will always with B

for each corner in each building there would be one and one only arrival point on the final green curve

image
image1188×764 7.71 KB

in my mind, the graph could look like this:

image
image1219×767 13 KB

#5

Just spotted that one (while the penultimate F1 race is under way [Lewis got Covid => meaning: forza George]).

Is not a question of tolerance (but is a question of recursion if multiple footprints are around [that option is internal and thus is not included in the attached]).

Path_FromPoint_V1.3dm (27.7 KB) Path_FromPoint_V1A.gh (124.0 KB)

#6

Thank you, Peter, for making effort and sharing such an interesting solution!

I have worked out a simplified method using ‘pull points’ + ‘shortest walk’.

:slight_smile:

#7

Thank you Inno!

You are absolutely correct that we have to find the tolerance.

I just figured out a method. However, ABM must be used if the input points, buildings and destination curves are multiplied to thousands.

:slight_smile:

#8

Dear all,

Thank you for your answer.

I have been supported by many of you. A massive thank you for the technical support from Grasshopper rhino FB group (https://www.facebook.com/groups/391624721004814/?multi_permalinks=1935034386663832&comment_id=1935563006610970&notif_id=1607094442885541&notif_t=feedback_reaction_generic&ref=notif).

Here I attached the grasshopper code and rhino files.

shortest_walk_around_obstacles_from_points_to_curves.3dm (168.7 KB) shortest_walk_around_obstacles_from_points_to_curves.gh (34.4 KB)

It took four minutes to visualise the shortest walks from 2500 points to three curves, with 10% being obstructed by nine building blocks. Hopefully, it can be applied to denser urban fabrics.

simplified_wire
simplified_wire1574×836 291 KB

#9

Well (the thing attached maybe needs some direct vision points to start as well) .See attached (as a hint).

Path_FromPoint_V1_SupplementStartPoints.gh (11.1 KB)

Update: In fact the straigh vision approach is the fastest (and better) way to go using classic resursion as follows:

Screen Shot 081
Screen Shot 0811682×632 168 KB

Screen Shot 080
Screen Shot 0801655×624 173 KB

  1. Define a bool array (say: named sampled) the size of footprint points (i.e. polyline.Count -1). In fact for many footprints you’ll need a bool [ , ] array.
  2. Define 2 public DataTrees (say: routes, routesIndices) for holding the recursive candidate paths as points and as indices. Define 2 public Lists (say: searchPts/Indices) for feeding the recursion (per loop) with search points/indices. Prior invoking the recursive Method add the actual start point to the searchPts.
  3. When in the recursion define 2 new tmp Lists (for points and indices) that would contain the next Loop search content. Loop all points in searchPts: for a given point get the straight vision pts/indices List ( as exposed in the supplement demo) THAT ARE NOT sampled and check if any pt yields a straight hit (if yes, update the routes Trees).
  4. From min (first) to max (last) index set the sampled array true. Sample the first and the last index into the equivalent tmp List. For instance in the last pic the only way to exit the local pocket is via the 2 yellow lines (indices 8, 23).
  5. Replace the searchPts/Indices with the equivalent tmp Lists and go to the next Loop (if no pts found terminate the recursion).
1 Like
#10

I’m thinking galapagos. Take your line, curve divide that line,curve, create a line from your start point to every point on the curve. Use galapagos to find the shortest distance. Create a penalty for an intersection with the building. This will give you the shortest line without going thru the building. Repeat using points on that straight line as vertices for a polyline. Just a thought…
Bill

#11

Here is a starting definition. Not quite perfect but it is a starting place.I broke the galapagos solving evolution into a couple of steps in attempt to not overwhelm it, however you can see that it does not return the “perfect” result. That is all of the time I have to noodle this. Let me know if this helps
BillShortest walking v1.gh (20.0 KB)