选择具有最多周围点的点的最有效方法

Question

注意:问题的底部有一个重要的编辑 - 检查出来

题

说我有一套要点:

我希望在半径范围内找到围绕它的点数最多的点 (即圆圈)或内部 (即正方形)2维的点.我将它称为最密集的函数.

对于这个问题中的图表,我将周围的区域表示为圆圈.在上图中,中间点的周围区域以绿色显示.该中间点具有半径内所有点的最多周围点 并且将由最密集的点函数返回.

我试过的

解决这个问题的可行方法是使用范围搜索解决方案; 这个答案进一步解释,它有" 最坏的情况使用这个,我可以获得每个点周围的点数,并选择具有最大周围点数的点.

但是,如果积分非常密集(大约一百万),那么:

那么每一百万点()需要进行范围搜索.最坏的情况,哪里 是范围内返回的点数,对于以下点树类型是正确的:

• 二维的kd树(实际上稍微差一点,在 )
• 2d范围的树木,
• 四叉树,最糟糕的时间

所以,对于一组人来说 半径范围内的点 在该组中的所有点,它给出了复杂性 对于每一点.这产生了超过一万亿次的运营!

有关实现这一目标的更有效,更精确的方法的任何想法,以便我能够在合理的时间内找到具有最多周围点的点,并且在合理的时间内(最好 或更少)？

编辑

原来上面的方法是正确的!我只需要帮助实现它.

(半)解决方案

如果我使用2d范围树:

• 范围报告查询成本 ,为 返回点,
• 对于具有分数级联(也称为分层范围树)的范围树,复杂性是 ,
• 对于2维,即 ,
• 此外,如果我执行范围计数查询(即,我不报告每个点),那么它的成本 .

我会在每一点上执行此操作 - 产生 复杂我想要的!

问题

但是,我无法弄清楚如何为2d分层范围树的计数查询编写代码.

我找到了一个关于范围树的很好的资源(从第113页开始),包括2d-range树的伪代码.但我无法弄清楚如何引入分数级联,也不知道如何正确实现计数查询以使其具有O(log n)复杂性.

我还发现了两个范围树的实现在这里和这里在Java中,一个在C++ 在这里,虽然我不知道该用分数作为级联它指出上述countInRange方法

它在最坏的情况下返回这些点的数量*O(log(n)^ d)时间.它还可以返回矩形中的点,在最坏的情况下*O(log(n)^ d + k)时间,其中k是位于矩形中的点的数量.

这告诉我它不适用分数级联.

精致的问题

因此,为了回答上面的问题,我需要知道的是,是否存在具有分数级联的二维范围树的任何库,其具有范围计数查询的复杂性 所以我不会重新发明任何轮子,或者你能帮助我编写/修改上面的资源来执行这种复杂性的查询吗？

如果你能提供任何其他方法来实现2d点的范围计数查询,也不要抱怨 以任何其他方式!

Answer 1

我建议使用平面扫描算法。这允许一维范围查询而不是二维查询。（哪个更有效，更简单，并且在正方形邻域的情况下不需要分数级联）：

1. 按 Y 坐标将点排序到数组 S。
2. 向数组 S 前进 3 个指针：其中一个 (C) 表示当前检查的（中心）点；另一个，A（稍前一点）表示 C 下方距离 > R 的最近点；最后一个，B（稍微落后一点）表示其上方距离 < R 的最远点。
3. 将 A 指向的点插入到排序统计树（按坐标 X 排序），并从该树中删除 B 指向的点。使用该树查找距 C 左/右距离为 R 的点，并使用这些点在树中的位置差来获取 C 周围正方形区域中的点数。
4. 使用上一步的结果选择“最包围”点。

如果旋转点（或仅交换 XY 坐标）以使占用区域的宽度不大于其高度，则可以优化该算法。此外，您还可以将点切割成垂直切片（具有 R 大小的重叠）并单独处理切片 - 如果树中的元素太多，以至于它不适合 CPU 缓存（对于只有 100 万个点来说这是不可能的）。该算法（优化与否）的时间复杂度为 O(n log n)。

对于圆形邻域（如果 R 不太大并且点分布均匀），您可以用几个矩形来近似圆：

在这种情况下，算法的第 2 步应该使用更多的指针来允许在多个树中插入/删除。在步骤 3 中，您应该在适当距离 (<=R) 的点附近进行线性搜索，以区分圆内的点和圆外的点。

处理圆形邻域的其他方法是用等高的矩形来近似圆（但这里圆应该分成更多块）。这导致算法更加简单（其中使用排序数组而不是顺序统计树）：

1. 将点所占据的区域切成水平切片，将切片按 Y 排序，然后将切片内的点按 X 排序。
2. 对于每个切片中的每个点，假设它是“中心”点并执行步骤 3。
3. 对于每个附近的切片，使用二分搜索来查找欧几里德距离接近 R 的点，然后使用线性搜索来区分“内部”点和“外部”点。当切片完全在圆内时停止线性搜索，并通过数组中位置的差异来计算剩余的点。
4. 使用上一步的结果选择“最包围”点。

该算法允许前面提到的优化以及分数级联。