5

我有两组 2D 点，它们在平面上被一条线分开。我想有效地找到一对点，​​由每组中的一个点组成，它们之间的距离最小。Radu Litiu 有一篇非常方便的论文，最近对两个分离的点集，但它使用 L1（曼哈顿）距离度量而不是欧几里得距离。

有谁知道适用于欧几里得距离的类似算法？

我几乎可以看到标准分治最近对算法的扩展——将这两个集合除以垂直于原始分割线的中线，在两侧递归，然后寻找由一个点组成的更接近的对中位数的每一边。如果与递归步骤的最小距离为 d，则中值一侧的点的伴星必须位于尺寸为 2d*d 的框内。但与原始算法不同的是，我看不到任何方法来限制该框内的点数，因此整个算法就变成了 O(m*n)。

有任何想法吗？

4

5 回答 5

2

For each point of one set find closest point in other set. While doing this, keep only one pair of points having minimal distance between them. This reduces given problem to other one: "Algorithm to find for all points in set A the nearest neighbor in set B", which could be solved using sweep line algorithm over (1) one set of points and (2) Voronoi diagram for other set.

Algorithm complexity is O((M+N) log M). And this algorithm does not use the fact that two sets of points are separated from each other by a line.

于 2013-09-04T14:22:02.377 回答
2

Evgeny 的答案有效，但如果没有库支持，需要付出很多努力：计算完整的 Voronoi 图以及额外的扫描线算法。更容易按顺序为两组点枚举其 Voronoi 单元格与分隔线相交的点，然后通过线性时间合并步骤测试其单元格相交的所有点对。

要计算所需的 Voronoi 图片段，假设 x 轴是分隔线。按 x 坐标对集合中的点进行排序，丢弃 y 大于其他 x 的点的点。开始按 x 坐标的顺序扫描点，将它们压入堆栈。在推送之间，如果堆栈至少有三个点，例如 p、q、r，其中 r 最近被推送，则测试平分 pq 的线是否与平分 qr 的线之后的分隔线相交。如果是这样，丢弃 q，并用新的前三名重复测试。粗略的 ASCII 艺术：

Case 1: retain q

------1-2-------------- separating line
     /  |
  p /   |
   \    |
    q-------r

Case 2: discard q

--2---1---------------- separating line
   \ /
  p X r
   \ /
    q
于 2013-09-04T16:48:35.210 回答
1

那么这个呢：

  1. 确定任意点在哪一侧：

    • 让 P 成为你的点 (P0,...Pi,...Pn)
    • 设 A,B 为分隔线起点
    • 所以：side(Pi) = ((BA).(Pi-A)) 的符号
    • 这是基于一个简单的事实，即标量向量乘法（点积）的符号取决于点的顺序（有关更多信息，请参见三角形/多边形缠绕规则）

  2. 找到任何 (Pi,Pj) 的最小距离，其中 side(Pi)!=side(pj)

    • 所以首先计算所有点的所有边 O(N)
    • 然后循环遍历所有 Pi 并在其中 for
    • 循环遍历所有 Pj 并搜索最小距离。
    • 如果 Pi 和 Pj 组近似。大小相等，它是 O((N/2)^2)

  3. 您可以通过与 AB 的“距离”对点 Pi、Pj 进行“排序”来进一步优化搜索

    • 您可以使用另一个点积来执行此操作，这次改为 (BA)
    • 使用垂直向量让它说（CA）
    • 丢弃 Pi2 中的所有点（以及类似的 Pj2）
    • 其中 ((BA).(P(i1)-A)) 接近 ((BA).(P(i2)-A))
    • 和|((CA).(P(i1)-A))| << |((CA).(P(i2)-A))|
    • 因为这意味着 Pi2 在 Pi1 后面（离 AB 更远）
    • 接近 Pi1 附近 AB 的法线
    • 优化后的复杂性很大程度上取决于数据集。
    • 应该是 O(N+(Ni*Nj)) 其中 Ni/Nj 是剩余点数 Pi/Pj
    • 你需要2N个点积，Ni*Nj距离比较（不需要sqrt-ed）
于 2013-09-04T13:04:47.277 回答
0

（我不确定这是否与大卫的想法有任何相似之处......我只是在登录后才看到它发表我的想法。）为了争论，假设我们把所有东西都换了，所以分界线是x 轴并按 x 坐标对我们的点进行排序。假设 N 不太大，如果我们沿 x 轴扫描（即遍历我们的 a 和 b 的排序列表），我们可以记录总体最小值和两个通过点列表。扫描中的当前点针对来自另一个列表的每个通过点进行测试，而从列表中的点到（我们扫描的 x 坐标，0）的距离大于或等于整体最小值。在下面的示例中，当到达 时b2，我们可以在 处停止测试a2。

        scan ->                 
      Y                           
      |         a2         
      |                   
      |   a1           a3   
X--------------------------
      |     b1           b3
      |             b2
于 2013-09-05T03:56:13.920 回答
0

解决这个问题的典型方法是扫描线算法。假设您有一个坐标系，其中包含所有点和从不同集合中分隔点的线。现在想象一条垂直于分隔线的线以升序从一个点跳到另一个点。为方便起见，您可以旋转和平移点集和分隔线，使分隔线等于 x 轴。扫描线现在与 y 轴平行。

用扫描线从一个点跳到另一个点，跟踪不同集合中两个点的最短距离。如果前几个点都来自同一组，那么很容易找到一个公式，它会告诉您必须记住哪一个，直到您从另一组中击中第一个点。

假设你总共有 N 个点。您必须对 O(N*log(N)) 中的所有点进行排序。扫描线算法本身将在 O(N) 中运行。

于 2013-09-04T13:02:52.290 回答