我需要一个算法，它可以接收一个未排序的轴对齐矩形数组，并返回任何重叠的矩形对。
每个矩形都有两个变量，即左上角和右下角的坐标。
每个矩形都有两个变量，即左上角和右下角的坐标。
3个回答
17
这是在DuduAlul的链接中介绍的交叉算法的简要描述。
该解决方案需要使用能够执行范围查询的搜索树。范围查询请求所有值在K1和K2之间的项目，并且它应该是O(R + log N)操作，其中N是树项的总数，而R是结果数。
该算法使用扫描方法：
1）按照其X值将所有左右矩形边缘排序为列表L。
2）为矩形顶部/底部的Y排序创建新的空范围搜索树T。
3）创建新的唯一矩形对结果集RS的空集合。
4）按升序遍历L。对于L中的所有V：
如果V.isRightEdge()
时间复杂度为O(R + N log N)，其中R是实际交点数。
--编辑--
我刚才发现解决方案并不完全正确——树T中的交点测试会漏掉一些情况。该树应该维护Y间隔而不是Y值，并且最好是一个Interval Tree。
该解决方案需要使用能够执行范围查询的搜索树。范围查询请求所有值在K1和K2之间的项目，并且它应该是O(R + log N)操作，其中N是树项的总数，而R是结果数。
该算法使用扫描方法：
1）按照其X值将所有左右矩形边缘排序为列表L。
2）为矩形顶部/底部的Y排序创建新的空范围搜索树T。
3）创建新的唯一矩形对结果集RS的空集合。
4）按升序遍历L。对于L中的所有V：
如果V.isRightEdge()
T.remove(V.rectangle.top)
T.remove(V.rectangle.bottom)
否则
对于所有在T中范围为V.rectangle.top到V.rectangle.bottom的U
将 <V.rectangle, U.rectangle> 添加到RS中
T.add(V.rectangle.top)
T.add(V.rectangle.bottom)
5) 返回 RS
时间复杂度为O(R + N log N)，其中R是实际交点数。
--编辑--
我刚才发现解决方案并不完全正确——树T中的交点测试会漏掉一些情况。该树应该维护Y间隔而不是Y值，并且最好是一个Interval Tree。
- Eyal Schneider
1
这是一个好答案。我也在csail.mit.edu的课程手册《Hacking a Google Interview》中找到了它。 - Mingliang Liu
12
这可能对于面试来说有点复杂，取决于职位类型， 它是一种几何计算类的算法。
答案可以在这里找到： http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
- DuduAlul
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接