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

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (10): 2485-2490.

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

祁佳玳, 寿华好

浙江工业大学理学院,杭州 310023

收稿日期:2016-05-21 修回日期:2016-07-11 出版日期:2016-10-08 发布日期:2020-08-13
作者简介:祁佳玳(1992-),女,山西,硕士生,研究方向为计算机辅助几何设计与图形学。
基金资助:
国家自然科学基金(61572430, 61272309, 61472366)

Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves

Qi Jiadai, Shou Huahao

College of Science, Zhejiang University of Technology, Hangzhou 310023, China

Received:2016-05-21 Revised:2016-07-11 Online:2016-10-08 Published:2020-08-13

摘要/Abstract

摘要： 当代数曲线表达式较为复杂时,用传统方法求解两条代数曲线间的最短距离具有一定的难度,因此提出一种细分算法。该方法应用四叉树数据结构将两条代数曲线细分离散,得到分别包含这两条代数曲线的两组像素集,应用区间算术计算这两组像素集之间的最短距离区间,该区间的中点能够用来近似表示代数曲线间的最短距离,则误差可以控制在该区间长度的一半以内。对比其他方法,不管代数曲线表达式如何地复杂,该方法始终有效,而且在任意精度下,都可以计算出代数曲线间最短距离的近似值。还可以计算出该近似值的最大误差限。

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

Abstract: 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.

Key words: algebraic curve, minimum distance, interval arithmetic, subdivision algorithm

中图分类号:

TP391.7

祁佳玳, 寿华好. 代数曲线间最短距离的细分算法[J]. 系统仿真学报, 2016, 28(10): 2485-2490.

Qi Jiadai, Shou Huahao. Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves[J]. Journal of System Simulation, 2016, 28(10): 2485-2490.

参考文献 9

[1]	Sohn K, Jüttler B, Kim M, et al.Computing Distances Between Surfaces Using Line Geometry[C]// Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, Beijing, China. USA: IEEE, 2002: 236-245.
[2]	Chen X, Chen L, Wang Y, et al.Computing the minimum distance between two Bézier curves[J]. Journal of Computational and Applied Mathematics (S0377-0427), 2009, 229(1): 294-301.
[3]	陈小雕, 雍俊海, 汪国昭. 平面代数曲线间最近距离的计算[J]. 计算机辅助设计与图形学学报, 2008, 20(4): 459-463.
[4]	徐金亭, 刘伟军, 卞宏友, 等. Bézier曲线间最近距离的计算方法[J]. 计算机辅助设计与图形学学报, 2009, 21(5): 595-599.
[5]	寿华好, 黄永明, 闫欣雅, 等. 两条代数曲线间Hausdorff距离的计算[J]. 浙江工业大学学报, 2013, 10(1): 574-577.
[6]	Krishnamurthy A, McMains S, Hanniel I. GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces[J]. Computer-Aided Design (S0010-4485), 2011, 43(11): 1370-1379.
[7]	Hanniel I, Krishnamurthy A, McMains S. Computing the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU[J]. Graphical Models (S1524-0703), 2012, 74(4): 255-264.
[8]	Bai Y, Yong J, Liu C, et al.Polyline approach for approximating Hausdorff distance between planar free-form curves[J]. Computer-Aided Design (S0010-4485), 2011, 43(6): 687-698.
[9]	Shou H, Lin H, Martin R, et al.Modified affine arithmetic is more accurate than centered interval arithmetic or affine arithmetic[J]. Lecture Notes in Computer Science (S0302-9743), 2003, 2768: 355-365.