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

王朝other·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

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

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

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

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

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

算法如下

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(a, c);

float d = ab * ab;

if ( f>d) return Distance(a, c);

f = f/d;

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

return Distance(a, D);

}

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

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

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

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航