algorithm - 将四边形与轴对齐的矩形相交？

Question

如何有效地测试一个轴对齐的矩形 R 是否与一个漂亮的四边形 Q 相交？

• Nice 的意思是：Q 是凸的（不是 V 形）且非自相交的（不是领结，不是退化的）。
• 只是二维。
• 只是是/否。我不需要实际的交叉区域。
• 编辑： Q 和 R 可以打开或关闭，无论方便。

显然，对于 Q 的每个边，可以测试它是否与 R 相交。这将问题减少到 如何测试线段是否与二维中的轴对齐矩形相交？.

但是，就像 Liang-Barsky 利用 R 的轴对齐比 Cohen-Sutherland 更快一样，Q 的属性可能被利用来获得比多次运行 Liang-Barsky 更快的东西。

因此，多边形-矩形相交算法 Sutherland-Hodgman、Vatti 和 Greiner-Hormann，所有这些算法都让 Q 为非凸的，不太可能是最优的。

矩形-矩形相交的区域看起来很有希望，即使它没有利用 R 的轴对齐性。

Answer 1

注意不要忽略 Q 完全覆盖 R 的情况，反之亦然，因为边缘测试会给出假阴性。

从概念上讲，一种方法：

• 将 R 视为两个轴对齐的无限波段的交点，垂直波段 [x0,x1] 和水平波段 [y0,y1]。
• 令xmin和xmax代表Q与水平带[y0,y1]相交的程度；如果 [xmin,xmax] ∩ [x0,x1] 非空，则 Q 与 R 相交。

在执行方面：

1. 初始化 xmin := +inf; xmax := -inf

2. 对于 Q 的每条边pq，p =(px,py) q =(qx,qy)，其中 py ≥ qy：

   一个。如果 qy > y1 或 y0 > py，忽略这条边，并检查下一条。

   湾。如果 py > y1，令 (x,y1) 为pq与水平线 y = y1 的交点；否则设 x 为 px。

   C。更新 xmin = min(xmin,x); xmax = max(xmax,x)。

   d。如果 y0 > qy，令 (x,y0) 为pq与水平线 y = y0 的交点；否则令 x 为 qx。

   e. 更新 xmin = min(xmin,x); xmax = max(xmax,x)。

3. 如果 xmin < x1 且 xmax > x0，Q 与 R 相交。

Answer 2

1）构造Q的轴对齐边界框。测试它不与 R 相交。

2) 对于 Q 的每一条边 E，测试 R 的所有四个顶点都位于 E 的支撑线的外侧。（使用边缘的隐式方程，A.x + B.y + c <> 0。）

当且仅当这些测试中的任何一个成功时，才没有交集。