[R-sig-Geo] Shortest path around obstacles (OT)

[Don MacQueen]

This question is basically off topic, since it isn't truly an R 
question, though it is certainly related to r-sig-geo. I ask here in 
the hopes that someone can suggest a direction for me to look.

I have a what is essentially a floor plan of a building (lines 
representing walls, breaks in the lines representing doors, and so 
on). I would like to have an algorithm that can calculate the 
shortest distance between any two points (actually, large numbers of 
pairs of points) that does not intersect any line (pass through any 
wall).

My real dream is to use these distances instead of Euclidean 
distances as input to a gaussian random fields algorithm such as 
those in the RandomFields package.

I've done some web-searching for libraries of geometric algorithms 
that might include this task, and have come across references to 
Dystra's algorithm, and some mention of line of sight calculations, 
as well as some algorithms for robotics (how the robot finds a path 
from here to there, passing around obstacles represented as 
polygons). So I have some leads.

None the less, I'd really appreciate any suggestions from the folks 
here on R-sig-geo.

Thanks
-Don
-- 
---------------------------------
Don MacQueen
Lawrence Livermore National Laboratory
Livermore, CA, USA
925-423-1062
macq at llnl.gov