Polyline approach for approximating Hausdorff distance between planar free-form curves

This paper presents a practical polyline approach for approximating the Hausdorff distance between planar free-form curves. After the input curves are approximated with polylines using the recursively splitting method, the precise Hausdorff distance between polylines is computed as the approximation of the Hausdorff distance between free-form curves, and the error of the approximation is controllable. The computation of the Hausdorff distance between polylines is based on an incremental algorithm that computes the directed Hausdorff distance from a line segment to a polyline. Furthermore, not every segment on polylines contributes to the final Hausdorff distance. Based on the bound properties of the Hausdorff distance and the continuity of polylines, two pruning strategies are applied in order to prune useless segments. The R-Tree structure is employed as well to accelerate the pruning process. We experimented on Bezier curves, B-Spline curves and NURBS curves respectively with our algorithm, and there are 95% segments pruned on approximating polylines in average. Two comparisons are also presented: One is with an algorithm computing the directed Hausdorff distance on polylines by building Voronoi diagram of segments. The other comparison is with equation solving and pruning methods for computing the Hausdorff distance between free-form curves.

► We approximate the Hausdorff distance between free-form curves using the Hausdorff distance between approximating polylines. The error of the approximation is controllable.
► Two pruning strategies are introduced to prune useless segments on polylines to accelerate the computation of the directed Hausdorff distance from polyline to polyline.
► R-Tree structure is employed as well to accelerate the pruning process.
► The approach is practical for most applications. Under the approximating errors given in our experiments, the polyline approach is more efficient than solving equation systems.