Precise Hausdorff distance computation between polygonal meshes

Michael Barton*, Iddo Hanniel, Gershon Elber, Myung Soo Kim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

We present an exact algorithm for computing the precise Hausdorff distance between two general polyhedra represented as triangular meshes. The locus of candidate points, events where the Hausdorff distance may occur, is fully classified. These events include simple cases where foot points of vertices are examined as well as more complicated cases where extreme distance evaluation is needed on the intersection curve of one mesh with the medial axis of the other mesh. No explicit reconstruction of the medial axis is conducted and only bisectors of pairs of primitives (i.e. vertex, edge, or face) are analytically constructed and intersected with the other mesh, yielding a set of conic segments. For each conic segment, the distance functions to all primitives are constructed and the maximum value of their low envelope function may correspond to a candidate point for the Hausdorff distance. The algorithm is fully implemented and several experimental results are also presented.

Original languageEnglish (US)
Pages (from-to)580-591
Number of pages12
JournalComputer Aided Geometric Design
Volume27
Issue number8
DOIs
StatePublished - Nov 1 2010

Keywords

  • Bisector surface
  • Geometric algorithm
  • Hausdorff distance
  • Low envelope
  • Medial axis
  • Polygonal mesh

ASJC Scopus subject areas

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Precise Hausdorff distance computation between polygonal meshes'. Together they form a unique fingerprint.

Cite this