algorithm - 给定点的坐标，找出存在于彼此一定距离内的所有点对？

Question

如果两点之间的距离为 0 <= D <= 1000，则 2 个点是对。给定 0 <= N <= 1000 颗星的 2D 坐标（浮点数），确定有多少对。

我以前看过这个问题几次，但我忘记了实现。我相信这与分而治之有关，您将飞机分成两半并在飞机的两侧递归，但我不确定这将如何解决。

不需要任何代码，只需对此类问题的解决方案进行一般演练就足够了。

标签： algorithm

Answer 1

您可能想到的是四叉树，即kd 树的 2D 情况。在四叉树中，您从包含所有点的边界矩形开始。您将所有点插入此基本级别。

从那里，您将四边形分成两半或四分之一。您将每个点插入到它落入的一半或四分之一中。您可以将每一半或四分之一进一步细分为更小的两半或四分之一，将每个点插入它们所属的较小区域。

要查找给定点距离内的所有点，您只需在树中找到所有在给定距离内具有任何点的四边形。然后，您可以仅针对初始点测试这些四边形中的点。

这使您无法对所有点进行典型的n ²比较。