我正在使用Google地图,试图找出在给定缩放级别下视口中可见的最大点数。
我的天真做法是获取视区(在坐标系中)并将其作为“拟合矩形”,看看有多少点适合该区域。 我查看了一下,但是我找不到用于在矩形区域内“最佳适合”随机点的算法。
这似乎是一个相当常见的问题,因此我可能不知道正确的关键字。
如果能帮助我找到解决方案,将不胜感激。
编辑:感谢回答,但恐怕我没有说清楚。覆盖所有点的矩形适应度几乎是微不足道的(对它们进行排序,获取最小/最大值即可)。 我想知道的是可以适合固定大小矩形下的最大点数:我已经得到了所有点和固定大小的“移动窗口”,我想知道我能够容纳多少个点。 很抱歉初始说明不好。
干杯。
我的天真做法是获取视区(在坐标系中)并将其作为“拟合矩形”,看看有多少点适合该区域。 我查看了一下,但是我找不到用于在矩形区域内“最佳适合”随机点的算法。
这似乎是一个相当常见的问题,因此我可能不知道正确的关键字。
如果能帮助我找到解决方案,将不胜感激。
编辑:感谢回答,但恐怕我没有说清楚。覆盖所有点的矩形适应度几乎是微不足道的(对它们进行排序,获取最小/最大值即可)。 我想知道的是可以适合固定大小矩形下的最大点数:我已经得到了所有点和固定大小的“移动窗口”,我想知道我能够容纳多少个点。 很抱歉初始说明不好。
干杯。
O(n)
中找到最小的边界矩形,但它需要一个凸壳而不是一组点。因此,给定一组点,总运行时间仍将为O(n*log(n))
。 - Bart KiersO(n*log(n))
:http://en.wikipedia.org/wiki/Convex_hull_algorithms - Bart Kiers