如何计算点到线段的最近距离

                                         算法原理图

 

 

在二维/三维图形学系统当中，线段的拾取是一个经常使用的功能

如何根据鼠标点来判断线段是否被选择了，最主要的方法之一是通过点到线段的最小距离来判定的

无论二维还是三维情况下，使用点到直线的距离公式似乎是最直接的选择

但是不要忘记点到直线公式计算的是点和直线之间的关系，而不是点和线段之间的关系

需要额外的判断，点在线段上的投影点是否位于线段内部，是才可以采用点到直线的公式，否则就不能

算法如下 

   

class Point

float Distance(Point p1, Point p2); // 返回两点之间的距离

float DistanceLine(Point a, Point b, Point c) // a和b是线段的两个端点， c是检测点

{

Point ab = b - a;

Point ac = c-a;

float f = ab * ac;

if (f<0) return Distance(c, a);//C1处的点

float d = ab * ab;

if ( f>d) return Distance(c, b);//C2处的点，d=f*cos（theta）

f = f/d; 

Point D = a + f *ab; // c在ab线段上的投影点

return Distance(c, D);

}

这个算法计算量很少，在现在流行配置的计算机基本上在当中1秒钟可以检测出上百万个线段

这个是检测一个点和一个线段之间的最短距离的

对于一个系统当中存在大量的线段需要检测的时候，应该把线段按照区域划分成组，建立一个包围盒

先检测点是否在包围盒内部，然后再进入组内检测具体的线段