轴对齐的矩形交叉点

Question

我需要一种算法,它采用未排序的轴对齐矩形阵列,并返回重叠的任何一对矩形

每个矩形都有两个变量,左上角和右下角的坐标

Answer 1

以下是DuduAlul链接中交叉算法的简要说明.

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

该算法使用扫描方法:

1)将所有左右矩形边缘根据其X值排序到列表L中.

2)创建一个新的空范围搜索树T,用于矩形顶部/底部的Y排序

3)创建唯一矩形对的新空结果集RS

4)按升序遍历L. 对于L中的所有V:

   如果是V.isRightEdge()

      T.remove(V.rectangle.top)

      T.remove(V.rectangle.bottom)

   其他

       对于T.getRange中的所有U(V.rectangle.top,V.rectangle.bottom)

         RS.add(<V.rectangle,U.rectangle>)

      T.add(V.rectangle.top)

      T.add(V.rectangle.bottom)

5)返回RS

时间复杂度为O(R + N log N),其中R是实际的交叉点数.

- 编辑 -

我只是想通了解决方案并不完全正确 - 树T中的交叉点测试错过了一些情况.树应保持Y间隔而不是Y值,理想情况下应该是间隔树.

Answer 2

对于求职面试来说可能有点复杂,取决于什么样的工作,这是一种几何计算类算法,

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