graphics - 如何测试线段是否与二维轴对齐矩形相交？

Question

如何测试线段是否与二维轴对齐矩形相交？该段由其两端定义:p1、p2。该矩形由左上角和右下角点定义。

Answer 1

原始海报想要检测线段和多边形之间的交点。如果有的话，无需定位交叉路口。如果这就是您的意思，那么您可以比梁-巴斯基或科恩-萨瑟兰做更少的工作:

设线段端点为 p1=(x1 y1) 和 p2=(x2 y2)。
令矩形的角为 (xBL yBL) 和 (xTR yTR)。

那么你所要做的就是

A.检查矩形的所有四个角是否在线的同一侧。通过 p1 和 p2 的直线的隐式方程为:

F(xy) = (y2-y1)*x + (x1-x2)*y + (x2*y1-x1*y2)

如果 F(x y) = 0，则 (x y) 接通。
如果 F(x y) > 0，则 (x y) 在线“上方”。
如果 F(x y) < 0，则 (x y) 在线“下方”。

将所有四个角代入 F(x y)。如果它们都是负数或都是正数，则不存在交集。如果有些是正面的，有些是负面的，则转到步骤 B。

B.将端点投影到 x 轴上，并检查线段的阴影是否与多边形的阴影相交。在 y 轴上重复:

如果 (x1 > xTR 且 x2 > xTR)，则没有交集(线位于矩形的右侧)。
如果 (x1 < xBL 且 x2 < xBL)，则没有交点(线位于矩形的左侧)。
如果 (y1 > yTR 且 y2 > yTR)，则没有交点(线位于矩形上方)。
如果 (y1 < yBL 且 y2 < yBL)，则没有交点(线位于矩形下方)。
否则，有一个交集。执行 Cohen-Sutherland 或您问题的其他答案中提到的任何代码。

当然，您可以先执行 B，然后再执行 A。

阿莱霍