如何判断一条线是否与一个矩形相交

Question

我已经查看了这个问题，但答案对我来说太长了:

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

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

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

提前感谢。

- Daniel Peñalba

---

你是在说一个直线，还是一条线段？例如，如果这两个点都在矩形内部，那么这条线是否相交？ - naught101

请查看此链接：http://www.jeffreythompson.org/collision-detection/line-rect.php - ashleedawg

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;
    }

- HABJAN

---

@Habjan：谢谢，简单明了。最佳答案。这个有测试过吗？ - Daniel Peñalba

@Daniel Peñalba：我做了几个测试 :-) - HABJAN

@HABJAN：感谢更新。我认为条件是（r.Contains(p1) || r.Contains(p2)）。如果任何一个点在矩形内部，那么这条线就相交了。 - Daniel Peñalba

可以有人解释一下"implementation"的意思吗？不是完全清楚...谢谢。 - Marko

@Marko：我同意，变量命名尤其让人感到不清晰。但是一个简单的算法（假设你的矩形有水平和垂直线）是：获取垂直线的x值，检查每个x处线的y值。然后获取水平线的y值。如果两条线的y值都大于顶部矩形的y值，或者两条线的y值都小于底部矩形的y值，则您的线不相交。否则，它会相交。 - naught101

Answer 2

很遗憾，错误答案被投票选中。计算实际交点非常昂贵，你只需要进行比较。寻找的关键词是“线段裁剪”(http://en.wikipedia.org/wiki/Line_clipping)。维基百科推荐使用Cohen-Sutherland算法(http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland)来快速拒绝，这可能是最常见的情况。维基百科页面上有一个C++实现。如果你不想实际裁剪线段，可以跳过大部分内容。 @Johann的答案看起来与该算法非常相似，但我没有详细研究过。

- JPE

---

非常好的答案。是的，Johann的代码看起来更好。谢谢你的解释。 - Xtro

Answer 3

暴力算法...

首先检查矩形是否在线段端点的左侧或右侧：

• 确定线段端点的最左和最右X值：XMIN和XMAX
• 如果Rect.Left > XMAX，则没有交点。
• 如果Rect.Right < XMIN，则没有交点。

然后，如果以上内容不足以排除交点，请检查矩形是否在线段端点上方或下方：

• 确定线段端点的最高和最低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.Top < LINEYRECTRIGHT && Rect.Top < LINEYRECTLEFT，则没有交点。

然后，如果您到达这里：

• 交点。

注意：我相信有一种更优雅的代数解法，但用笔和纸几何地执行这些步骤很容易理解。

一些未经测试和编译的代码如下：

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;
}

- Johann Gerell

---

正如JPE在他的回答中提到的那样，你的代码比得到赞同的答案要好得多。 - Xtro

这个答案似乎是针对线段的，而不是（无限）直线。 - naught101

@naught101 - 这就是所要求的。 - Johann Gerell

这个问题没有提到线段。两个点也可以定义一条实际的直线。但是，是的，这个问题有点含糊不清。 - naught101

这个答案需要注意的是，虽然对于X，我们几乎可以肯定地预期X会随着向右移动而增加，但对于Y来说就不那么确定了。在某些情况下，Y会随着向下移动而增加，在其他情况下，Y会像本答案所假设的那样随着向上移动而增加。 - Gerard

Answer 4

这段代码具有更好的性能：

    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);
    }

- Wojtpl2

Answer 5

我采用了HABJAN的解决方案，它运作良好，并将其转换为Objective-C。Objective-C代码如下：

bool LineIntersectsLine(CGPoint l1p1, CGPoint l1p2, CGPoint l2p1, CGPoint l2p2)
{
    CGFloat q = (l1p1.y - l2p1.y) * (l2p2.x - l2p1.x) - (l1p1.x - l2p1.x) * (l2p2.y - l2p1.y);
    CGFloat 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;
}

bool LineIntersectsRect(CGPoint p1, CGPoint p2, CGRect r)
{
    return LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y + r.size.height)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y)) ||
    (CGRectContainsPoint(r, p1) && CGRectContainsPoint(r, p2));
}

很感谢HABJAN。我会备注，一开始我写了自己的例程来检查沿着梯度的每个点，并且我尽了最大努力来最大化性能，但这立刻快得多了。

- John Bushnell

---

来自Objective-C团队的感谢！ - Stanislav Pankevich

Answer 6

对于Unity（反转y轴！）。这种方法解决了其他方法在此处遇到的除以零问题：

using System;
using UnityEngine;

namespace Util {
    public static class Math2D {

        public static bool Intersects(Vector2 a, Vector2 b, Rect r) {
            var minX = Math.Min(a.x, b.x);
            var maxX = Math.Max(a.x, b.x);
            var minY = Math.Min(a.y, b.y);
            var maxY = Math.Max(a.y, b.y);

            if (r.xMin > maxX || r.xMax < minX) {
                return false;
            }

            if (r.yMin > maxY || r.yMax < minY) {
                return false;
            }

            if (r.xMin < minX && maxX < r.xMax) {
                return true;
            }

            if (r.yMin < minY && maxY < r.yMax) {
                return true;
            }

            Func<float, float> yForX = x => a.y - (x - a.x) * ((a.y - b.y) / (b.x - a.x));

            var yAtRectLeft = yForX(r.xMin);
            var yAtRectRight = yForX(r.xMax);

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

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

            return true;
        }
    }
}

- vincent

Answer 7

没有一个简单的预定义的.NET方法可以调用来完成这个任务。然而，使用Win32 API，有一种相当简单的方法来实现它（在实现方面很容易，但性能并不是强项）：LineDDA

BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)

该函数为要绘制的每个像素调用回调函数。在此函数中，您可以检查像素是否在矩形内 - 如果找到一个，则相交。

正如我所说，这不是最快的解决方案，但非常容易实现。要在C#中使用它，您当然需要从gdi32.dll中导入DllImport。

[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);

- Thalur

Answer 8

最简单的计算几何技术就是遍历多边形的线段，看它是否与任何一个相交，因为如果相交，则必定也与多边形相交。

这种方法（以及大部分计算几何）唯一需要注意的是我们必须小心处理边缘情况。如果线在矩形上交叉于一个点-我们将其视为相交还是不相交？在实现时要小心。

编辑：线段相交计算的典型工具是LeftOf(Ray, Point)测试，它返回点是否在射线左侧。给定一条线段l（我们用作射线）和包含点a和b的线段，如果一个点在左侧而另一个点不在左侧，则该线段与线相交：

(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))

同样，你需要注意边缘情况，当点在直线上时，但这取决于你如何定义交点。

- ceyko

---

如果您与多边形的任何线段相交，那么您一定会与该多边形相交吗？穿过矩形一侧但未到达另一侧的线仍然会与矩形相交... - Dan Puzey

但这是一条线。它不可能穿过一个线段，然后停在矩形的中间。你想的是线段。我想我可能误解了问题的意思，不过... - ceyko

如果一条线没有端点，那么它与其他线的交点数量永远不可能是奇数。 - Dave Rager

@Dave Eek，你是对的。我就把奇偶性那一段删掉——很明显，如果直线与任何线段相交，则它必然相交于多边形。 @Dan 是的，我更倾向于数学背景，所以我认为直线==无限长线段。 - ceyko

我认为原始回答更好，实际上：如果矩形的一条边是线段的子线，则该线只会与矩形的一侧相交，并且不会穿过矩形 - 例如：它是矩形的切线。 - naught101