php - 给定每个矩形的左上角(x0，y0)和右下角(x1，y1)的数学/算法/JS : How to determine if 2+ rectangles intersect,

Question

我遇到了完成我的申请所需的数学问题，所以我寻求帮助。

给定 2 个(或更多，但基本上是 2 个)矩形，每个矩形有 2 个已知点:Top-left(x1, y1) 和 Bottom-right(x2, y2)(如果需要解决问题，我可以通过这些信息找到长度)。

TL(x1, y1)
   +-----------------+
   |                 |
   |                 |       TL(x3, y3)
   |                 |            +---------------------------+
   +-----------------+            |                           |
               BR(x2, y2)         +---------------------------+
                                                         BR(x4, y4)

有没有办法确定它们是否有交集，在面积上，我的意思是，如果这个矩形的任何部分位于另一个矩形的任何部分上？

我已经搜索并找到了一些帮助，但它并没有解决问题:

There are 4 conditions in which the two rectangles will not intersect:

• The left edge of one rectangle is on the right side of the right edge of the other one, means that the first one is completely laid on the right side of the second one, no intersection.

• The right edge of one rectangle is on the left side of the left edge of the other one, means that the first one is completely laid on the left side of the second one, no intersection.

• The top edge of one rectangle is under the bottom edge of the other one, means that the first one is completely laid under the second one, no intersection.

• The bottom edge of one rectangle is above the top edge of the other one, means that the first one is completely laid above the second one, no intersection.

所以我尝试颠倒条件，即如果上述 4 种情况不发生，则矩形可能 相交。但是我还是能找到2个矩形不满足任何条件，仍然不相交的条件(如上图)。

非常感谢任何帮助，请告诉我实现它的方法或算法或代码(请只使用 JS 和 PHP)。

非常感谢!

[x]

Answer 1

一种用于任意数量的交叉点检测(“重叠”)的算法 矩形可以按如下方式工作。使用了两个数据结构。

• 矩形左右边缘 x 坐标的排序列表 S。
• 安 interval tree由矩形的 y 坐标(底部/顶部)给出的间隔 T。

算法遍历 x 坐标的排序列表 S:

1. 如果当前 x 坐标是矩形 R 的左边缘，则 将 R 的 y 坐标 [y1, y2] 与区间树 T 进行比较。 如果发现重叠，则算法停止并报告 OVERLAP。如果 树T中没有重叠，则区间[y1,y2]为 插入到树中。

2. 如果当前 x 坐标是矩形 R 的右边缘，则 它的 y 区间 [y1, y2] 从区间树 T 中移除。

3. 如果排序列表 S 被完全处理，则没有重叠。算法停止并报告 NO-OVERLAP。

N个矩形的时间复杂度是O(N*log(N)) 因为对于每个 2*N x 坐标在区间树中搜索 N 个区间。 辅助数据结构S和T的空间复杂度为O(N)。