轴对齐矩形相交

Question

我需要一个算法，需要轴对准的矩形的一个未排序的阵列和 返回任何一对矩形的重叠

每个矩形具有两个变量中，左上角的坐标和在右下角

Answer 1

这可能是有点复杂的面试，要看是什么样的工作， 这是一个几何计算一种算法，

答案可以在这里找到： http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf

Answer 2

下面是在DuduAlul的链接中提出的交集算法的简要说明。

该解决方案需要使用能够执行范围查询的搜索树。范围查询要求K1和K2之间的值的所有项目，并且它应该是O（R + log N）操作，其中N是树项目的总数，R是结果的数目。

该算法采用扫描方式：

1）排序的所有左，右边缘的矩形，根据自己的X值，到列表L.

2）创建一个新的空范围搜索树T，为矩形的顶部Y的排序/塔底

3）创建独特的矩形对

4）导线L的升序的一个新的空的结果集RS。为以L所有的V：

     如果V.isRightEdge（）

            T.remove（V.rectangle.top）

           Ť .remove（V.rectangle.bottom）

     其他

           对于所有u在T.getRange（V.rectangle.top，V.rectangle.bottom）

                  RS.add （< V.rectangle，U.rectangle>）

            T.add（V.rectangle。顶部）

            T.add（V.rectangle.bottom）

5）返回RS

---

的时间复杂度是O（R + N日志N），其中R是交叉点的实际数量。

- 编辑 -

我想通了，解决的办法是不完全正确 - 在树T的相交测试错过某些情况下。树应保持Y间隔而不是Y值，理想情况下应该是Interval Tree。

Answer 3

Sweep and prune是很多物理引擎解决这类问题的方法。

David Baraff's SIGGRAPH notes有一个很好的解释，在7.2节边界框下。