数学/算法/ JS：如何确定是否2+矩形相交，给出的左上（X0，Y0），并且每个矩形的右下角（X1，Y1） [英] Math/ Algorithm/ JS: How to determine if 2+ rectangles intersect, given the TopLeft(x0, y0) and Bottom-Right(x1, y1) of each rectangle

问题描述

我遇到这是需要完成我的应用程序这道数学题，所以我寻求帮助。

I come across this math problem which is needed to complete my application, so I'm asking for help.

由于2（或更多，但基本上2）矩形带2个已知点，每个 最常见左（X1，Y1）的和的底右（X2，Y2）的（Ⅰ可以找到与这些信息的长度，如果是一个需要解决的问题）。

Given 2 (or more, but basically for 2) rectangles with 2 known points for each: Top-left(x1, y1) and Bottom-right(x2, y2) (I can find the length with these info, if it is a need to solve the problem).

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

反正是有，以确定他们是否有交集，在面积，我的意思是，如果有一部分这个矩形的规定的任何部分的另外一个？

Is there anyway to determine if they have intersection, in area, I mean, if any part of this rectangle lays on any part of another one?

我已经搜查，发现了一个小的帮助，但它并没有解决问题：

I've searched and found out a little help, but it does not solve the problem:

有4个条件，其中两个矩形不会相交：

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

  

• 1矩形的左边缘的右边的另一个右边缘的，是指第一个完全在右侧中的第二个规定，没有交集。

• 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.

1矩形的右边缘上的另一个的左边缘的左侧，表示第一个被完全上的第二个左侧敷设，没有交集。

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.

1矩形的顶边是中的另一个的底部边缘下，意味着第一个是根据第二个完全敷设，没有交集。

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.

1矩形的底部边缘中的另一个的顶边缘之上，这意味着第一个是完全高于第二个规定，没有交集。

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矩形不符合任何条件，仍然不相交。

So I tried to reverse the conditions, which is if 4 of the above does not occur, the rectangles may intersect. But I still can find the condition (such as the picture above) in which 2 rectangles do not fulfill any condition, and still does not intersect.

任何帮助是非常AP preciated，请告诉我这样做或算法或code的方式（JS和PHP只请）。

Any help is highly appreciated, please show me the way to do it or algorithm or code (JS and PHP only please).

非常感谢！

[X]

推荐答案

这是算法的交叉点检测的任何数量的（重叠） 矩形可以工作如下。两个数据结构被使用。

An algorithm for the intersection detection ("overlapping") of any number of rectangles could work as follows. Two data structures are used.

• 矩形的左，右边缘的x坐标的排序表S。
• 通过矩形的y坐标（底/顶部）给出的区间T时的间隔树。

• A sorted list S of the x-coordinates of the left and right edges of the rectangles.
• An interval tree T of the intervals given by the y-coordinates (bottom/top) of the rectangles.

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

The algorithm sweeps over the sorted list S of the x-coordinates:

1. 如果当前的x坐标是一个矩形R的左边缘，然后 的y坐标的R [Y1，Y2]的相比，间隔树T. 如果发现有重叠，则算法停止，并报告重叠。如果 没有重叠在树T，则在区间[Y1，Y2]的 插入树。

1. If the current x-coordinate is the left edge of a rectangle R then the y-coordinates [y1, y2] of R are compared to the interval tree T. If an overlap is found, then the algorithm stops and reports OVERLAP. If there was no overlap in the tree T, then the interval [y1, y2] is inserted into the tree.

如果当前的x坐标是一个矩形R的右边缘，然后 其Y间隔[Y1，Y2]从区间树T中删除。

If the current x-coordinate is the right edge of a rectangle R then its y-interval [y1, y2] is removed from the interval tree T.

如果排序列表S被处理完毕，再有就是没有重叠。该算法停止和报告不重叠。

If the sorted list S is completely processed, then there was no overlap. The algorithm stops and reports NO-OVERLAP.

对于N矩形的时间复杂度为O（N *日志（N）） 因为对于每个2 * N 的x坐标中的时间间隔为树N个间隔执行搜索。 空间复杂度为O（N）为辅助数据结构S和T

The time complexity for N rectangles is O(N*log(N)) because for each 2*N x-coordinates a search in the interval tree for N intervals is performed. The space complexity is O(N) for the auxiliary data structures S and T.

这篇关于数学/算法/ JS：如何确定是否2+矩形相交，给出的左上（X0，Y0），并且每个矩形的右下角（X1，Y1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！