如何知道线是否与矩形相交

Question

我已经查看了这个问题,但答案对我来说非常大:

如何知道一条线是否与C#中的平面相交？ - 基本2D几何

是否有任何.NET方法可以知道由两个点定义的直线是否与矩形相交？

public bool Intersects(Point a, Point b, Rectangle r)
{
   // return true if the line intersects the rectangle
   // false otherwise
}

提前致谢.

Answer 1

    public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
    {
        return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
               (r.Contains(p1) && r.Contains(p2));
    }

    private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
    {
        float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
        float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);

        if( d == 0 )
        {
            return false;
        }

        float r = q / d;

        q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
        float s = q / d;

        if( r < 0 || r > 1 || s < 0 || s > 1 )
        {
            return false;
        }

        return true;
    }

Answer 2

不幸的是,错误的答案已被否决.计算实际交叉点的成本太高,您只需要进行比较.要查找的关键字是"Line Clipping"(http://en.wikipedia.org/wiki/Line_clipping).当您想要快速拒绝时,维基百科推荐使用Cohen-Sutherland算法(http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland),这可能是最常见的情况.维基百科页面上有一个C++实现.如果您对实际剪切线不感兴趣,可以跳过大部分线.@Johann的答案看起来与该算法非常相似,但我没有详细研究它.

Answer 3

这段代码有更好的性能：

    public static bool SegmentIntersectRectangle(
        double rectangleMinX,
        double rectangleMinY,
        double rectangleMaxX,
        double rectangleMaxY,
        double p1X,
        double p1Y,
        double p2X,
        double p2Y)
    {
        // Find min and max X for the segment
        double minX = p1X;
        double maxX = p2X;

        if (p1X > p2X)
        {
            minX = p2X;
            maxX = p1X;
        }

        // Find the intersection of the segment's and rectangle's x-projections
        if (maxX > rectangleMaxX)
        {
            maxX = rectangleMaxX;
        }

        if (minX < rectangleMinX)
        {
            minX = rectangleMinX;
        }

        if (minX > maxX) // If their projections do not intersect return false
        {
            return false;
        }

        // Find corresponding min and max Y for min and max X we found before
        double minY = p1Y;
        double maxY = p2Y;

        double dx = p2X - p1X;

        if (Math.Abs(dx) > 0.0000001)
        {
            double a = (p2Y - p1Y)/dx;
            double b = p1Y - a*p1X;
            minY = a*minX + b;
            maxY = a*maxX + b;
        }

        if (minY > maxY)
        {
            double tmp = maxY;
            maxY = minY;
            minY = tmp;
        }

        // Find the intersection of the segment's and rectangle's y-projections
        if (maxY > rectangleMaxY)
        {
            maxY = rectangleMaxY;
        }

        if (minY < rectangleMinY)
        {
            minY = rectangleMinY;
        }

        if (minY > maxY) // If Y-projections do not intersect return false
        {
            return false;
        }

        return true;
    }

您还可以在 JS 演示中检查它是如何工作的： http: //jsfiddle.net/77eej/2/

如果你有两个点和矩形，你可以这样调用这个函数：

    public static bool LineIntersectsRect(Point p1, Point p2, Rect r)
    {
        return SegmentIntersectRectangle(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
    }

Answer 4

蛮力算法......

首先检查rect是否在行端点的左侧或右侧:

• 建立线端点的最左边和最右边的X值:XMIN和XMAX
• 如果Rect.Left> XMAX,则没有交集.
• 如果Rect.Right <XMIN,则没有交集.

然后,如果上述内容不足以排除交集,请检查rect是否在行终点之上或之下:

• 建立线端点的最顶部和最底部Y值:YMAX和YMIN
• 如果Rect.Bottom> YMAX,则没有交集.
• 如果Rect.Top <YMIN,则没有交集.

然后,如果以上不足以排除交集,则需要检查线的方程式y = m * x + b,以查看矩形是否在线上方:

• 在Rect.Left和Rect.Right上建立线的Y值:LINEYRECTLEFT和LINEYRECTRIGHT
• 如果Rect.Bottom> LINEYRECTRIGHT && Rect.Bottom> LINEYRECTLEFT,则没有交集.

然后,如果上述内容不足以排除交集,则需要检查rect是否在行下方:

• 如果Rect.Top <LINEYRECTRIGHT && Rect.Top <LINEYRECTLEFT,那么没有交集.

然后,如果你到这里:

• 路口.

NB我确信有更优雅的代数解决方案,但用笔和纸几何方式执行这些步骤很容易理解.

一些未经测试和未编译的代码:

public struct Line
{
    public int XMin { get { ... } }
    public int XMax { get { ... } }

    public int YMin { get { ... } }
    public int YMax { get { ... } }

    public Line(Point a, Point b) { ... }

    public float CalculateYForX(int x) { ... }
}

public bool Intersects(Point a, Point b, Rectangle r)
{
    var line = new Line(a, b);

    if (r.Left > line.XMax || r.Right < line.XMin)
    {
        return false;
    }

    if (r.Top < line.YMin || r.Bottom > line.YMax)
    {
        return false;
    }

    var yAtRectLeft = line.CalculateYForX(r.Left);
    var yAtRectRight = line.CalculateYForX(r.Right);

    if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight)
    {
        return false;
    }

    if (r.Top < yAtRectLeft && r.Top < yAtRectRight)
    {
        return false;
    }

    return true;
}