TY - JOUR
T1 - Computing the Hausdorff distance between two B-spline curves
AU - Chen, Xiao-Diao
AU - Ma, Weiyin
AU - Xu, Gang
AU - Paul, Jean-Claude
PY - 2010/12
Y1 - 2010/12
N2 - 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. © 2010 Elsevier Ltd. All rights reserved.
AB - 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. © 2010 Elsevier Ltd. All rights reserved.
KW - Geometric pruning technique
KW - Hausdorff distance
KW - Root-finding method
UR - http://www.scopus.com/inward/record.url?scp=77957919105&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-77957919105&origin=recordpage
U2 - 10.1016/j.cad.2010.06.009
DO - 10.1016/j.cad.2010.06.009
M3 - 21_Publication in refereed journal
VL - 42
SP - 1197
EP - 1206
JO - CAD Computer Aided Design
JF - CAD Computer Aided Design
SN - 0010-4485
IS - 12
ER -