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

Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves

作　　者：祁佳玳 寿华好[1] 

机构地区：[1]浙江工业大学理学院,杭州310023

出　　处：《系统仿真学报》2016年第10期2485-2489,2496,共6页Journal of System Simulation

基　　金：国家自然科学基金(61572430;61272309;61472366)

摘　　要：当代数曲线表达式较为复杂时,用传统方法求解两条代数曲线间的最短距离具有一定的难度,因此提出一种细分算法。该方法应用四叉树数据结构将两条代数曲线细分离散,得到分别包含这两条代数曲线的两纽像素集,应用区间算术计算这两纽像紊集之间的最短距离区间,该区间的中点能够用来近似表示代数曲线闻的最短距离,则误差可以控制在该区间长度的一半以内。对比其他方法,不管代数曲线表达式如何地复杂,该方法始终有效,而且在任意精度下,都可以计算出代数曲线间最短距离的近似值。还可以计算出该近似值的最大误差限。Since it is difficult to compute the minimum distance between two algebraic curves by traditional methods when the expressions of the algebraic curves are complicated, a subdivision algorithm is proposed. Quadtree data structure was used to subdivide the two algebraic curves into two sets of pixels Interval arithmetic was used to compute the minimum distance interval between these two sets of pixels. The center of this interval is the approximation of the minimum distance between the two algebraic curves The error is less than a half of this interval. Compared with traditional methods, this method can obtain the approximation of the minimum distance between two algebraic curves at any precision, as well as the error estimation at the same time.

关 键 词：代数曲线 最短距离 区间算术 细分算法 

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]