8

给定两条二维线段 A 和 B,我如何计算连接 A 和 B 的最短二维线段 C 的长度?

4

7 回答 7

7

考虑您的两条线段 A 和 B 分别由两个点表示:

由 A1(x,y)、A2(x,y) 表示的 A 线

线 B 由 B1(x,y) B2(x,y) 表示

首先使用此算法检查两条线是否相交。

如果它们确实相交,则两条线之间的距离为零,连接它们的线段就是交点。

如果它们不相交,请使用此方法:http ://paulbourke.net/geometry/pointlineplane/计算以下之间的最短距离:

  1. 点 A1 和线 B
  2. A2点和B线
  3. B1点和A线
  4. B2点和A线

这四个线段中最短的就是你的答案。

于 2009-02-12T13:57:16.190 回答
4

此页面包含您可能正在寻找的信息。

于 2009-02-12T13:12:00.760 回答
3

使用上述AfterlifeRob Parker算法的一般思想,这是一组方法的 C++ 版本,用于获取 2 个任意 2D 段之间的最小距离。这将处理重叠段、平行段、相交和非相交段。此外,它使用各种 epsilon 值来防止浮点不精确。最后,除了返回最小距离外,该算法还将为您提供最接近线段 2 的线段 1 上的点(如果线段相交,这也是交点)。如果需要,也可以返回最接近 [p1,p2] 的 [p3,p4] 上的点,但我将把它作为练习留给读者:)

// minimum distance (squared) between vertices, i.e. minimum segment length (squared)
#define EPSILON_MIN_VERTEX_DISTANCE_SQUARED 0.00000001

// An arbitrary tiny epsilon.  If you use float instead of double, you'll probably want to change this to something like 1E-7f
#define EPSILON_TINY 1.0E-14

// Arbitrary general epsilon.  Useful for places where you need more "slop" than EPSILON_TINY (which is most places).
// If you use float instead of double, you'll likely want to change this to something like 1.192092896E-04
#define EPSILON_GENERAL 1.192092896E-07

bool AreValuesEqual(double val1, double val2, double tolerance)
{
    if (val1 >= (val2 - tolerance) && val1 <= (val2 + tolerance))
    {
        return true;
    }

    return false;
}


double PointToPointDistanceSquared(double p1x, double p1y, double p2x, double p2y)
{
    double dx = p2x - p1x;
    double dy = p2y - p1y;
    return (dx * dx) + (dy * dy);
}


