如何检查线段是否与矩形相交？

Question

如果您有两个点(x1,y1)和(x2,y2)，表示矩形的两个相对角落，和另外两个点(x3,y3)和(x4,y4)，表示线段的两个端点，您如何检查线段是否与矩形相交？

（该线段是仅包含给定端点的线段。它不是由这两个点定义的无限长度线。）

- omega

---

可能是line-rectangle collision detection的重复问题。 - templatetypedef

你的语句被称为“段落”。 - kassak

Answer 1

一种非常简单的选择是使用标准算法检查两条线段是否相交，以检查线段是否与构成盒子角落的四个线段中的任何一个相交。 检查两条线段是否相交在计算上非常高效，因此我预计这可以运行得非常快。

希望这能帮到你！

- templatetypedef

---

@templatetypedef 提出的思路无法处理一种情况：线段的两个端点都在矩形内部。但是这种情况很容易检查：x1 < x3 && x3 < x2 && y1 < y3 && y3 < y2。 - lrineau

@lrineau 除非它包含在矩形中，否则它不会与矩形相交。 - Mark Ping

这取决于你是只考虑矩形的实体部分，还是同时考虑它的边界。 - lrineau

如何处理线段直接通过矩形角落的情况，从而导致与触碰该角落两侧的矩形的交点检查失败？ - Walt D

如果线段碰到了角落，那么碰撞检测不会通过吗？假设您对每条边都进行了包容性检查，那么应该没问题。 - templatetypedef

@templatetypedef：没错，你说得对。我以为是舍入误差，但我的线段交点代码只是进行了排他性检查，而不是包容性检查。谢谢！（不过，我仍然想知道是否可能存在舍入误差导致问题的情况。） - Walt D

Answer 2

为了理解如何推导出测试线段是否与矩形相交的公式，重要的是记住向量点积的属性。

将线段表示为单位向量和线段起点与原点之间的距离。以下是一些C#代码，用于从PointF变量a_ptStart和a_ptEnd计算该值，使用Vector：

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));

您还需要计算线段的垂直向量及其与原点的距离。通过旋转单位向量90°很容易。

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));

假设矩形的四个角落分别用名为 vecRect1、vecRect2、vecRect3 和 vecRect4 的向量变量表示，计算该线段与目标边界矩形的四个角之间的距离：

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
    Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
    Math.Max(dPerpLineDist3, dPerpLineDist4)));

如果所有距离都是正数，或者所有距离都是负数，则矩形在直线的一侧或另一侧，因此没有交点。（零范围矩形被认为与任何线段不相交。）

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
        || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
    /* no intersection */;

接下来，将目标边界矩形的四个角投影到线段上。这样可以得到线段起点与矩形角投影在该线段上的距离。

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
    Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
    Math.Max(dDistLine3, dDistLine4)));

如果矩形的点不在线段的范围内，则不存在交集。

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
    /* no intersection */;

我相信这已经足够了。

- ulatekh

---

这个方法适用于三维吗？假设我们有矩形的法线。通过线段方向和法线，我们可以得到第三个方向，它垂直于它们两个，因此我们可以计算出'vecPerpLine'。剩下的就是使用点积和距离相减。这对我来说很有意义。有人可以评论我的想法吗？ - kotu

Answer 3

使用线段的方向向量获取矩形的所有4个顶点（角落）的点积。如果所有4个值都具有相同符号，则所有顶点位于该直线的同一侧（不是线段，而是无限线），因此该直线不与矩形相交。这种方法仅适用于2D交集检测。这可用于快速过滤大部分对象（仅使用乘法和加法）。对于线段而非直线，您必须进行进一步的检查。

- Srinivasan

---

我一直在思考这个问题...它是不正确的。所有的顶点可以位于线的同一侧，但仍然产生相反符号的点积。而且使用方向向量并没有考虑到线实际上所在的位置。一个人可以选择两条平行线：一条与矩形相交，另一条则不相交。由于它们的方向相同，四个点积将为两条线产生相同的值，这显然与定理相矛盾。尽管最初的想法很好，但我必须给它打-1分。 - Martijn Courteaux

这个答案看起来很混乱？它消除了线的任何位置数据，因此仅对通过原点的线有效。即使如此，它也不适用于通过原点的线，想想一下线方向向量（1/√2，1/√2）和矩形（5,10），（15,10），（5,0），（15,0）。所有点积都是正的，但它们相交了。 - Dominic Newman

如果您采用法向量的方向，它可能会起作用，但对于不经过原点的线仍然无效。不过，您可以通过将所有坐标偏移此量来解决这个问题。 - Dominic Newman