超声检测技术的妙用



超声检测技术的妙用

碰撞干涉检测问题是确定不同的物体在空间是否占有相同区域的问题。该问题可描述如下：“给定N 个物体s1，s2 ，… ，sn，它们在空间中的位置是由定义在时间域[t0，t1] 上的函数f1，f2，…，fn来确定的，判定在这个时间域内相同时刻是否存在任何一对物体占有公共空间”。该问题的描述说明了这样的意义，物体占有的空间决定于时间，由此又引出静态干涉和动态干涉检测的定义。

静态干涉检测: 物体在空间中的位置是可移动的，但不随时间变化，位置的变化是由其它参数定义的，判别是否有任何一对物体占有公共空间。空间布局和装配干涉检测等即属于此类问题。

动态干涉检测：动态干涉检测与时间相关，即碰撞检测。物体在空间中的位置是随时间变化的，它可分为二种情况：

(1) 运动空间中只有一个物体是运动的。例如一个机器人在车间里运动，机器人是运动的，车间里的其它障碍物是静止的；

(2) 一对物体都必须是运动的，例如车间里两个运动的机器人。无论是静态干涉检测还是动态干涉检测，目的都是要求避免物体间的碰撞。

Tetsuya，Toshiaki和Mario等人提出了一种称为空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检测它们的碰撞。这种算法基于这样一条原理没有任何物体和其它物体占有同一个球体，也不需要特殊的计算来检测碰撞。并且，在它们的方法中，每个物体连同它们所占有的球体在三维空间中都被赋予一个名字，因而其它物体知道它们和哪个物体发生碰撞。

chin和wang研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸一边形和一个简单非凸m-边形的相交问题的最优算法，并且研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为o(m+n)。

汪嘉业利用单调折线研究了在一个多边形的凸包和另一个多边形不相交的条件下，确定两个多边形是否碰撞，并在碰撞时确定全部碰撞部位的问题，提出了时间复杂度为o(m+n)的最优算法，并且其算法还可推广到确定包含有圆弧边的多边形之间的最初碰撞部位。

李辉利用最大最小坐标的顶点子集的方法研究了一个凸多边形沿一给定方向移动时是否与另一凸多边形发生碰撞，并且利用斜支撑线的方法来研究一个凸多边形相对于另一个凸多边形的可移动区域问题，提出了时间复杂度为o(log(n+m))和o(m+n)的算法，在常数意义下，它们都是最优的。