double PointSegmentDistanceSquared( double px, double py,
                                    double p1x, double p1y,
                                    double p2x, double p2y,
                                    double& t,
                                    double& qx, double& qy)
{
    double dx = p2x - p1x;
    double dy = p2y - p1y;
    double dp1x = px - p1x;
    double dp1y = py - p1y;
    const double segLenSquared = (dx * dx) + (dy * dy);
    if (AreValuesEqual(segLenSquared, 0.0, EPSILON_MIN_VERTEX_DISTANCE_SQUARED))
    {
        // segment is a point.
        qx = p1x;
        qy = p1y;
        t = 0.0;
        return ((dp1x * dp1x) + (dp1y * dp1y));
    }
    else
    {
        t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
        if (t <= EPSILON_TINY)
        {
            // intersects at or to the "left" of first segment vertex (p1x, p1y).  If t is approximately 0.0, then
            // intersection is at p1.  If t is less than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t >= -EPSILON_TINY)
            {
                // intersects at 1st segment vertex
                t = 0.0;
            }
            // set our 'intersection' point to p1.
            qx = p1x;
            qy = p1y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else if (t >= (1.0 - EPSILON_TINY))
        {
            // intersects at or to the "right" of second segment vertex (p2x, p2y).  If t is approximately 1.0, then
            // intersection is at p2.  If t is greater than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t <= (1.0 + EPSILON_TINY))
            {
                // intersects at 2nd segment vertex
                t = 1.0;
            }
            qx = p2x;
            qy = p2y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else
        {
            // The projection of the point to the point on the segment that is perpendicular succeeded and the point
            // is 'within' the bounds of the segment.  Set the intersection point as that projected point.
            qx = ((1.0 - t) * p1x) + (t * p2x);
            qy = ((1.0 - t) * p1y) + (t * p2y);
            // for debugging
            //ASSERT(AreValuesEqual(qx, p1x + (t * dx), EPSILON_TINY));
            //ASSERT(AreValuesEqual(qy, p1y + (t * dy), EPSILON_TINY));
        }
        // return the squared distance from p to the intersection point.
        double dpqx = px - qx;
        double dpqy = py - qy;
        return ((dpqx * dpqx) + (dpqy * dpqy));
    }
}


double SegmentSegmentDistanceSquared(   double p1x, double p1y,
                                        double p2x, double p2y,
                                        double p3x, double p3y,
                                        double p4x, double p4y,
                                        double& qx, double& qy)
{
    // check to make sure both segments are long enough (i.e. verts are farther apart than minimum allowed vert distance).
    // If 1 or both segments are shorter than this min length, treat them as a single point.
    double segLen12Squared = PointToPointDistanceSquared(p1x, p1y, p2x, p2y);
    double segLen34Squared = PointToPointDistanceSquared(p3x, p3y, p4x, p4y);
    double t = 0.0;
    double minDist2 = 1E+38;
    if (segLen12Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
    {
        qx = p1x;
        qy = p1y;
        if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
        {
            // point to point
            minDist2 = PointToPointDistanceSquared(p1x, p1y, p3x, p3y);
        }
        else
        {
            // point - seg
            minDist2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y);
        }
        return minDist2;
    }
    else if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
    {
        // seg - point
        minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy);
        return minDist2;
    }

    // if you have a point class and/or methods to do cross products, you can use those here.
    // This is what we're actually doing:
    // Point2D delta43(p4x - p3x, p4y - p3y);    // dir of p3 -> p4
    // Point2D delta12(p1x - p2x, p1y - p2y);    // dir of p2 -> p1
    // double d = delta12.Cross2D(delta43);
    double d = ((p4y - p3y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p3x));
    bool bParallel = AreValuesEqual(d, 0.0, EPSILON_GENERAL);

    if (!bParallel)
    {
        // segments are not parallel.  Check for intersection.
        // Point2D delta42(p4x - p2x, p4y - p2y);    // dir of p2 -> p4
        // t = 1.0 - (delta42.Cross2D(delta43) / d);
        t = 1.0 - ((((p4y - p3y) * (p4x - p2x)) - ((p4y - p2y) * (p4x - p3x))) / d);
        double seg12TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED / segLen12Squared);
        if (t >= -seg12TEps && t <= (1.0 + seg12TEps))
        {
            // inside [p1,p2].   Segments may intersect.
            // double s = 1.0 - (delta12.Cross2D(delta42) / d);
            double s = 1.0 - ((((p4y - p2y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p2x))) / d);
            double seg34TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED / segLen34Squared);
            if (s >= -seg34TEps && s <= (1.0 + seg34TEps))
            {
                // segments intersect!
                minDist2 = 0.0;
                qx = ((1.0 - t) * p1x) + (t * p2x);
                qy = ((1.0 - t) * p1y) + (t * p2y);
                // for debugging
                //double qsx = ((1.0 - s) * p3x) + (s * p4x);
                //double qsy = ((1.0 - s) * p3y) + (s * p4y);
                //ASSERT(AreValuesEqual(qx, qsx, EPSILON_MIN_VERTEX_DISTANCE_SQUARED));
                //ASSERT(AreValuesEqual(qy, qsy, EPSILON_MIN_VERTEX_DISTANCE_SQUARED));
                return minDist2;
            }
        }
    }

    // Segments do not intersect.   Find closest point and return dist.   No other way at this
    // point except to just brute-force check each segment end-point vs opposite segment.  The
    // minimum distance of those 4 tests is the closest point.
    double tmpQx, tmpQy, tmpD2;
    minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy);
    tmpD2 = PointSegmentDistanceSquared(p4x, p4y, p1x, p1y, p2x, p2y, t, tmpQx, tmpQy);
    if (tmpD2 < minDist2)
    {
        qx = tmpQx;
        qy = tmpQy;
        minDist2 = tmpD2;
    }
    tmpD2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy);
    if (tmpD2 < minDist2)
    {
        qx = p1x;
        qy = p1y;
        minDist2 = tmpD2;
    }
    tmpD2 = PointSegmentDistanceSquared(p2x, p2y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy);
    if (tmpD2 < minDist2)
    {
        qx = p2x;
        qy = p2y;
        minDist2 = tmpD2;
    }

    return minDist2;
}
于 2012-07-11T07:30:37.690 回答
2

