加载中…
正文 字体大小:

点到线段的最短距离算法

(2013-02-21 19:14:42)
标签:

点到线段距离

矢量算法

最短距离

分类: 算法应用

点到线段最短距离的运算与点到直线的最短距离的运算二者之间存在一定的差别,即求点到线段最短距离时需要考虑参考点在沿线段方向的投影点是否在线段上,若在线段上才可采用点到直线距离公式,如图1所示。

                  点到线段的最短距离算法

1 a)最短距离为点P与其在线段AB上投影C之间的线段PC

                                        b)最短距离为点P与端点B(或A)所构成的线段PB(或PA

 

具体算法主要有以下三种:

1、方法——经典算法

该算法直接用高中时所学习到的解析几何知识对点到线段的距离进行求解。其基本思想是先判断点在线段端点、点在线上等等的特殊情况,逐步的由特殊到一般,当忽略点在线段上的特殊情况时,判断点到线段方向的垂线是否落在线段上的方法是通过比较横纵坐标的方式来判断,最后把不同的判断情况用不同的几何方式来进行处理计算得出结果。

由上面叙述的基本思路可以知道这种算法虽然很容易理解和接受,但从算法的实用性的角度分析还是有很大的缺点的,首先是算法复杂,计算量巨大,大量的比较判断、距离计算、角度计算等等,实际应用中往往是需要求由大量线段组成的折线到某点的最短距离,如此用这样的算法计算量是不能想象的。其次经典算法中使用的一些简化运算的函数不利于语言的重新包装,如果想换编程语言的话,就比较麻烦了。

2、方法二——面积算法

该方法主要是先判断投影点是否在线段上,投影点在线段延长线上时,最短距离长度为点到端点的线段长度;当投影点在线段上时,先使用海伦公式计算三角形面积,再计算出三角形的高,即为最短距离。

运用面积算法求解点到线段最短距离思路很清晰,也很容易理解。从效率方面考虑,比如需要多次计算平方、根号,这对于大量数据进行运算是负担很重的。求面积就必须把三条边长全部求出,并且用到的海伦公式也需要进行开方运算,计算过程显得繁琐。

3、方法三——矢量算法

矢量算法过程清晰,如果具有一定的空间几何基础,则是解决此类问题时应优先考虑的方法。当需要计算的数据量很大时,这种方式优势明显。

由于矢量具有方向性,故一些方向的判断直接根据其正负号就可以得知,使得其中的一些问题得以很简单的解决。

     用此方法考虑,我们只需要找到向量 点到线段的最短距离算法点到线段的最短距离算法方向上的投影,具体如下:

             点到线段的最短距离算法

上面的 点到线段的最短距离算法点到线段的最短距离算法方向上的单位向量,其意义是给所求向量确定方向。点到线段的最短距离算法是的两个向量的内积,且 点到线段的最短距离算法  ,其中θ为向量APAB之间的夹角。点到线段的最短距离算法是向量长度。

 

那么点到线段的最短距离算法即为上图中线段AC的长度值,不带有方向性。此数值与上述表征方向的 点到线段的最短距离算法整体构成有大小、有方向的新向量点到线段的最短距离算法,即为 点到线段的最短距离算法点到线段的最短距离算法方向上的投影向量,C为投影点。

根据得到的点到线段的最短距离算法,由向量的方向性可知:如果情况是上图(a)所示,那么0<r<1;如果是如图(b)所示的情况,那么r 1;如果是如图(c)所示的情况,那么得到r 0;

特殊情况如点在线段上、点在端点、点在线段延长线上等等的情况全部适用于此公式,只是作为特殊情况出现,无需另作讨论。这也是矢量算法思想的优势所在。

故根据r值的不同,最短距离𝑑可以计算为:   
                                      点到线段的最短距离算法

使用C#实现上述算法:

public static double PointToSegDist(double x, double y, double x1, double y1, double x2, double y2)

{

double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);

if (cross <= 0) return Math.Sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));


double d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

if (cross >= d2) return Math.Sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2));

 

double r = cross / d2;

double px = x1 + (x2 - x1) * r;

double py = y1 + (y2 - y1) * r;

return Math.Sqrt((x - px) * (x - px) + (py - y1) * (py - y1));

}

 

除了代码简单、计算量少的优点外,上述代码不依赖其它函数和自定义的数据结构,便于直接使用或者转换为其他编程语言(诸如C++java等)使用而无需做较大的改动。

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有