Shortest path in a multiply-connected domain having curved boundaries

Computing the shortest path, overcoming obstacles in a plane, is a well-known geometric problem. However, widely assumed obstacles are polygonal in nature. Very few papers have focused on curved obstacles, and in particular, for curved multiply-connected domains (domains having holes). Given a set of parametric curves forming a multiply-connected domain (MCD), with one closed curve acting as an outer boundary and several non-intersecting inner curves (loops) as representing holes and two distinct points SS and EE lying on the outer boundary, this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point–curve tangents (PCTs) and bitangents (BTs) using their respective constraints. A generalized region lemma is proposed, which is then employed to remove PCTs/BTs that will not contribute to the potential path and subsequently aiding in removing a few inner loops. The algorithm is designed to explore all potential paths. Merging of paths is also proposed to avoid redundant computations. A final SIP is chosen from potential paths using the length of each path. The algorithm also has the potential to give all paths of equal lengths contributing to shortest paths (within a tolerance level). As the algorithm computes all the potential paths on the fly, there is no need to employ a visibility graph to compute the shortest path. Curves are represented using non-uniform rational B-splines (NURBS). The algorithm uses the curves as such and does not discretize into point-sets or polygons. Extensions to handle curves with C1C1 discontinuities and SS and EE not on the outer boundary have also been described. Results of the implementation are provided and complexity of the algorithm is also discussed. This paper follows up the one presented for simply-connected domains (SCDs) in Bharath Ram and Ramanathan (2011) [4].

► This paper computes the shortest path for multiply-connected curved boundaries.
► The algorithm does not discretize the boundaries into points or polylines.
► No need to employ visibility graph to compute the shortest path.
► The algorithm can handle C1C1 discontinuities.
► Start and end points need not be on the outer boundary.