点到代数曲线最短距离的细分算法

A subdivision algorithm for computing the minimum distance between a point and an algebraic curve

距离计算在计算机辅助几何设计与图形学领域有着广泛的应用.为了有效计算点到代数曲线的最短距离,提出了一种基于区间算术和区域细分的细分算法.利用四叉树数据结构对给定区域进行细分,用区间算术计算细分后所有像素点到给定点的距离区间,得到最小距离区间.该方法的优势在于在得到任意精度的点到代数曲线最短距离的同时,亦得到了该结果的最大误差限.为进一步提高速度,还对算法进行了改进.

The distance computation has wide applications in computer-aided geometric design and graphics.A subdivision algorithm based on the interval arithmetic and quadtree data structure for computing the minimum distance between a point and an algebraic curve is proposed.A quadtree data structure is adopted during the subdivision of the give domain,and the interval arithmetic is used to compute the interval distances between the pixel on the algebraic curve and the given point.Compared with other methods,this method can obtain a close approximate value of the minimum distance between a point and an algebraic curve at any precision,while conducting the error estimation at the same time.An improved algorithm is also proposed to further accelerate the calculation speed.