查找线段与框相交的位置

Question

我想找出一堆线段夹在它们周围的 window 中的位置。我看到了 Liang–Barsky 算法，但这似乎假设段已经剪裁了 window 的边缘，而这些没有。

假设我有一个从 (0,0) 到 (26,16) 的 window，以及以下部分：

(7,6) - (16,3)
(10,6) - (19,6)
(13,10) - (21,3)
(16,12) - (19,14)

插图：

我想我需要将线段扩展到某个 X 或 Y 点，直到它们到达 window 的边缘，但我不知道如何做。

如何找到这些线段（转换为线？）夹入 window 边缘的点？我将在 C# 中实现它，但这与语言无关。

Answer 1

如果你有两条线段P和Q，点

P0 - P1
Q0 - Q1

线方程是

P = P0 + t(P1 - P0)
Q = Q0 + r(Q1 - Q0)

然后要找出它们在扩展后相交的位置，您需要求解以下等式 t 和 r

P0 + t(P1 - P0) = Q0 + r(Q1 - Q0)

下面的代码可以做到这一点。（从我自己的代码库中提取）

    public static (double t, double r )? SolveIntersect(this Segment2D P, Segment2D Q)
    {
        // a-d are the entries of a 2x2 matrix
        var a = P.P1.X - P.P0.X;
        var b = -Q.P1.X + Q.P0.X;
        var c = P.P1.Y - P.P0.Y;
        var d = -Q.P1.Y + Q.P0.Y;

        var det = a*d - b*c;
        if (Math.Abs( det ) < Utility.ZERO_TOLERANCE)
            return null;

        var x = Q.P0.X - P.P0.X;
        var y = Q.P0.Y - P.P0.Y;

        var t = 1/det*(d*x - b*y);
        var r = 1/det*(-c*x + a*y);

        return (t, r);

    }

如果函数返回null，则表示直线是平行的，不能相交。如果有返回结果就可以了

    var result = SolveIntersect( P, Q );
    if (result != null)
    {
        var ( t, r) = result.Value;
        var p = P.P0 + t * (P.P1 - P.P0);
        var q = Q.P0 + t * (Q.P1 - Q.P0);
        // p and q are the same point of course
    }

延长的线段通常会与多个框边相交，但只有一个交点会在框内。你可以很容易地检查这个。

   bool IsInBox(Point corner0, Point corner1, Point test) =>
      (test.X > corner0.X && test.X < corner1.X && test.Y > corner0.Y && test.Y < corner1.Y ;

这应该可以为您提供将线条延伸到盒子边缘所需的一切。

Answer 2

我设法解决了这个问题。

我可以将我的线延伸到盒子的边缘，方法是首先找到我的线的方程，然后求解每边的 X 和 Y 以获得它们对应的点.这需要将 max 和 min Y 以及 max 和 min X 传递到以下函数中，返回 4 个值。如果点在框的边界之外，可以忽略。

我的代码在 C# 中，并且正在为 EMGU LineSegment2D 制作扩展方法。这是 OpenCv 的 .NET 包装器。

我的代码：

    public static float GetYIntersection(this LineSegment2D line, float x)
    {
        Point p1 = line.P1;
        Point p2 = line.P2;

        float dx = p2.X - p1.X;
        if(dx == 0)
        {
            return float.NaN;
        }

        float m = (p2.Y - p1.Y) / dx; //Slope
        float b = p1.Y - (m * p1.X); //Y-Intercept
        return m * x + b;
    }

    public static float GetXIntersection(this LineSegment2D line, float y)
    {
        Point p1 = line.P1;
        Point p2 = line.P2;

        float dx = p2.X - p1.X;
        if (dx == 0)
        {
            return float.NaN;
        }

        float m = (p2.Y - p1.Y) / dx; //Slope
        float b = p1.Y - (m * p1.X); //Y-Intercept
        return (y - b) / m;
    }

然后我可以取这些点，检查它们是否在框的边界内，丢弃不在框内的点，删除重复的点（线直接进入角落）。这将给我留下一个 x 和一个 y 值，然后我可以将它们与我传递给函数的相应最小或最大 Y 或 X 值配对2分。然后我可以用这两点制作我的新片段。

Answer 3

Wiki 对 Liang-Barsky 算法的描述还不错，但是代码有问题。

注意：此算法旨在尽快丢弃 条没有交叉点的线。如果大部分线都与矩形相交，那么从你的答案来看可能会更有效，否则 L-B 算法获胜。

This page详细介绍了方法，并包含简洁有效的代码：

// Liang-Barsky function by Daniel White @ http://www.skytopia.com/project/articles/compsci/clipping.html
// This function inputs 8 numbers, and outputs 4 new numbers (plus a boolean value to say whether the clipped line is drawn at all).
//
bool LiangBarsky (double edgeLeft, double edgeRight, double edgeBottom, double edgeTop,   // Define the x/y clipping values for the border.
                  double x0src, double y0src, double x1src, double y1src,                 // Define the start and end points of the line.
                  double &x0clip, double &y0clip, double &x1clip, double &y1clip)         // The output values, so declare these outside.
{

    double t0 = 0.0;    double t1 = 1.0;
    double xdelta = x1src-x0src;
    double ydelta = y1src-y0src;
    double p,q,r;

    for(int edge=0; edge<4; edge++) {   // Traverse through left, right, bottom, top edges.
        if (edge==0) {  p = -xdelta;    q = -(edgeLeft-x0src);  }
        if (edge==1) {  p = xdelta;     q =  (edgeRight-x0src); }
        if (edge==2) {  p = -ydelta;    q = -(edgeBottom-y0src);}
        if (edge==3) {  p = ydelta;     q =  (edgeTop-y0src);   }   

        if(p==0 && q<0) return false;   // Don't draw line at all. (parallel line outside)

        r = q/p; 

        if(p<0) {
            if(r>t1) return false;         // Don't draw line at all.
            else if(r>t0) t0=r;            // Line is clipped!
        } else if(p>0) {
            if(r<t0) return false;      // Don't draw line at all.
            else if(r<t1) t1=r;         // Line is clipped!
        }
    }

    x0clip = x0src + t0*xdelta;
    y0clip = y0src + t0*ydelta;
    x1clip = x0src + t1*xdelta;
    y1clip = y0src + t1*ydelta;

    return true;        // (clipped) line is drawn
}

查找线段与框相交的位置

Find where line-segments intersect with a box

language-agnostic

math

geometry

lines