Finding minimum rectilinear distance paths in the presence of barriers

Abstract

Given a set of origin‐destination points in the plane and a set of polygonal barriers to travel, this paper develops an efficient algorithm for finding minimal distance feasible paths between the points, assuming that all travel occurs according to the rectilinear distance metric. By geometrical arguments the problem is reduced to a finite network problem. The nodes are the origin‐destination points and the barrier vertices. The links designate those node pairs that “communicate” in a simple way, where communication implies the existence of a node‐to‐node rectilinear path that is not made longer by the barriers. The weight of each link is the rectilinear distance between its two corresponding nodes. Solution of the minimal distance path problem on the network procedes in two steps. First, for a given origin or root node, a tree is generated containing a minimal distance path to each node that communicates with the root node. Second, a modified Dijkstra‐type iteration is utilized, starting with the nodes of the tree, sequentially adding nodes according to minimum “penalty distance,” where the penalty is the extra travel distance caused by the barriers. The paper concludes with a discussion of the computational complexity of the procedure, followed by a numerical example.