41

如果您有 2 个点 (x1, y1) 和 (x2, y2)，它们代表一个矩形的两个对角，还有 2 个其他点，(x3,y3) 和 (x4,y4)，它们代表一个矩形的 2 个端点线段，如何检查线段是否与矩形相交？

（线段只是包含在给定端点之间的线段。它不是由这两个点定义的无限长线。）

4

3 回答 3

33

一个非常简单的选择是使用标准算法来检查两条线段是否相交，以检查线段是否与构成框角的四个线段中的任何一个相交。检查两条线段是否相交在计算上非常有效，所以我希望它可以运行得非常快。

希望这可以帮助！

于 2013-04-24T23:11:30.273 回答
1

得到所有4个顶点（矩形的角）与线段的方向向量的点积。如果所有 4 个值的符号相同，则所有顶点都位于直线的同一侧（不是线段，而是无限线），因此直线不与矩形相交。这种方法仅适用于二维交叉点检测。这可用于快速过滤其中的大多数（仅使用乘法和加法）。您必须对线段而不是线进行进一步检查。

于 2015-06-04T19:27:12.730 回答
1

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

将线段表示为单位向量以及线段起点与原点之间的距离。这是一些 C# 代码，用于从PointF变量a_ptStart和计算它a_ptEnd，使用 a 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));

假设矩形的四个角位于名为、、和的Vector变量中，计算线段与目标边界矩形的所有四个角之间的距离：vecRect1vecRect2vecRect3vecRect4

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 */;

我相信这就足够了。

于 2016-06-03T18:17:45.027 回答