Computer Science and Application
Vol.05 No.11(2015), Article ID:16401,9 pages
10.12677/CSA.2015.511050

The Geometric Iteration Method for Computing the Minimum Distance between Two Spatial Circles

Xiaowu Li1, Zhinan Wu2, Lin Wang1, Mingsheng Zhang1

1College of Information Engineering, Guizhou Minzu University, Guiyang Guizhou

2School of Mathematics and Computer Science, Yichun University, Yichun Jiangxi

Received: Nov. 1st, 2015; accepted: Nov. 18th, 2015; published: Nov. 24th, 2015

Copyright © 2015 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

Computing the minimum distance between two spatial circles is the base of collision detection and intersection in the fields of computer graphics, computer-aided design and computer-aided geometric design. This paper has completely analyzed and discussed the minimum distance problem between two spatial circles for their spatial position relationships. If the two central axes of two spatial circles are not paralleled, we have presented the algorithm for computing the minimum distance between two spatial circles based on the geometric iterative method. Besides, if two central axes of two spatial circles have an intersection, we also have presented two pairs of corresponding points of the minimum distance for two spatial circles based on the geometric iterative method; if two central axes of two spatial circles are paralleled or coincident, we have directly provided the analytical expressions for computing the minimum distance between two spatial circles. Numerical examples illustrate that the algorithms are efficient and robust.

Keywords:Two Spatial Circles, The Minimum Distance, Geometric Iteration Method, Central Axis

几何迭代方法计算空间两圆之间的最近距离

李小武1,吴志男2,王林1,张明生1

1贵州民族大学信息工程学院,贵州 贵阳

2宜春学院,数学与计算机科学学院,江西 宜春

收稿日期:2015年11月1日;录用日期:2015年11月18日;发布日期:2015年11月24日

摘 要

空间两圆之间的最近距离计算是计算机图形学、计算机辅助设计、计算机辅助几何设计等领域进行碰撞检测和相交计算问题的基础。本文对任意位置关系的空间两圆的最近距离进行了完整分析与讨论。空间两圆的中心轴不平行时,提出了基于几何迭代方法的空间两圆最近距离的求解算法,当空间两圆中心轴有交点时,本文给出了间两圆最近距离的两对对应点;当空间两圆的中心轴平行或重合时,本文给出两圆最近距离的解析表达式。最后通过若干例子显示本文方法的稳定性和有效性。

关键词 :空间两圆,最近距离,几何迭代方法,中心轴

1. 引言

空间物体之间的最近距离计算是计算机图形学、计算机辅助设计、计算机辅助制造、计算机辅助几何设计、机器人、数控加工等领域中的重要话题。空间两物体之间的最近距离不仅是机辅助设计/计算机辅助制造中的碰撞检测必要环节之一,同时也是计算机图形学中的碰撞检测中的重要环节[1] [2] 。对于多面体之间最近距离的研究有[2] -[5] ,关于空间两曲面最近距离的研究有[2] [6] 小雕等[7] 给出了基于点圆最近距离计算的圆环面/球面求交算法。该算法直接判断处理无交、相切于一点、交于一个圆以及交于两个圆等简单情况;对于其他情况,通过求解一元四次关键方程得到相应的关键值,对大圆参数区间进行划分,然后通过简单的符号判断来确定相交的参数子区间,并直接给出交曲线段的参数表达式。文献[8] 把圆环面之间的最近距离问题转换成三维空间中两圆的最小距离问题,并用群论的方法证明了这个问题没有闭式解,需要求解一个一元八次方程,但文献没有给出具体求解过程。刘晓明等[9] 指出文献[8] 的各种位置关系判断并不是完全的。文献[10] 用迭代方法求解空间两圆的最近距离问题,首先在空间任意取一点,直接计算该点至第一圆的最近距离的坐标点,然后再由该坐标点直接计算第二圆的最近距离的坐标点,在反复迭代直至求出空间两圆的最近距离。该算法虽然能求出两圆全局的最近距离,但该算法没有给出空间两圆最近距离的两对对应点。文献[11] 也设计了一个迭代算法求出两个空间椭圆的最近距离问题。文献[10] [11] 相同之处在于都采用了迭代思想来逼近两圆或两椭圆的最近距离,都没有分析讨论最近距离的两对对应点以及中心轴平行和重合的特殊位置情况。文献[12] 以几何方法为基础,通过判断圆环中心圆之间的位置关系来判定相交区域,并运用数值分析方法精确计算出每条交线的初始点,然后用跟踪法求出交线。文献[9] 证明了空间两圆Hausdorff 距离总可以表示为它们的一对共线法向点的距离,给出了计算空间两圆的共线法向点的详细过程,并对这些共线法向点进行筛选,求出了空间两圆的最近距离和Hausdorff 距离。文献[9] 还给出了两圆环包含、分离和相交时的充要条件,解决了两圆环面之间的最近距离计算问题,从理论上对两圆环的位置关系给出了严格的判别方法,但具体的实现却依赖于用数值方法求解八次方程。最近关于空间曲线最近距离的研究有[13] -[19] 。

