Efficient measurement of continuous space shortest distance around barriers

Abstract

There are many different metrics used to estimate proximity between locations. These metrics are good in some situations and not so good in others, depending on permissible movement behavior. A complicating issue for general metrics to accurately reflect proximity is the presence of obstacles and barriers prohibiting certain directions of movement. This paper develops a continuous space-based technique for deriving a guaranteed shortest path between two locations that avoids barriers. The problem is formalized mathematically. A solution approach is presented that relies on geographic information system (GIS) functionality to exploit spatial knowledge, making it accessible for use in various kinds of spatial analyses. Results are presented to illustrate the effectiveness of the solution approach and demonstrate potential for general integration across a range of spatial analysis contexts. The contribution of the paper lies in the formal specification of the problem and an efficient GIS-based solution technique.

Keywords:

• optimization
• convex hull
• Euclidean distance