Computing the Hausdorff distance between two B-spline curves

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

51 Scopus Citations
View graph of relations

Author(s)

  • Xiao-Diao Chen
  • Weiyin Ma
  • Gang Xu
  • Jean-Claude Paul

Detail(s)

Original languageEnglish
Pages (from-to)1197-1206
Journal / PublicationCAD Computer Aided Design
Volume42
Issue number12
Publication statusPublished - Dec 2010

Abstract

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.

Research Area(s)

  • Geometric pruning technique, Hausdorff distance, Root-finding method

Citation Format(s)

Computing the Hausdorff distance between two B-spline curves. / Chen, Xiao-Diao; Ma, Weiyin; Xu, Gang; Paul, Jean-Claude.

In: CAD Computer Aided Design, Vol. 42, No. 12, 12.2010, p. 1197-1206.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review