本文利用几何迭代方法完整地研究了空间两圆任意位置关系的最近距离的算法。当空间两圆中心轴不平行时,对任意初始迭代点,求出该点至第一圆的最近距离的正交投射点,由正交投射点经过逆坐标变换和坐标变换正交投射至第二圆得到第二圆的正交投射点,然后再把该点作为初始迭代点重复上述步骤反复迭代,直至求出空间两圆的最近距离。当空间两圆的中心轴有公共点时,还可以求出空间两圆最近距离的另外一对对应的点;当空间两圆的中心轴平行,文章给出了简化版的两圆最近距离的迭代算法,当第二圆的正交投射至第一圆所在平面时,与第一圆有交点时,我们还给出了另外一对两圆最近距离的对应点。此外,文章还为两圆的中心轴平行或重合情况给出了求解最近距离的表达式。上述实例显示本文算法是有效和鲁棒的。

2. 算法分析与实现及实例

2.1. 两中心轴一般位置(不平行)的几何迭代算法

第一个圆和第二原始位置圆,圆经过坐标变换得到圆,其中圆的中心轴的向量和圆心点分别为

目标是求圆的最近距离,空间两圆最近距离的基本思路为:

I) 正交投射空间任意点至第一圆得到对应的正交投射点;

II) 正交投射第一圆上的正交投射点至第二圆得到对应的正交投射点;

III) 反复进行上述两步直至求出第一圆与第二圆之间最近距离。

下面按照三步步骤思路具体实现空间两圆最近距离的相关算法。

由于圆的中心轴的向量和圆心点分别是 ()和。故圆转换为圆的坐标变换过程为

(1)

其中

由坐标变换(1),可知对应的逆坐标变换

(2)

由坐标变换(1)和逆坐标变换(2),给出计算空间两圆之间最近距离的算法。

算法1:

Step 1:正交投射第二圆上任意点或第二圆圆心至第一圆,得到对应

的正交投射点

Step 2:利用逆坐标变换公式(2),对第一圆上的正交投射点进行逆坐标变换(2)得到点,其中

Step 3:计算点正交投射至第二原始位置的圆的正交投射点

Step 4:正交投射点经过坐标变换(1)得到并记作点

Step 5:令,反复重复上述四步,直至第一圆上的点与第二圆上的点之间距离最短,即圆之间最短距离为

当两圆中心轴有公共点时,这时两圆的最近距离有两对对应点,投射第二圆的中心轴至第一圆得到直线。点关于直线的对称点为:

作为算法1的初始迭代点,

重复上述五步直至求出两圆的另外一对最近距离的对应点。空间两圆中心轴一般位置和垂直的示意图见图1图2

Figure 1. Schematic figure for general position of central axes of two spatial circles

图1. 空间两圆中心轴一般位置的示意图

Figure 2. Schematic figure for perpendicular position of central axes of two spatial circles

图2. 空间两圆中心轴垂直的示意图

注释1:当空间两圆两中心轴互相垂直且有公共点,圆心点在z-轴上的特殊位置时,给出了具体的解析分析表达式。这时第一圆和第二原始位置的圆分别为,经过坐标变换(1)后变成第二圆,其中,中心轴的向量和圆心点分别为 (不失一般性假定)和。不难知道这时第一圆的上点是第二圆的正交投射点,同理第一圆的上点是第二圆的正交投射点,所以两圆的最近距离为。另外,第二圆的点至第一圆的正交投射点集就是第一圆本身,则最近距离为。由于,所以这时两圆的最近距离为。更特别的,当第二圆的圆心点与第一圆圆心点重合时,这时两圆的最近距离变为

注释2:文献[10] 给出了Kurush-Kuhn-Tucker优化条件,并给出了在优化条件下非线性Kurush-Kuhn- Tucker系统的封闭式解。对于两圆盘在同一中心轴上和在同一水平面上,没有给出这两种特殊位置的解。文献[11] 首先给出了点至空间椭圆最近距离的一元四次方程准确解,然后利用迭代方法在第一椭圆上任选一点求出至第二空间椭圆最近距离及对应点,再由对应点求出至第一椭圆最近距离及对应点,反复迭代直至求出两椭圆最近距离及对应点。当空间两椭圆最近距离两对对应点时没有给出对应分析和讨论。另外对空间两椭圆中心轴是同一轴时最近距离有无数对应点没有给出分析;当两椭圆是在同一平面时,也没有给出对应分析和讨论。我们不仅给出了空间两圆在任意位置的迭代方法最近距离及对应点,还分析和讨论了空间两圆最近距离有两对对应点位置分析结论。此外,我们还对两圆在同一平面位置给出了完整的分析,也就是说,我们给出了空间两圆在空间任意位置的所有情况讨论。

