algorithm - 如何找出两个点中哪一个最接近一组点？

Question

如何找出两个点中哪一个最接近一组点？

假设我有两个点 (x1,y1) 和 (x2,y2)，我想知道哪个更接近一组点 p1、p2、p3、p4。

有什么算法吗？？

输入的点数和Set中的点数不固定

我们可以有 n 个输入以及 Set 中的 n 个点。

Answer 1

在设置点上构造一个 kD 树。这可以在时间 Ns Log Ns 中完成。

然后对于每个输入点，找到最近的邻居。这需要 Ni Log Ns 时间。最后，找到 Ni 比较中的最短距离。

总时间，(Ns + Ni) Log Ns。这与蛮力相比，采用 Ns.Ni。对于小 Ni，蛮力更可取。