录十六

持之以恒

求点到线段的最短距离

点到线段的最短距离与点到直线的最短距离,二者在概念上是存在一定差异的。求点到线段最短距离时,需要考虑点在沿线段方向的投影点是否在线段上。若在线段上,点到线段的最短距离才等于点到直线的距离;否则,点到线段的最短距离则是点到线段某一端点的距离。如图所示:

x1.png

已知线段AB,和任意一点P,点P在线段方向上的投影为点C,则投影点C和线段AB的位置关系,可以分为以下三种情况,如图:

求点到线段的最段距离,可以先求出向量AC。则根据向量的基本运算,以及几何意义,有以下推导过程:

从将上面的推导结果,可以看到向量AC等于向量AB乘以一个标量u,则:

当0<u<1时,投影点C在线段上;当u≤0或u≥0时,投影点C在线段的两侧。所以点到线段最短距离d为:

算法理解了,代码实现很容易,下面附上完整的代码实现:

typedef struct Point2D
{
    float x;
    float y;
    
}Point2D;

float PointToSegDist(const Point2D& P1, const Point2D& P2, const Point2D& pt)
{
    float fDot = (P2.x - P1.x)*(pt.x - P1.x) + (P2.y - P1.y)*(pt.y - P1.y);
    if (fDot <= 0.0f)
    {
        return  sqrt((P1.x - pt.x)*(P1.x - pt.x) + (P1.y - pt.y)*(P1.y - pt.y));
    }
    
    float d2AB = (P1.x - P2.x)*(P1.x - P2.x) + (P1.y - P2.y)*(P1.y - P2.y);
    if (fDot >= d2AB)
    {
        return sqrt((P2.x - pt.x)*(P2.x - pt.x) + (P2.y - pt.y)*(P2.y - pt.y));
    }
    
    float u = fDot / d2AB;
    
    float AC_x = P1.x + (P2.x - P1.x) * u;
    float AC_y = P1.y + (P2.y - P1.y) * u;
    
    return sqrt((pt.x - AC_x) * (pt.x - AC_x) + (pt.y - AC_y) * (pt.y - AC_y));
}


发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © 1999-2019, lu16.com, All Rights Reserved