2.2. 两中心轴平行的几何迭代算法

两中心轴平行,此时两圆的表达式可分别表示为第一圆和第二圆,其中,中心轴为,圆心点为。若用算法1计算两圆的最近距离,发现坐标变换(1)和逆坐标变换(2)已失效,为此提出相应的两圆最近距离的算法2:

算法2:

Step 1:正交投射空间任意点至第一圆得到对应的正交投射点

Step 2:计算点正交投射至第二圆的正交投射点,其中

,此时

Step 3:令,反复重复上述两步,直至第一圆上的点与第二圆上的点之间距离最短,即圆之间最短距离为

时,两圆的最近距离有两对对应点,投射第二圆的中心点至第一圆平面得到点,连接两点和点得到直线。点关于直线的对称点为

作为算法2的初始迭代点,重复上述三步直至求出两圆的另外一对最近距离的对应点。

2.3. 中心轴平行的空间两圆最近距离解析表达式

第一圆和第二圆,其中第二圆中心轴为,圆心点为。空间两圆中心轴平行的示意图见图3

分下列几种情况具体分析

1) 若,则空间两圆最近距离的对应点分别为,其最近距离为

2) 若,则对对应点为,其距离为,其中

Figure 3. Actual examples for parallel position of central axes of two spatial circles

图3. 空间两圆中心轴平行的实例

3) 若

,两圆最近距离的对应点为

其距离为

,两圆最近距离的对应点为

其距离为

2.4. 中心轴重合的空间两圆最近距离解析表达式

这时第一圆,第二圆。两圆最近距离对应点集为,两个式子的参数必须同时取同一值,所以两圆的最近距离为

例1:空间两圆的半径分别为,第二圆的中心轴的向量和圆心分别为,由算法1可知,两圆最近距离对应点分别为(2.2566117602763080,5.5594697016336607,0)和(5.5251451389773982, 13.600640848138522,5.4491555845201255)。最近距离为10.24875800。 此例是针对算法1中的空间两圆中心轴没有公共点时两圆最近距离只有唯一一对对应点的解释。

例2:空间两圆的半径分别为,第二圆的中心轴的向量和圆心分别为,由算法1可知,两圆最近距离第一对对应点分别为(−9.7379538193036241, −2.2742593108768315,0)和(−7.9338517047101518, −1.8529186362318786, 0.7410600411832663),另外一对对应点分别为(−0.0811899 52715625401, −9.9996704041472304,0)和(−0.0661482952898482, −8.1470813637681214, 0.7410600411832664),最近距离为1.995365226。此例是针对算法1中的空间两圆中心轴有公共点时两圆最近距离有两对对应点的说明。

3. 总结与展望

本文完全地给出了空间两圆任意位置的最近距离的迭代算法和解析表达式,当空间两圆中心轴不平行,利用几何迭代法提出了空间两圆最近距离的算法;当空间两圆中心轴平行时,提出了简化版的空间两圆最近距离的迭代算法;当中心轴平行或重合时,我们提出了空间两圆最近距离的解析表达式。文章提供的迭代算法对初始迭代点不敏感且是有效的。下一步将在此基础上尝试给出空间圆环面/球面、圆环面/圆环面、椭圆环面/圆环面、椭圆环面/椭圆环面等与空间两圆有关联的若干情况分析。

基金项目

国家自然科学基金(61263034);国家统计局基金资助项目(2014LY011);贵州省科学技术基金([2014]2092),[2014]2093));贵州省“模式识别与智能系统”重点实验室建设项目(黔科合计[2009]4002);贵州省“信息处理与模式识别”研究生教育创新基地。

文章引用

李小武,吴志男,王林,张明生. 几何迭代方法计算空间两圆之间的最近距离
The Geometric Iteration Method for Computing the Minimum Distance between Two Spatial Circles[J]. 计算机科学与应用, 2015, 05(11): 394-402. http://dx.doi.org/10.12677/CSA.2015.511050

