异面线段间的最短距离_砖头不离身

http://blog.sina.com.cn/u/1720364664

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

异面线段间的最短距离

(2012-10-10 20:54:46)

标签：

空间线段之间距离

线段距离

it

分类：算法

我们知道，异面直线的最短距离指的就是公垂线的长度，计算方法很多，还可以计算出最短距离点对。

但在有的应用中，需要求出异面线段的最短距离。区别在于，异面线段的最短距离不一定就是公垂线的距离。换句话说，异面线段的最短距离点对必须都落在每条线段里面，而不能在线段的延长线上。

那么假设，现在异面线段的最短距离点对没有落在每条线段里面，很显然，公垂线距离就不是最短距离了。该如何求解最短距离呢？实际上，只要我们求出线段的每个端点到另一条线段的最短距离，然后进行比较，最小者即胜出当选。

下面我们来从几何上证明这一点。

第一幅图中，PQ是线段AB和CD的公垂线。由于P，Q分别位于AB和CD线段内，因此PQ就是最短距离。由此我们也可以看出公垂线的一般做法。平移ＡＢ与ＣＤ相交得Ｑ，从Ｑ向P做垂线，得P。

再来看第二幅图。显然PQ不再是线段AB与CD的最短距离了，因为Q不在CD内。从几何上就可以看出，实际上AB上任一点U到CD上任一点V的距离UV都可以这样求得：设U在CD和A’B’构成的二维平面内的投影为U’，那么UU’,U’V和UV就构成了一个直角三角形。

ED的距离就是这样通过EE’和E’D求得的。由于EE’ （或者UU’）都是相等的，因此最短距离的问题转变为求最小U’V（E’D）的问题。即转化到二维平面上CD和A’B’的最短距离。这就比较简单了。如果CD和A’B’相交，那么最短距离为0，CD和AB的最短距离就是PQ；如果不相交，分别求出端点A’,B’到CD的最短距离和端点C,D到A’B’的最短距离，然后进行比较。当然实际求解中不用那么复杂，从图中可以看出，我们直接求解端点A,B到CD的最短距离和端点C,D到AB的最短距离即可。

http://s16/bmiddle/668aae78tcbc02c2e819f&690

因此结论就是：

（1）如果两条线段异面或相交，那么首先判断公垂线的最小距离点对是否分别在两条线段上。如果在，那么公垂线距离为最短距离，直接返回该值。

（2）如果最小距离点对不在其上，或者两条线段平行，那么直接把每条线段端点到另一条线段的最短距离进行比较即可。

该算法相当有用，因为它被使用在一种很经典的算法中，那就是求解三维空间中线段到多边形的最短距离。该问题源自于碰撞检测中三角形面与胶囊体的碰撞。胶囊体上的点到其轴线段的最短距离都是R。因此我们可以求出轴线段到检测三角形的最短距离，如果其小于R，那么说明三角形上肯定有点在胶囊体内部，也就是碰撞发生了。另外，在三维GIS的点选线段操作中也可以使用并借鉴。

本人代码实现，关键代码如下：

double SocketUdp::getPointsDis(stPoint stPS,stPoint stPE)

{

return sqrt((stPS.dX-stPE.dX)*(stPS.dX-stPE.dX)+(stPS.dY-stPE.dY)*(stPS.dY-stPE.dY));

}

double SocketUdp:: getTheNearestDis(stPoint stLine1PS,stPoint stLine1PE,stPoint stTargetP)

{

float a,b,c;

a=getPointsDis(stLine1PE,stTargetP);

if(a<=0.00001)

return 0.0f;

b=getPointsDis(stLine1PS,stTargetP);

if(b<=0.00001)

return 0.0f;

c=getPointsDis(stLine1PS,stLine1PE);

if(c<=0.00001)

return a;//如果stLine1PS和stLine1PE坐标相同，则退出函数，并返回距离

//---stTargetP在线段上的投影不在线段上---------------------------

if(a*a>=b*b+c*c)

return b; //如果是钝角返回b

if(b*b>=a*a+c*c)

return a; //如果是钝角返回a

//stTargetP在线段上的投影在线段上

float l=(a+b+c)/2; //周长的一半

float s=sqrt(l*(l-a)*(l-b)*(l-c)); //海伦公式求面积，也可以用矢量求

return 2*s/c;

}

double SocketUdp::getTheNearestDis(stPoint stLine1PS,stPoint stLine1PE,stPoint stLine2PS, stPoint stLine2PE)

{

double dNearestDis;

//line2的起始端到line1的最小距离

dNearestDis = getTheNearestDis(stLine1PS,stLine1PE,stLine2PS);

//line2的终点到line1的最小距离与原值取小

dNearestDis = min(dNearestDis,getTheNearestDis(stLine1PS,stLine1PE,stLine2PE));

//line1的起始端到line2的最小距离与原值取小

dNearestDis = min(dNearestDis,getTheNearestDis(stLine2PS,stLine2PE,stLine1PS));

//line1的终点到line2的最小距离与原值取小

dNearestDis = min(dNearestDis,getTheNearestDis(stLine2PS,stLine2PE,stLine1PE));

return dNearestDis;

}