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)；贵州省“信息处理与模式识别”研究生教育创新基地。