参考文献 (References)

  1. 1. Ho, S., Sarma, S. and Adachi, Y. (2001) Real-Time Interference Analysis between a Tool and an Environment. Com-puter-Aided Design, 33, 935-947. http://dx.doi.org/10.1016/S0010-4485(00)00117-2

  2. 2. Johnson, D. and Cohen, E. (1998) A framework for Efficient Minimum Distance Computations. Proceedings of the IEEE Conference on Robotics and Automation, 36, 78-84. http://dx.doi.org/10.1109/robot.1998.681403

  3. 3. Cameron, S. and Enhancing, G.J.K. (1997) Computing Minimum and Penetration Distances between Convex Polyhedra. Proceedings of the IEEE Conference on Robotics and Automation, 3112-3117. http://dx.doi.org/10.1109/ROBOT.1997.606761

  4. 4. Gilbert, E.G., Johnson, D.W. and Keerthi, S.S. (1988) A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space. IEEE Journal of Robotics and Automation, 4, 193-203. http://dx.doi.org/10.1109/56.2083

  5. 5. Lin, M.C. (1993) Efficient Collision Detection for Animation and Robotics. Ph. D Thesis, University of California, Berkeley.

  6. 6. Snyder, J. (1995) An Interactive Tool for Placing Curved Surfaces without Interpenetration. Computer Graphics. SIGGRAPH, Los Angeles, 6-11 August 1995, 209-218.

  7. 7. 陈小雕, 雍俊海, 郑国勤, 等. 圆环面/球面求交算法[J]. 计算机辅助设计与图形学学报, 2005, 17(6): 1202-1206.

  8. 8. Neff, C.A. (1990) Finding the Distance between Two Circles in Three-Dimensional Space. IBM Journal of Research and Development, 34, 770-775. http://dx.doi.org/10.1147/rd.345.0770

  9. 9. 刘晓明, 刘长远, 胡强, 雍俊海. 计算两圆环面之间的最近距离[J]. 计算机辅助设计与图形学学报, 2011, 23(2): 240-246.

  10. 10. Almohamad, H.A. and Selim, S.Z. (2003) An Algorithm for Computing the Distance between Two Circular Disks. Applied Mathematical Modelling, 27, 115-124. http://dx.doi.org/10.1016/S0307-904X(02)00080-X

  11. 11. Kim, I.S. (2006) An Algorithm for Finding the Distance between Two Ellipses. Communications Korean Mathematical Society, 21, 559-567. http://dx.doi.org/10.4134/CKMS.2006.21.3.559

  12. 12. 王日昀, 宁涛, 席平, 等. 圆环与圆环求交算法中初始点的计算[J]. 工程图学学报, 2004, 25(1): 47-51.

  13. 13. Chen, X.D., Chen, L.Q., Wang, Y.G., Xu, G., Yong, J.H. and Paul, J.C. (2009) Computing the Minimum Distance between Two Bézier Curves. Journal of Computational and Applied Mathematics, 229, 294-301. http://dx.doi.org/10.1016/j.cam.2008.10.050

  14. 14. Chen, X.D., Ma, W.Y., Xu, G. and Paul, J.C. (2010) Computing the Hausdorff Distance between Two B-Spline Curves. Computer-Aided Design, 42, 1197-1206. http://dx.doi.org/10.1016/j.cad.2010.06.009

  15. 15. Chang, J.W., Choi, Y.K., Kim, M.S. and Wang, W.P. (2011) Computation of the Minimum Distance between Two Bézier Curves/Surfaces. Computers & Graphics, 35, 677-684. http://dx.doi.org/10.1016/j.cag.2011.03.025

  16. 16. Bai, Y.B., Yong, J.H., Liu, C.Y., Liu, X.M. and Meng, Y. (2011) Polyline Approach for Approximating Hausdorff Distance between Planar Free-Form Curves. Computer-Aided Design, 43, 687-698. http://dx.doi.org/10.1016/j.cad.2011.02.008

  17. 17. Ma, Y.P., Tu, C.H. and Wang, W.P. (2012) Distance Computa-tion for Canal Surfaces Using Cone-Sphere Bounding Volumes. Computer Aided Geometric Design, 29, 255-264. http://dx.doi.org/10.1016/j.cagd.2011.10.007

  18. 18. Sundar, B.R., Chunduru, A., Tiwari, R., Gupta, A. and Muthu-ganapathy, R. (2014) Footpoint Distance as a Measure of Distance Computation between Curves and Surfaces. Com-puters & Graphics, 38, 300-309. http://dx.doi.org/10.1016/j.cag.2013.10.032

  19. 19. Blasco, A. and Pérez-Díaz, S. (2015) Characterizing the Finiteness of the Hausdorff Distance between Two Algebraic Curves. Journal of Computational and Applied Mathematics, 280, 327-346. http://dx.doi.org/10.1016/j.cam.2014.12.005

期刊菜单