最佳固定矩形区域覆盖点

Question

3

我正在使用Google地图，试图找出在给定缩放级别下视口中可见的最大点数。

我的天真做法是获取视区（在坐标系中）并将其作为“拟合矩形”，看看有多少点适合该区域。我查看了一下，但是我找不到用于在矩形区域内“最佳适合”随机点的算法。

这似乎是一个相当常见的问题，因此我可能不知道正确的关键字。

如果能帮助我找到解决方案，将不胜感激。

编辑：感谢回答，但恐怕我没有说清楚。覆盖所有点的矩形适应度几乎是微不足道的（对它们进行排序，获取最小/最大值即可）。我想知道的是可以适合固定大小矩形下的最大点数：我已经得到了所有点和固定大小的“移动窗口”，我想知道我能够容纳多少个点。很抱歉初始说明不好。

干杯。

- R4cOOn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cdeszaq · Accepted Answer

要在一组点中找到最适合的矩形，并假定集合中的所有点都需要在矩形内，您只需要在两个维度上找到最小/最大值即可。

其中一种方法是按其X维度对点进行排序，并将第一个和最后一个作为该维度中的最小/最大值，然后在Y维度上重复此过程以获得该最小/最大值。从那些信息中，您就有了制作矩形所需的所有内容。

从计算复杂性的角度来看，复杂性是所使用的排序算法的复杂性的2倍（因为你必须排序2次）+获取每个排序集的第一个和最后一个元素的复杂性，如果您例如使用一个数组，这是一个O(1)操作。

如果您使用归并排序，并将其分类到数组中，则总体复杂度为O(n log n)。分解成操作数量，您有2(n log n)+4。

这不会给您提供最紧密的拟合矩形，因为它不会确保矩形的一侧与至少2个点共线（为此，您需要Roating Calipers算法，@Bart Kiers建议），但这是一个更快的算法，因为旋转卡尺本质上执行的就是我在这里描述的操作，但然后旋转矩形，直到其边缘之一与2个最小/最大点对齐。