Math/Algorithm/JS:给定每个矩形的TopLeft(x0,y0)和Bottom-Right(x1,y1),如何确定2个以上的矩形是否相交

Question

我遇到了完成我的申请所需的数学问题,所以我正在寻求帮助.

给出2个(或更多,但基本上为2个)矩形,每个矩形有2个已知点:左上角(x1,y1)和右下角(x2,y2)(我可以找到这些信息的长度,如果是需要解决问题).

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

无论如何确定它们是否有交叉,在区域中,我的意思是,如果这个矩形的任何部分放在另一个的任何部分上？

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

有两种情况,两个矩形不会相交:

• 一个矩形的左边缘位于另一个矩形的右边缘的右侧,意味着第一个矩形的左边缘完全位于第二个矩形的右侧,没有交叉点.

• 一个矩形的右边缘位于另一个矩形的左边缘的左侧,意味着第一个矩形的右边缘完全位于第二个矩形的左侧,没有交叉点.

• 一个矩形的顶部边缘位于另一个矩形的底部边缘下方,意味着第一个矩形完全位于第二个矩形的下方,没有交叉点.

• 一个矩形的下边缘位于另一个矩形的上边缘上方,意味着第一个矩形完全位于第二个上方,没有交叉点.

所以我试图扭转条件,即如果没有发生上述4,则矩形可能会相交.但我仍然可以找到2个矩形不满足任何条件但仍然不相交的条件(如上图).

任何帮助都非常感谢,请告诉我这样做的方法或算法或代码(仅限JS和PHP).

非常感谢!

[X]

Answer 1

用于任何数量的矩形的交叉检测("重叠")的算法可以如下工作.使用两种数据结构.

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

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

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

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

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

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