java - 在两组中找到一对最近点的智能和快速方法是什么？

Question

例如，我有两个点列表：

List<Point2D> a;
List<Point2D> b;

i找到这样的和的最好方法是什么j，所以这a.get(i).distance(b.get(j))是最小的？

显而易见的解决方案是蛮力 - 计算从 ina每个点到 in 每个点的b距离，保持距离最短的对。但是这个算法是O(n^2)，这是不好的。有更好的方法吗？

score 3 · Accepted Answer

您可以将其中一个列表放在四叉树或其他一些空间索引中，以使每次查找快速。

作为替代方案，您可以将所有数据放入具有空间索引功能的数据库中。

score 3 · Accepted Answer

对于列表的每个点，a您都可以从列表中找到最近的点，b如本答案中所述。时间复杂度为 O((M+N) log M)。N = |A|，M = |B|。

然后你只需搜索中的点a，有最近的邻居。时间复杂度为 O(N)。

2 回答 2