Computing the Hausdorff distance between two B-spline curves

This paper presents a geometric pruning method for computing the Hausdorff distance between two B-spline curves. It presents a heuristic method for obtaining the one-sided Hausdorff distance in some interval as a lower bound of the Hausdorff distance, which is also possibly the exact Hausdorff distance. Then, an estimation of the upper bound of the Hausdorff distance in an sub-interval is given, which is used to eliminate the sub-intervals whose upper bounds are smaller than the present lower bound. The conditions whether the Hausdorff distance occurs at an end point of the two curves are also provided. These conditions are used to turn the Hausdorff distance computation problem between two curves into a minimum or maximum distance computation problem between a point and a curve, which can be solved well. A pruning technique based on several other elimination criteria is utilized to improve the efficiency of the new method. Numerical examples illustrate the efficiency and the robustness of the new method.

Research highlights
► Present a geometric pruning method for computing the Hausdorff distance between two B-spline curves.
► Detect cases where Hausdorff distance occurs at an end point for one or both of the two curves.
► Eliminate most of the roots of the corresponding equation system where Hausdorff distance cannot occur.
► Provide good initial value for solving the corresponding non-linear equation system by using the Newton–Ralphson method.