A Subdivision Algorithm For Computing The Minimum Distance Between Algebraic Curves And Surfaces

The main content of this thesis is the subdivision algorithm of the shortest distance between algebraic curves and surfaces,which mainly deals with the shortest distance between a point and an algebraic curve/surface and the shortest distance between algebraic curves/surfaces.The problem of the shortest distance between curves/surfaces has a very wide range of applications,such as the interference detection in CAD / CAM,robot collision detection and path planning,tactile rendering,computer simulation and other fields,so its research has a very important significance.In Chapter 1,the research background and research status of distance calculation are given briefly.In Chapter 2,we mainly introduce the relevant theoretical knowledge of the interval arithmetic,the quadtree data structure and the octree data structure,and then introduce some related algorithms of calculating the shortest distance.In Chapter 3,based on interval arithmetic and the quadtree data structure,a subdivision algorithm is proposed to calculate the shortest distance from a point to an algebraic curve.As a supplement,the corresponding algorithm is proposed toimproving the computational efficiency by using interval arithmetic and equations.In Chapter 4,a subdivision algorithm is proposed for calculating the shortest distance from a point to an algebraic surface basing on interval arithmetic and the octree data structure.Similarly,a corresponding improved algorithm is proposed.In chapter 5,on the basis of the third chapter,we propose a new algorithm to calculate the shortest distance between two algebraic curves using the interval arithmetic and the quadtree data structure,and the corresponding improved algorithm.The calculation speed is improved obviously.In chapter 6,on the basis of the fourth chapter and the fifth chapter,a subdivision algorithm is proposed to calculate the shortest distance between two algebraic surfaces,based on the interval arithmetic and the octree data structure.In these chapters,the proposed algorithms are compared with other algorithms,we can see that the proposed algorithms can achieve better accuracy,and the error of the corresponding results can be obtained,which is the advantage of these algorithms.In Chapter 7,we sum up the work of this thesis and suggest the direction of future improvement.