浙江大学学报（理学版）2016，Vol.43Issue(3)：286-291,6.DOI:10.3785/j.issn.1008-9497.2016.03.006
点到代数曲线最短距离的细分算法
A subdivision algorithm for computing the minimum distance between a point and an algebraic curve
摘要
Abstract
The distance computation has wide applications in computer‐aided geometric design and graphics .A subdi‐vision algorithm based on the interval arithmetic and quadtree data structure for computing the minimum distance be‐tween 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.关键词
代数曲线/最短距离/区间算术/细分算法Key words
algebraic curves/minimum distance/interval arithmetic/subdivision algorithm分类
信息技术与安全科学引用本文复制引用
祁佳玳,寿华好..点到代数曲线最短距离的细分算法[J].浙江大学学报（理学版）,2016,43(3):286-291,6.基金项目
国家自然科学基金资助项目（61572430，61272309，61472366）． （）
