Computing The Hausdorff Distance Approximation From Free-Form Curves To Free-Form Curves And Free-Form Surfaces

The Hausdorf distance is defined between two bounded point sets. It is the max-imum distance among all distances from a given point set to another point set. TheHausdorf distance can be used to measure the resemblance between two point sets andis widely used in domains such as computer graphics and pattern recognition. In com-puter aided design, the Hausdorf distance from free-form curves to free-form curvesand free-form surfaces can be used for error control and overlapping test.We approximate the Hausdorf distance between planar free-form curves with theHausdorf distance between planar polylines. The computation of the Hausdorf dis-tance between planar polylines is based on an incremental algorithm computing theHausdorf distance from a planar segment to a planar polyline. In order to prune uselesssegments on polylines, we proposed two pruning strategies according to the propertiesof the Hausdorf distance and applied the strategies along with the R-Tree structure tothe polylines. Comparing with the approach of solving equations, the approach in thisarticle has advantages in efciency and implementation feasibility.For the Hausdorf distance between free-form curves in3D space, we compute theHausdorf distance between spacial polylines as the approximation. The computationof the Hausdorf distance between spacial polylines is based on the incremental algo-rithm computing the Hausdorf distance from a spacial segment to a spacial polyline.The incremental algorithm depends on the split set of a segment by the Voronoi dia-gram of a polyline. We compute the split set by analyzing the structure of the bisectorsurface of two segments and solving intersection equations of a line with the bisectorsurface. We also applied the pruning strategies and R-Tree to spacial polylines to im-prove the efciency of our algorithm. In our experiments, our approach outperformsthe approach of solving equations in speed under the distance error around105.We approximate the Hausdorf distance from a spacial free-from curve to a free-form surface with the Hausdorf distance from a spacial polyline to a triangular mesh. The computation of the Hausdorf distance from a spacial polyline to a triangular meshis based on the incremental algorithm computing the Hausdorf distance from a spacialsegment to a triangular mesh. For useless segments and triangles in space, we applythe pruning strategies. The average pruning rate in our experiments is up to99%.