php - 数学/算法/JS : How to determine if 2+ rectangles intersect, 给定每个矩形的 TopLeft(x0, y0) 和 Bottom-Right(x1, y1)

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

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

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

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

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



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

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

非常感谢!

[X]

最佳答案

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

矩形左右边缘 x 坐标的排序列表 S。

由矩形的 y 坐标(底部/顶部)给出的间隔的 interval tree T。

该算法扫描 x 坐标的排序列表 S:

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

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

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

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

关于php - 数学/算法/JS : How to determine if 2+ rectangles intersect, 给定每个矩形的 TopLeft(x0, y0) 和 Bottom-Right(x1, y1)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7990285/