我建议简单地对构成矩形的每个线段(边缘)进行线段线段交叉检查。这是我多年前编写的线段相交检测算法,是从我的一个旧 XNA 项目中挖掘出来的:
// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
intersection = Vector2.Zero;
Vector2 b = a2 - a1;
Vector2 d = b2 - b1;
float bDotDPerp = b.X * d.Y - b.Y * d.X;
// if b dot d == 0, it means the lines are parallel so have infinite intersection points
if (bDotDPerp == 0)
return false;
Vector2 c = b1 - a1;
float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
if (t < 0 || t > 1)
return false;
float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
if (u < 0 || u > 1)
return false;
intersection = a1 + t * b;
return true;
}
我将把每条边输入到上述方法中并收集结果作为读者的练习:)
编辑一年后,现在我已经上大学并完成了图形课程:
看看科恩-萨瑟兰算法当您有大量线且其中大多数线不与矩形相交时,可以有效地执行此操作。它使用 9 段网格,并将线的每个端点放置在所述网格的区域中:
使用它我们可以判断是否不会有任何线相交:
例如这里CD
不会与矩形相交(在第一张图像中以红色显示),因为两者C
and D
都在顶行并且都不会AB
。对于直线可能与矩形相交的地方,我们必须尝试直线与直线的相交。
他们对各部分进行编号/标记的方式使我们能够简单地执行x AND y != 0
(where x
and y
是每个线端点的部分标签)以确定是否不会有交叉点。
使用这种方法意味着我们的线与线的交叉点要少得多,这大大加快了整个过程。