Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2016, Vol. 43 Issue (3): 286-291    DOI: 10.3785/j.issn.1008-9497.2016.03.006
数学与计算机科学     
点到代数曲线最短距离的细分算法
祁佳玳, 寿华好
浙江工业大学 理学院, 浙江 杭州 310023
A subdivision algorithm for computing the minimum distance between a point and an algebraic curve
QI Jiadai, SHOU Huahao
College of Science, Zhejiang University of Technology, Hangzhou 310023, China
 全文: PDF(361 KB)  
摘要： 距离计算在计算机辅助几何设计与图形学领域有着广泛的应用.为了有效计算点到代数曲线的最短距离,提出了一种基于区间算术和区域细分的细分算法.利用四叉树数据结构对给定区域进行细分,用区间算术计算细分后所有像素点到给定点的距离区间,得到最小距离区间.该方法的优势在于在得到任意精度的点到代数曲线最短距离的同时,亦得到了该结果的最大误差限.为进一步提高速度,还对算法进行了改进.
关键词： 代数曲线;  最短距离;  区间算术;  细分算法    
Abstract: 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.
Key words: algebraic curves    minimum distance    interval arithmetic    subdivision algorithm
收稿日期: 2015-11-06 出版日期: 2016-03-01
CLC:  TP391.7  
基金资助: 国家自然科学基金资助项目(61572430,61272309,61472366).
通讯作者: 寿华好,ORCID:http://orcid.org/0000-0002-8991-337X,E-mail:shh@zjut.edu.cn.     E-mail: shh@zjut.edu.cn
作者简介: 祁佳玳(1992-),ORCID:http://orcid.org/0000-0003-4909-854X,女,硕士研究生,主要从事计算机辅助几何设计与图形学研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

祁佳玳, 寿华好. 点到代数曲线最短距离的细分算法[J]. 浙江大学学报（理学版）, 2016, 43(3): 286-291.

QI Jiadai, SHOU Huahao. A subdivision algorithm for computing the minimum distance between a point and an algebraic curve. Journal of ZheJIang University(Science Edition), 2016, 43(3): 286-291.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.03.006    或    https://www.zjujournals.com/sci/CN/Y2016/V43/I3/286

[1] CHANG Jungwoo, CHIO Yiking, KIM Myungsoo, et al. Computation of the minimum distance between two Bézier curves/surfaces [J]. Computer & Graphics,2011,35(3):677-684.
[2] MA Yanpeng, TU Changhe, WANG Wenping. Distance computation for canal surfaces using cone-sphere bounding volumes [J]. Computer Aided Geometric Design,2012,29(5):255-264.
[3] CHEN Xiaodiao, MA Weiyin, XU Gang . Computing the Hausdorff distance between two B-spline curves[J]. Computer Aided Design,2010,42(12):1197-1206.
[4] 陈小雕,王毅刚,徐岗.Bézier曲线曲面间最近距离的几何裁剪算法[J].计算机辅助几何设计与图形学学报,2009,21(10):1404-1411. CHEN Xiaodiao, WANG Yigang, XU Gang. Geometric pruning method for computing minimum distance between a Bézier curves and a Bézier surfaces [J]. Journal of Computer-Aided Design & Computer Graphics,2009,21(10):1404-1411.
[5] CHEN Xiaodiao, YONG Junhai, WANG Guozhao, et al. Computing the minimum distance between a point and a NURBS curve [J]. Computer-Aided Design,2008,40(10/11):1051-1054.
[6] 陈小雕,雍俊海,汪国昭.平面代数曲线间最短距离的计算[J].计算机辅助几何设计与图形学学报,2008,20(4):459-463. CHEN Xiaodiao, YONG Junhai, WANG Guozhao, et al. Computing the minimum distance between two planar algebraic curves [J]. Journal of Computer-Aided Design & Computer Graphics,2008,20(4):459-463.
[7] CHRISTIAN L, ELMAR S. Efficient distance computation for quadratic curves and surfaces [C] // Proceeding of Geometric Modeling and Processing. New York: IEEE Computer Society Press,2002:60-69.
[8] KIM Kujin. Minimum distance between a canal surface and a simple surface [J]. Computer-Aided Design,2003,35(10):871-879.
[9] 余正生,樊丰涛,王毅刚.点到隐式曲线曲面的最小距离[J].工程图学学报,2005(5):74-79. YU Zhengsheng, FAN Fengtao, WANG Yigang. The minimum distance between a point and an implicit curve/surface [J]. Journal of Engineering Graphics,2005(5):74-79.
[10] 寿华好,黄永明,闫欣雅,等.两条代数曲线间Hausdorff距离的计算[J].浙江工业大学学报,2013,41(5):574-577. SHOU Huahao, HUANG Yongming, YAN Xinya, et al. Computation of the Hausdorff distance between two algebraic curves [J]. Journal of Zhejiang University of Technology,2013,41(5):574-577.
[11] 伍丽峰,陈岳坪,谵炎辉,等.求点到空间参数曲线最小距离的几种算法[J].机械设计与制造,2011,32(9):15-17. WU Lifeng, CHEN Yueping, ZHAN Yanhui, et al. Algorithms on calculating minimum distance between point and spatial parametric curves [J]. Machinery Design & Manufacture,2011,32(9):15-17.
[12] 林意,薛思骐,郭婷婷.一种参数曲线间Hausdorff距离的计算方法[J].图学学报,2014,35(5):704-708. LIN Yi, XUE Siqi, GUO Tingting. A method of calculating the Hausdorff distance between parametric curves [J]. Journal of Graphics,2014,35(5):704-708.
[13] 廖平.分割逼近法快速求解点到复杂平面曲线最小距离[J].计算机工程与应用,2009,45(10):163-164. LIAO Ping. Fast calculating minimum distance between point and complex curve with subdivision approximating algorithm [J]. Computer Engineering and Application,2009,45(10):163-164.
[14] SHOU Huahao, LIN Hongwei, RALPH M , et al. Modified affine arithmetic is more accurate than centered interval arithmetic or affine arithmetic [J]. Lecture Notes in Computer Science,2003,2768:355-365.
[1] 宋建文, 罗江林, 王博, 张倩, 王献悦. 基于故事情景链语法的偶动画短片分析与建模[J]. 浙江大学学报（理学版）, 2020, 47(3): 284-296.
[2] 赵喆, 张天野, 黄彦浩, 郑文庭, 陈为. 面向仿真数据的电网运行方式可视分析[J]. 浙江大学学报（理学版）, 2020, 47(1): 36-44.
[3] 郑锐, 钱文华, 徐丹, 普园媛. 基于卷积神经网络的刺绣风格数字合成[J]. 浙江大学学报（理学版）, 2019, 46(3): 270-278.
[4] 喻奇, 王伦耀, 夏银水. 基于library-free映射的电路面积快速优化算法[J]. 浙江大学学报（理学版）, 2018, 45(6): 733-740.
[5] 张理涛, 谷同祥, 孟慧丽. 解非对称鞍点问题的广义交替分裂预处理子的一个注记[J]. 浙江大学学报（理学版）, 2017, 44(2): 168-173.
[6] 张理涛. 解鞍点问题的新SOR类迭代法的一个注记[J]. 浙江大学学报（理学版）, 2016, 43(3): 292-295.
[7] 卜登立. 基于混合遗传算法的MPRM最小化[J]. 浙江大学学报（理学版）, 2016, 43(2): 184-189.