The shortest path in a simply-connected domain having a curved boundary

Given two distinct points SS and EE on a closed parametric curve forming the boundary of a simply-connected domain (without holes), this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. The SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents and bitangents using their respective constraints. They are then analyzed further to identify potential tangents. A region check is performed to determine the tangent that will form part of the SIP. Portions of the curve that belong to the SIP are also identified during the process. The SIP is identified without explicitly computing the length of the curves/tangents. The curve is represented using non-uniform rational BB-splines (NURBS). Results of the implementation are provided.

► Exact representation of the curve is used without approximating using sample points.
► The algorithm uses the point-curve and curve–curve tangent formulations.
► The algorithm does not require explicit computation of lengths of curves/tangents.
► The complexity of the algorithm is O(TlogT), where TT is the number of tangents.
► Implementation results indicate that the algorithm is very amenable for implementation purposes.