Efficient computation for continuous Hausdorff and average Euclidean distance between polylines

Polyline distance metrics provide a foundation for geospatial analysis tasks ranging from trajectory analysis and movement tracking to assessment of multiscale geospatial databases. Two commonly discussed metrics in these contexts are the maximum (Hausdorff) and average Euclidean distance. However, implementations of these metrics between the continuous paths defining polyline features are lacking. Instead, distances between discrete sets of vertices or between one set of vertices and another continuous polyline are typically computed, often without acknowledgment that these are imperfect approximations of distances between two continuous polylines. This paper reports on an algorithm and functioning code implementation to accurately compute the planar 2D Hausdorff and average Euclidean distances between continuous polylines by traversing one polyline and integrating the continuous distance function to the other. Code accuracy and robustness are verified against 50 synthetic test cases, and application to typical cartographic features is used to assess computational efficiency and to quantify errors associated with commonly used approximations. Results indicate loglinear efficiency with input polylines following similar trajectories. Compared to the true distances, commonly used approximations were found to produce errors of up to 36% and 160.7% for Hausdorff and average Euclidean distance, respectively. Given similar computational efficiencies, continuous polyline distance metrics are recommended over discrete approximations to avoid errors.