将四边形与轴对齐的矩形相交？
Intersect quadrilateral with axis-aligned rectangle?
如何有效地测试轴对齐的矩形 R
与漂亮的四边形 Q 相交？
- 很好的意思是：Q 是凸的（不是人字形）和非自相交（不是领结，不是退化）。
- 只是二维的。
- 就yes/no。我不需要实际的交叉区域。
- 编辑： Q 和 R 可以打开或关闭，只要方便即可。
显然可以测试 Q 的每条边是否与 R 相交。
这将问题简化为
How to test if a line segment intersects an axis-aligned rectange in 2D?.
但是就像R的轴对齐被Liang-Barsky利用一样
比 Cohen-Sutherland 更快，
Q 的属性可能会被利用来多次获得比 运行 Liang-Barsky 更快的东西。
因此，多边形-矩形相交算法
Sutherland–Hodgman、Vatti 和 Greiner-Hormann 都让 Q 为非凸的，不太可能是最优的。
Area of rectangle-rectangle intersection 看起来很有希望，即使它没有利用 R 的轴对齐。
注意不要忽略 Q 完全覆盖 R 的情况，反之亦然，因为边缘测试会给出假阴性。
概念上的一种方法：
- 将R视为两个轴对齐的无限带的交集，垂直带[x0,x1]和水平带[y0,y1]。
- 令xmin和xmax表示Q与水平带[y0,y1]相交的范围；如果 [xmin,xmax] ∩ [x0,x1] 非空，则 Q 与 R 相交。
执行方面：
- 初始化 xmin := +inf; xmax := -inf
对于Q的每条边pq，p=(px,py) q =(qx,qy), py ≥ qy:
一个。如果 qy > y1 或 y0 > py，忽略这条边，检查下一条。
b。如果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).
如果 xmin < x1 且 xmax > x0，则 Q 与 R 相交。
1) 构造Q的轴对齐边界框。测试它不与 R.
相交
2) 对于Q的每条边E，测试R的四个顶点是否都在E的支撑线的外侧。 （使用边的隐式方程，A.x + B.y + c <> 0。）
当且仅当其中任何一个测试成功时，才没有交集。
如何有效地测试轴对齐的矩形 R 与漂亮的四边形 Q 相交？
- 很好的意思是：Q 是凸的（不是人字形）和非自相交（不是领结，不是退化）。
- 只是二维的。
- 就yes/no。我不需要实际的交叉区域。
- 编辑： Q 和 R 可以打开或关闭，只要方便即可。
显然可以测试 Q 的每条边是否与 R 相交。 这将问题简化为 How to test if a line segment intersects an axis-aligned rectange in 2D?.
但是就像R的轴对齐被Liang-Barsky利用一样 比 Cohen-Sutherland 更快， Q 的属性可能会被利用来多次获得比 运行 Liang-Barsky 更快的东西。
因此，多边形-矩形相交算法 Sutherland–Hodgman、Vatti 和 Greiner-Hormann 都让 Q 为非凸的，不太可能是最优的。
Area of rectangle-rectangle intersection 看起来很有希望，即使它没有利用 R 的轴对齐。
注意不要忽略 Q 完全覆盖 R 的情况，反之亦然，因为边缘测试会给出假阴性。
概念上的一种方法：
- 将R视为两个轴对齐的无限带的交集，垂直带[x0,x1]和水平带[y0,y1]。
- 令xmin和xmax表示Q与水平带[y0,y1]相交的范围；如果 [xmin,xmax] ∩ [x0,x1] 非空，则 Q 与 R 相交。
执行方面：
- 初始化 xmin := +inf; xmax := -inf
对于Q的每条边pq，p=(px,py) q =(qx,qy), py ≥ qy:
一个。如果 qy > y1 或 y0 > py，忽略这条边，检查下一条。
b。如果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).
如果 xmin < x1 且 xmax > x0，则 Q 与 R 相交。
1) 构造Q的轴对齐边界框。测试它不与 R.
相交2) 对于Q的每条边E，测试R的四个顶点是否都在E的支撑线的外侧。 （使用边的隐式方程，A.x + B.y + c <> 0。）
当且仅当其中任何一个测试成功时，才没有交集。