Gernot Hoffmann论文(算法和 Pascal 代码):

http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf

于 2009-02-12T13:12:23.067 回答
2

快速提示:如果您想根据点比较距离,则无需计算平方根。

例如,要查看 P-to-Q 的距离是否小于 Q-to-R,只需检查(伪代码):

square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y)
于 2009-02-12T13:16:37.800 回答
2

Afterlife 说,“首先使用这个算法检查两条线是否相交”,但他没有说明他的意思是什么算法。显然,重要的是线段的交点而不是延长线;任何非平行线段(不包括未定义线的重合端点)都将相交,但线段之间的距离不一定为零。所以我认为他的意思是“线段”而不是“线”。

Afterlife 给出的链接是一种非常优雅的方法,可以找到一条线(或线段,或射线)上与另一个任意点的最近点。这适用于查找从每个端点到另一条线段的距离(将计算的参数 u 限制为对于线段或射线不小于 0,对于线段不大于 1),但它不处理一条线段上的内部点比任一端点更近的可能性,因为它们实际上相交,因此需要对相交进行额外检查。

至于确定线段交点的算法,一种方法是找到延长线的交点(如果平行则完成),然后确定该点是否在两条线段内,例如通过取从交点 T 到两个端点的向量的点积:

((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) * (Ty - A2y))

如果这是负数(或“零”),则 T 在 A1 和 A2 之间(或在一个端点处)。类似地检查其他线段。如果任一大于“零”,则线段不相交。当然,这取决于首先找到延长线的交点,这可能需要将每条线表示为方程并通过高斯归约(等)求解系统。

但可能有一种更直接的方法,无需求解交点,即取向量 (B1-A1) 和 (B2-A1) 的叉积以及向量 (B1-A2) 和(B2-A2)。如果这些叉积在同一方向,则 A1 和 A2 在 B 线的同一侧;如果它们在相反的方向上,那么它们在 B 线的相对两侧(如果为 0,则一个或两个都B 线上)。同样检查向量 (A1-B1) 和 (A2-B1) 以及 (A1-B2) 和 (A2-B2) 的叉积。如果这些叉积中的任何一个为“零”,或者两条线段的端点都落在另一条线的相对两侧,则线段本身必须相交,否则它们不会相交。

当然,您需要一个方便的公式来计算两个向量坐标的叉积。或者,如果您可以确定角度(正或负),则不需要实际的叉积,因为它是我们实际关心的向量之间的角度方向(或角度的正弦,真的) . 但我认为叉积(二维)的公式很简单:

交叉(V1,V2) = (V1x * V2y) - (V2x * V1y)

这是 3-D 叉积向量的 z 轴分量(其中 x 和 y 分量必须为零,因为初始向量在平面 z=0 中),因此您可以简单地查看符号(或“零”)。

因此,您可以使用这两种方法之一来检查 Afterlife 描述的算法中的线段相交(参考链接)。

于 2009-02-15T21:54:30.390 回答
0

这个页面有一个很好的简短描述,用于查找两行之间的最短距离,尽管@strager 的链接包含一些代码(在 Fortran 中!)

于 2009-02-12T13:19:22.787 回答