2
\$\begingroup\$

Usually you need path finding algorithms to find one or the best path between two points. Do you know if path finding algorithm where you don't know the destination point exists?

I have a graph made of thousands of nodes, I'd like to pick one, and tell my path finding algorithm "find a destination node that is at least at N units of distance of my origin point".

Is it a common problem? How would you solve it?

Thanks.

\$\endgroup\$
  • \$\begingroup\$ you'd rather pick all given nodes at distance == N and then apply pathfinding algorithm to get to a random one of them. \$\endgroup\$ – Leggy7 Apr 11 '16 at 19:11
2
\$\begingroup\$

Create an isochrone map (https://en.wikipedia.org/wiki/Isochrone_map), get a polygon of all the points accessible within N units of time.

An isochrone map basically looks like this (3 isochrones are represented in this example): enter image description here

Let's just focus on the red one, which takes a center point and a time (or a distance). Based on this time/distance limit, the road network is tested to find all destinations within this limit. This kind of map is often used in marketing/logistics as you can determine which of your customers/warehouse/whatever is accessible within X minutes, so that you can target a specific audience.

The result of the calculation is a polygon (the red polygon for instance, or red+yellow+green). Then by definition, every node which does not intersect this polygon will be at least N units of time away

There are multiple ways to calculate isochrones (or "isodistance" if you are working with distance limits), but this is a broader question. Also if you don't own the data, some web services will allow you to calculate isochrones worldwide.

The OP seem to have its own road network to work with, so an algorithm will need to be implemented to calculate the isochrone in the first place. The OSM wiki has some interesting links: OSM Isochrone

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you expand on this answer some more please? It seems pretty useful but the answer isn't totally clear (at least to me). \$\endgroup\$ – Steven Apr 12 '16 at 4:04
  • 2
    \$\begingroup\$ There you go, hope it makes more sense \$\endgroup\$ – fnicollet Apr 12 '16 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.