1

给定网格内的一组随机点，如何有效地检查它们是否都位于其他点的固定范围内。即：选择任何一个随机点，然后您可以导航到网格中的任何其他点。

进一步澄清：如果您有一个 1000 x 1000 的网格并在其中随机放置 100 个点，您如何证明任何一个点都在邻居的 100 个单位内，并且所有点都可以通过从一个点走到另一个点来访问？

我一直在编写一些代码并提出了一个有趣的问题：非常偶尔（到目前为止只有一次）它会创建一个超出其余点最大范围的点岛。我需要解决这个问题，但蛮力似乎不是答案。

它是用 Java 编写的，但我擅长使用伪代码或 C++。

4

7 回答 7

2

我喜欢@joel.neely 的构造方法，但如果你想确保更均匀的密度，这更有​​可能起作用（尽管它可能会产生更多的集群而不是整体均匀的密度）：

  1. 通过从有效网格内的均匀分布中选择 x,y 来随机放置一个初始点 P_0
  2. 对于 i = 1:N-1
    1. 选择随机 j = 从 0 到 i-1 均匀分布，识别P_j之前放置的点
    2. P_i选择distance( P_i, ) < 100 的随机点P_j，方法是重复以下步骤，直到在P_i下面的子步骤 4 中选择了一个有效点：
      1. 选择 (dx,dy) 每个从 -100 到 +100 均匀分布
      2. 如果 dx^2+dy^2 > 100^2，距离太大（21.5%的时间失败），返回上一步。
      3. 计算候选坐标( P_i) = coords( P_j) + (dx,dy)。
      4. P_i如果它在整个有效网格内，则它是有效的。
于 2008-12-30T14:03:06.540 回答
1

如果我正确理解您的问题，给定一组站点，您想测试每个站点的最近邻居（对于 L1 距离，即网格距离）的距离是否小于 K 值。

这很容易通过计算点集的 Delaunay 三角剖分获得欧几里得距离：站点的最近邻居是其在 Delaunay 三角剖分中的邻居之一。有趣的是，L1 距离大于欧几里得距离（在一个因子 sqrt(2) 内）。

因此，测试您的状况的方法如下：

  1. 计算站点的 Delaunay 三角剖分
  2. 对于每个站点 s，在三角剖分中从 s 开始广度优先搜索，以便您发现到 s 的欧几里得距离小于 K 的所有顶点（Delaunay 三角剖分具有距离小于 K 的顶点集的性质）给定站点在三角剖分中连接）
  3. 对于每个站点 s，在距离 s 小于 K 的这些顶点中，检查它们中的任何一个是否在距离 s 小于 K 的 L1 距离处。如果不是，则该属性不满意。

该算法可以通过以下几种方式进行改进：

  1. 一旦发现 L1 距离小于 K 的站点，当然应该停止第 2 步的广度优先搜索。
  2. 在寻找 s 的有效邻居期间，如果发现站点 s' 与 s 的 L1 距离小于 K，则无需为 s' 寻找有效邻居：s 显然是其中之一。
  3. 不需要完整的广度优先搜索：在访问了所有与 s 相关的三角形后，如果三角剖分中 s 的邻居都不是有效邻居（即 L1 距离小于 K 的站点），则表示为 (v 1 , ...,v n ) 邻居。最多有四个与水平轴和垂直轴相交的边（ vi，vi +1 ）。只能通过这四个（或更少）边继续搜索。[这来自于 L1 球体的形状]
于 2009-01-03T23:38:40.327 回答
1

就评估现有的点集而言，这看起来像是一种欧几里得最小生成树问题。维基百科页面指出这是Delaunay 三角剖分的子图；所以我认为计算 Delaunay 三角剖分就足够了（参见上一页参考资料或谷歌“计算几何”），然后计算最小生成树并验证所有边的长度是否小于 100。

