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