6

注意：问题底部有一个重大编辑 - 看看

问题

假设我有一组要点：

积分

我想找到它周围点最多的点，在半径内R（即圆形）或在+-R二维点的半径内（即正方形）。我将其称为最密集点函数。

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

我试过的

解决此问题的一种可行方法是使用范围搜索解决方案；这个答案进一步解释了它有“O(log(n) + k)最坏情况时间”。使用它，我可以获得每个点周围的点数，并选择周围点数最多的点。

但是，如果这些点非常密集（大约一百万），那么：

在此处输入图像描述

那么这百万个点（1e6）中的每一个都需要执行范围搜索。对于以下点树类型，最坏情况时间O(log(n) + k)（其中ķ是范围内返回的点数）为真：

  • 二维的 kd-trees（实际上稍微差一点，在 处O(sqrt(n)+k)），
  • 二维范围的树，
  • 四叉树，最坏情况时间为在）

因此，对于组内所有点的1e6半径R内的一组点，它给出O(log(1e6) + 1e6)了每个点的复杂度。这产生了超过一万亿次操作！

关于实现这一目标的更有效、更精确的方法的任何想法，以便我可以在合理的时间内（最好O(n log(n))或更少）找到一组点周围点最多的点？

编辑

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

(半)解决方案

如果我使用二维范围树：

  • 一个范围报告查询成本O(log^d(n) + k)，对于ķ返回的点，
  • 对于具有分数级联的范围树（也称为分层范围树），复杂度为O(log^(d-1)(n) + k)，
  • 对于 2 维，即O(log(n) + k)，
  • 此外，如果我执行范围计数查询（即，我不报告每个点），那么它的成本为O(log(n)).

我会在每一点上执行这个 - 产生O(n log(n))我想要的复杂性！

问题

但是，我无法弄清楚如何为二维分层范围树的计数查询编写代码。

我找到了关于范围树的一个很好的资源（从第 113 页开始），包括二维范围树伪代码。但是我不知道如何引入分数级联，也不知道如何正确实现计数查询，因此它很O(log n)复杂。

我还在这里和这里在 Java 中找到了两个范围树实现，在 C++ 中找到了一个，尽管我不确定这是否使用分数级联，因为它在countInRange方法上方指出

它返回最坏情况下此类点的数量 * O(log(n)^d) 时间。它还可以在最坏的情况下返回矩形中的点 * O(log(n)^d + k) 时间，其中 k 是矩形中的点数。

这对我来说表明它不应用分数级联。

提炼的问题

因此，要回答上述问题，我只需要知道是否有任何具有分数级联的二维范围树的库具有复杂的范围计数查询，O(log(n))所以我不去重新发明任何轮子，或者你能帮我吗？编写/修改上述资源以执行该复杂性的查询？

如果您可以为我提供任何其他方法以任何其他方式实现二维点的范围计数查询，也不要抱怨O(log(n))！

4

3 回答 3

2

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

  1. 按 Y 坐标将点排序到数组 S。
  2. 向数组 S 前进 3 个指针：一个 (C) 表示当前检查的（中心）点；另一个，A（稍前一点）表示距离 > R 低于 C 的最近点；最后一个，B（稍微落后一点）表示距离 < R 上方的最远点。
  3. 将 A 指向的点插入到Order 统计树（按坐标 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. 使用上一步的结果选择“最包围”点。

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

于 2017-06-08T13:27:29.420 回答
1

我会首先创建一个类似https://en.wikipedia.org/wiki/K-d_tree的东西，在其中你有一棵树，叶子上有点，每个节点都有关于其后代的信息。在每个节点上，我都会计算后代的数量，以及一个包围这些后代的边界框。

现在对于每个点，我都会递归地搜索树。在我访问的每个节点上，要么所有边界框都在当前点的 R 内，要么所有边界框距离当前点超过 R，或者其中一些在 R 内，一些在 R 外。在第一个案例我可以使用当前节点的后代数量的计数来增加当前点的R内的点数并返回上一级递归。在第二种情况下，我可以简单地返回一级递归而不增加任何内容。只有在中间情况下，我才需要继续沿树递归。

因此，我可以为每个点计算 R 内的邻居数，而无需检查每个其他点，然后选择计数最高的点。

如果这些点分布均匀，那么我认为您最终会构建一个 kd 树，其中较低级别接近于常规网格，并且我认为如果网格的大小为 A x A，那么在最坏的情况下 R 足够大所以它的边界是一个与 O(A) 低级单元相交的圆，所以我认为如果你有 O(n) 个点，你可以预计这会花费大约 O(n * sqrt(n))。

于 2017-06-04T05:59:56.023 回答
0

O(n)您可以通过及时预处理数据来估计相邻点的数量来加速您使用的任何算法。

对于半径为R的圆，创建一个网格，其单元格在 x 和 y 方向上都有维度R。对于每个点，确定它属于哪个单元格。对于给定的单元格c，此测试很简单：

c.x<=p.x && p.x<=c.x+R && c.y<=p.y && p.y<=c.y+R

（您可能需要深入思考闭区间或半开区间是否正确。）

如果您有相对密集/均匀的覆盖范围，那么您可以使用数组来存储值。如果覆盖范围是稀疏/异构的，您可能希望使用哈希图。

现在，考虑网格上的一个点。单元格内点的极值位置如下所示：

半径 R 的网格

单元格角落的点只能与四个单元格中的点相邻。沿边的点可以与六个单元格中的点相邻。不在边缘上的点与 7-9 个单元格中的点相邻。由于很少有一个点恰好落在角落或边缘上，我们假设焦点单元格中的任何点都与所有 8 个周围单元格中的点相邻。

因此，如果点p在单元格(x,y)中，N[p]则标识p半径R内的邻居数，并表示单元格(x,y)Np[y][x]中的点数，则由下式给出：N[p]

N[p] = Np[y][x]+
       Np[y][x-1]+
       Np[y-1][x-1]+
       Np[y-1][x]+
       Np[y-1][x+1]+
       Np[y][x+1]+
       Np[y+1][x+1]+
       Np[y+1][x]+
       Np[y+1][x-1]

一旦我们为每个点估计了邻居的数量，我们就可以及时将该数据结构堆化为一个 maxheap O(n)（例如make_heap）。该结构现在是一个优先级队列，我们​​可以在每个查询的O(log n)时间内按其估计的邻居数量排序。

对第一个点执行此操作，并使用O(log n + k)循环搜索（或一些更聪明的算法）来确定该点的实际邻居数。记下变量中的这一点best_found并更新其N[p]值。

查看堆的顶部。如果估计的邻居数量少于N[best_found]那么我们就完成了。否则，重复上述操作。

为了改进估计，您可以使用更精细的网格，如下所示：

半径 R/2 的网格

以及一些巧妙的滑动窗口技术以减少所需的处理量（例如，参见矩形情况的答案- 对于圆形窗口，您可能应该使用 FIFO 队列的集合）。为了提高安全性，您可以随机化网格的原点。

再次考虑您提出的示例：

网格覆盖的棘手邻居计数示例

很明显，这种启发式方法有可能节省大量时间：使用上述网格，只需执行一次昂贵的检查即可证明中间点具有最多的邻居。同样，更高分辨率的网格将改进估计并减少需要进行的昂贵检查的数量。

您可以并且应该结合mcdowella 的答案使用类似的边界技术；但是，他的回答并没有提供一个开始寻找的好地方，因此可能会花费大量时间来探索低价值点。

于 2017-06-05T19:19:54.323 回答