几天来我一直在尝试为这个问题寻找算法，但没有成功:
我有 2 个列表 - 一个包含点 ((x,y) )，另一个包含矩形(每个都有两个点 - 左下角 + 右上角)。
矩形平行于轴(x轴和y轴)
我必须返回在最多矩形内的点 Θ(nlog(n)).
因此考虑到所需的运行时间..我可以按照我喜欢的方式对两个数组进行排序..但我似乎仍然没有找到在小于 Θ(n^2) 的时间内解决此问题的方法。
感谢您的提示和帮助。
最佳答案
如 LmTinyToon 所写，采用现成的 R 树实现方法，它更简单。
否则你可以使用扫描线方法:
按 X 坐标对点进行排序，按左边缘和右边缘对矩形进行排序。
用垂直线扫过
当遇到左边缘时，将事件矩形插入区间树，当遇到右边缘时，将其移除。
根据区间树检查每个点
关于algorithm - 找到出现在最多矩形中的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44716634/