首先我们来看第一个问题：空间中线段PQ到三角形ABC的最短距离。在这里，想法可不要太简单。如果你从没接触过这种问题，可能你第一个想法就是分别求出P和Q到ABC所在平面的距离PP’和QQ’，然后进行比较，小者胜出。
这显然是不正确的。假设P和Q的投影点P’和Q’都不在三角形内，那么最短距离既不是PP’，也不是QQ’。这时，你可能突然记起以前学过一个东西：点到三角形的最短距离。让我们回忆一下求法：首先找到点X在三角形所在平面的投影X’。如果X’在三角形内，那么XX’就是最短距离。假设X’不在三角形内，就需要分别计算X’到三角形每条边的最短距离，也就是点到线段的最短距离，然后进行比较，小者胜出。几何证明很简单，略去。
那么好，于是我们分别计算P和Q到三角形ABC的距离，然后比较。这次总对了吧。仔细思考一下，发现也是错误的。一种很简单的情况就推翻了刚才的想法。让我们假设PQ和ABC平面严格平行，并且投影点都在三角形外。显然P到ABC的最短距离就是PP1，而PP1就是三角形PAC的高;Q到ABC的最短距离就是QQ1，QQ1就是三角形QCB的高。这样，即使我们比较出谁更小，也不能得到正确的最短距离。因为最短距离恰恰是我们上面第一种情况提到的，最简单的，PP’,当然，也就是QQ’，以及PQ上任意一点到平面的垂直距离，它们都是相等的，因为PQ与平面平行。
想到这里，可能就会比较疑惑了。看来这个距离还不是那么好求的。但是我们还是发现点规律。不管怎么说，这个距离是随着PQ的投影点与三角形的关系而变的。于是，有了新的思路，我们最好来研究一下投影点与三角形的关系。
实际上，只有三种情况。
（1） P’和Q’都在三角形内。
（2） P’和Q’中有一个点在三角形内。
（3） P’和Q’都在三角形外。
第一种情况很简单了。上面已经提到过了。
第二种情况。P’在三角形外，Q’在内。如果QQ’比PP’小，当然QQ’就胜出了。当时如果大呢？难道我们要比较QQ’和PP1的距离？即使PP1更小，如何知道在Q到P的所有点里面，没有哪一个点到ABC的距离会比PP1更小呢？
看下面这幅图。Q向P移动，显然当移动到X的时候，X到ABC的距离都比QX之间所有的点到ABC的最短距离要短。XX’暂时胜出。是XX’还是PP1强悍呢？还要比较吗？
我们再来看。目前还剩下PX之间的所有的点，到ABC的最短距离，都可以用其到三角形边AC的最短距离来表示。由此一来，我们惊讶的发现，后面所有需要比较的距离其实都是PQ上的一点和AC上一点的距离。那PQ到AC的异面线段最短距离不就是王者吗？干嘛还要比较PP1和XX’两个小将？
（注：异面线段最短距离的最短距离求法请参加我的另一篇博文）
我想，第三种情况也不需要证明了，让我们来想象。假设P’和Q’都在三角形外部，那么P’Q’必然与ABC的两条边各有一个交点，假设与AC有交点X’，与BC有交点Y’。这样，整个PQ被分为三段。PX段，XY段和YQ段。显然每段推出一个首领，然后pk就是王者。XY段很简单，XX’，YY’谁小谁胜出。但是不管XX’还是YY’都是小人物。因为上面已经证明了，PX段的首领，也就是PQ到AC的最短距离，远远比XX’强。同理QY段，PQ到BC的最短距离也比YY’强。最后把PX和QY段的首领pk一下就可以了。
三种情况我们都分析完了。看来我们只要求出PQ到AB，BC，AC的最短距离，然后比较就可以了。呵呵，不要忘了第一种情况呀。所以我们还要求P和Q分别到ABC的最短距离。因此有5个距离需要比较，小者为王。所以，我们不需要对每种情况分门别类，而只需要把所有的有限数量的值计算出来，然后进行比较即可。这就好像，在天龙八部里面，我们要知道谁最厉害。我们开始分很多种情况讨论。
（1） 扫地僧死了，乔峰他爹和慕容复他爹肯定最厉害。
（2） 扫地僧残疾了，乔峰他爹受伤了，那么慕容复他爹可能厉害
（3） 扫地僧结婚了，乔峰他爹武功被废了，慕容复他爹弃武从文了，那么乔峰厉害。
实际上就不用分那么多情况，让他们在一起一通乱打，找到胜出的。嘿嘿。我很残忍……
战争结束了……
再多说一句，线段到平面多边形的最短距离的求法，就不用我多说了吧。
还要说一点思路，求点到三角形的最短距离的时候，投影点就可以分为在三角形内和外讨论。因此求线段到三角形的最短距离的时候，也应该思考从投影的角度来分析，是否线段到线段的最短距离也是关键？直到最后得到一个结论，或者证明一个推论。希望读者受益。
再来说一点技术。在编程中，如果采用这种距离比较法而不是分情况判别法，那么算法的消耗时间是稳定的。尤其是在碰撞检测等复杂计算中，可以得到大致稳定的帧率。
评论