输入:
- 一组矩形(也有重叠的矩形)和一组点。
- 坐标是
integer类型。 - 矩形的边平行于轴
输出:
给定的任何矩形内的所有点
我应该使用什么高效算法和数据结构？谢谢。
最佳答案
您可以使用 sweep line algorithm :按 X 坐标对点进行排序。当矩形进入或离开扫描线(其左右边界的 X 坐标)时引入事件。当前与扫掠线相交的矩形在投影到扫掠线上时是一组间隔，因此可以使用 interval tree 来维护它们。或 segment tree (后者仅在 Y 坐标压缩之后，但您可以将其作为预处理步骤)。
使用该设置，对于每个点，您只需要检查它是否与您的数据结构维护的区间之一相交。
运行时间:O((n+m) log (n+m))
关于algorithm - 查找由一组矩形包含的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22778007/