从阅读参考资料看来，这是 O(N log N)，也许有更快的方法，但这已经足够了。

一个更简单（但可能效率较低）的算法如下所示：

  1. 给定：这些点位于从索引 0 到 N-1 的数组中。
  2. 以 x 坐标顺序对点进行排序，即 O(N log N) 以进行有效排序。
  3. 初始化 i = 0。
  4. 增量 i。如果 i == N，则停止成功。（所有点都可以从另一个半径 R 到达）
  5. 初始化 j = i。
  6. 递减 j。
  7. 如果j<0或P[i].x - P[j].x > R，则以失败告终。（存在间隙，半径为 R 的所有点无法相互到达）
  8. 否则，如果 P[i].x 和 P[j].x 在彼此的 R 范围内，我们就会到达这里。检查点 P[j] 是否足够接近 P[i]：如果(P[i].x-P[j].x)^2 + (P[i].y-P[j].y)^2 <R^2`，则点 P[i] 可以通过半径 R 内的先前点之一到达，然后返回步骤 4。
  9. 继续尝试：返回第 6 步。

编辑：这可以修改为应该是 O(N log N) 但我不确定：

  1. 给定：这些点位于从索引 0 到 N-1 的数组中。
  2. 以 x 坐标顺序对点进行排序，即 O(N log N) 以进行有效排序。
  3. 维护一个按 y 坐标顺序排列的点集 YLIST，将 YLIST 初始化为集合 {P[0]}。我们将从左到右扫描 x 坐标，将点一个接一个地添加到 YLIST 并删除 x 坐标离新添加的点太远的点。
  4. 初始化 i = 0，j = 0。
  5. 在这一点上，循环不变式始终为真：k <= i 的所有点 P[k] 形成一个网络，它们可以通过半径 R 从彼此到达。YLIST 中的所有点都有位于 P[i] 之间的 x 坐标。 xR 和 P[i].x
  6. 增量 i。如果 i == N，则停止成功。
  7. 如果 P[i].xP[j].x <= R，则转到第 10 步。（如果 i == j，则自动为真）
  8. 点 P[j] 无法从半径为 R 的点 P[i] 到达。从 YLIST 中移除 P[j]（这是 O(log N)）。
  9. 增加 j，进行第 6 步。
  10. 此时，j<iP[i].xR 和 P[i].x 之间的所有点 P[j] 和 x 坐标都在集合 YLIST 中。
  11. 将 P[i] 添加到 YLIST（这是 O(log N)），并记住 YLIST 中的索引 k，其中 YLIST[k]==P[i]。
  12. 点 YLIST[k-1] 和 YLIST[k+1]（如果它们存在；P[i] 可能是 YLIST 中的唯一元素，也可能位于极端）是 YLIST 中离 P[i] 最接近的点.
  13. 如果点 YLIST[k-1] 存在并且在 P[i] 的半径 R 内，则 P[i] 可以从至少一个先前点以半径 R 到达。转到第 5 步。
  14. 如果点 YLIST[k+1] 存在并且在 P[i] 的半径 R 内，则 P[i] 可以从至少一个先前点以半径 R 到达。转到第 5 步。
  15. P[i] 不能从前面的任何点到达。以失败告终。
于 2008-12-30T14:37:15.847 回答
1

新的和改进的 ;-)

感谢 Guillaume 和 Jason S 的评论让我思考更多。这产生了第二个提案，其统计数据显示出显着改善。

Guillaume 说我之前发布的策略会失去均匀的密度。当然，他是对的，因为它本质上是一种倾向于绕原点运行的“醉汉行走”。然而，点的均匀随机放置产生了不符合“路径”要求的显着概率（所有点都可以通过不大于 100 步长的路径连接）。测试这种情况很昂贵；生成纯随机解决方案直到通过一次更是如此。

Jason S 提供了一个变体，但对大量模拟的统计测试使我得出结论，他的变体产生的模式与我的第一个提案中的模式一样聚集（基于检查坐标值的平均值和标准偏差）。

下面修改后的算法产生的点集的统计数据与纯（均匀）随机放置的统计数据非常相似，但通过构造保证满足路径要求。不幸的是，形象化比口头解释要容易一些。实际上，它要求点在一个模糊一致的方向（NE、SE、SW、NW）上随机交错，只有在“从墙上反弹”时才会改变方向。

这是高级概述：

  1. 随机选择一个初始点，将水平行程设置为 RIGHT，垂直行程设置为 DOWN。

  2. 对剩余的点数重复（例如原始规范中的 99）：

    2.1。随机选择距离在 50 到 100 之间的 dx 和 dy。（我假设欧几里得距离——平方和的平方根——在我的试验实现中，但“出租车”距离——绝对值之和——会更容易编码。）

    2.2. 根据水平和垂直行程（右/下 -> 加，左/上 -> 减）将 dx 和 dy 应用于前一点。

    2.3. 如果任一坐标超出范围（小于 0 或至少 1000），则在违反的边界周围反射该坐标，并将其行进替换为相反方向。这意味着四种情况（2 个坐标 x 2 个边界）：

    2.3.1. if x < 0, then x = -x and reverse LEFT/RIGHT horizontal travel.
2.3.2. if 1000 <= x, then x = 1999 - x and reverse LEFT/RIGHT horizontal travel.
2.3.3. if y < 0, then y = -y and reverse UP/DOWN vertical travel.
2.3.4. if 1000 <= y, then y = 1999 - y and reverse UP/DOWN vertical travel.

请注意，步骤 2.3 下的反射保证将新点留在前一点的 100 个单位内，因此保留了路径要求。然而，水平和垂直旅行的限制迫使点的生成随机地“扫过”整个空间，比原来的纯“酒鬼走路”算法产生更多的总分散。

于 2009-01-02T13:56:29.660 回答
1

快速思考一下：如果您将网格划分为 50x50 的补丁，当您放置初始点时，您还会记录它们属于哪个补丁。现在，当您想检查一个新点是否在其他点的 100 像素内时，您可以简单地检查补丁加上它周围的 8 点，看看点数是否匹配。

例如，你知道你有 100 个随机点，每个补丁包含它们包含的点数，你可以简单地总结一下，看看它是否确实是 100——这意味着所有点都可以到达。

我敢肯定还有其他方法，很难。

编辑：从左上点到 50x50 补丁右下角的距离是 sqrt(50^2 + 50^2) = 70 点，所以你可能不得不选择更小的补丁大小。也许 35 或 36 会做 (50^2 = sqrt(x^2 + x^2) => x=35.355...)。

于 2008-12-30T13:12:30.387 回答
1

找到点集的凸包，然后使用旋转卡尺法。凸包上最远的两个点是集合中最远的两个点。由于所有其他点都包含在凸包中，因此可以保证它们比两个极值点更近。

于 2008-12-30T13:41:22.450 回答
0

通过构造强制所需条件。不要仅通过绘制随机数来放置所有点，而是按如下方式约束坐标：

  1. 随机放置一个初始点。

  2. 对剩余的点数重复（例如 99）：

    2.1。在前一点的某个范围（例如 90）内随机选择一个 x 坐标。

    2.2. 计算 y 坐标的合法范围，使其在前一点的 100 个单位内。

    2.3. 在该范围内随机选择一个 y 坐标。

  3. 如果您想完全模糊原点，请按坐标对对点进行排序。

与纯随机性相比，这不需要太多开销，但会保证每个点与至少一个其他点的距离在 100 个单位以内（实际上，除了第一个和最后一个点，每个点都在其他两个点的 100 个单位以内）。

作为上述的变体，在步骤 2 中，随机选择任何已经生成的点并将其用作参考，而不是之前的点。

于 2008-12-30T13:44:49.307 回答