Computing The Hausdorff Distance Between Algebraic Curve And Algebraic Surface

Hausdorff distance is one of the most important computational geometry concepts. Hausdorff distance is a max-min distance that measures the similarity of two objects. It is applied widely in computer graphics, computer aided geometry design, pattern recognition, image processing, terrain aided navigation system and moving objects visual analysis. Previous works about Hausdorff distance are focused on parametric curves and surfaces. Because of the special property of algebra curves and surfaces which is very hard to parameterize the computation of Hausdorff distance between two algebraic curves or two algebraic surfaces has not yet been solved. Based on interval arithmetic and subdivision algorithm solutions are given to compute the Hausdorff distances between two algebraic curves or two algebraic surfaces. In chapter1, the research of background Hausdorff distance is given. Then, in chapter2, some theories of Hausdorff distance are introduced especially on the definition of Hausdorff distance and its several variants.Based on quad-tree data structure and interval arithmetic technique, a new subdivision algorithm for computing Hausdorff distance between two planar algebra curves is proposed in chapter3. In this chapter,we describe the domain discretization process and the calculation process in detail.Numerical experiments show that the algorithm is effective to compute Hausdorff distance between two algebraic curves,and we can obtained the error estimation at the same time.And then an subdivision algorithm for computing Hausdorff distance between two algebraic surfaces is given in Chapter4. This is the three-dimensional analogy of two-dimensional case in Chapter3.In recent years, with the rapid development of computer’s computing ability, algebraic curves and algebraic surfaces are widely used in computer aided geometric and computer graphics.Therefore,the study of the Hausdorff distance between algebraic curves and surfaces is necessary,also is very meaningful. Finally, In chapter5,we make a conclusion and point out directions of future research.