Geographic obstructions in radius searches

Question

I am new here and points poor so I can only offer 50 pt bounty.

Suppose I have an application a search for all gas stations within 10 mile radius of a certain location. However one side of this location is surrounded by a mountain range that you have to drive 50 miles to get around. You would not want to return results from the other side of the mountain. What are some good algorithms/techniques to deal with such a problem? I know with point to point searches you can use path costs but I am not sure what the technique is with radius searches.

Here is an example:

The red line is a chord on the radius circle from 40,-74 to 41,-72 lat long (not accurate just saying) The user at 40,-73 performs a geographic radius search for something which also encompasses areas across the LI sound in Connecticut which are impractical to get to. The algorithm should know that there exists a chord completely intersecting the search circle and not return results that are on the other side of that chord. So only points in the green area would get returned.

This should be able to be done without any road network analysis if the programmer defines these bounding lines. For instance there may be an area in some country that is dangerous to pass through and you would want people on either side of that area to be restricted to that side. Or an international border etc. I am just asking this because I am pretty sure people are doing this.

Answer 1

Although the best solution would be to calculate distance along a road network (rather than straight line distance) using, for example, ArcGIS's Network Analyst, a dirty hack would be to create straight lines between the center of your radius and each station, then calculate the total elevation gain along that profile (a script for doing this automatically is given here). You could then set a threshold to reject those with total elevation gains higher than a certain value (those that you need to cross mountains to reach).

EDIT Since you seem set on not using network analysis, why not create a raster cost map in which the value corresponds to the difficulty of traversing that terrain? That could be based on other data (i.e. water bodies, elevation, landcover, etc.). Then you can either return the lowest cost station or do a select by attribute using the cost map...

Another option would be to create a polygon vector layer showing the impassable zones (mountains, water bodies, etc.) and then create a line between your location and all stations in the radius. Using select by location you can see whether that line intersects any of the impassable polygons; if it does, unselect the station.

The best tool for the task is still network analysis...

Answer 2

You should change your metric, what "near" then means. In your example 10 miles nearby meams 10 miles beeline. However, you might rather want to query for any gas stations, where the shortest street way path is not longer than 10 miles away.

You can also combine both approaches and first query all surrounding points and then filter them, i.e. by calculating the route lengths.

If you are more into the algorithms, I'd suggest you to have a look at pathfinding algorithms used for navigation assistants.