algorithm - 网格点算法(在网格中寻找点)

Question

我正在搜索一种算法，例如 closest pair of points algorithm

我没有设置所有点之间的任意距离，而是设置了一个网格系统，其中 4 个点分别是右上角、右下角、左上角和左下角。这使所有点之间的距离保持不变。

例如，如果我要在这个网格上放置一个外部点，我需要找到它所在的网格方 block ，假设找到最近的 4 个点(给我网格方 block 的端点)。

我打算为最近的点实现该算法，但由于这些点之间的距离始终相同，我不知道这是否值得使用不同的更高效的算法。

我真的不需要对答案进行详细解释，只需要指出正确的方向即可。

Answer 1

我假设这是二维的？非常简单，您可以这样做——我使用类似的技术在大型数据挖掘项目中快速优化空间聚类。

将您的坐标空间划分为 X 和 Y 方向上固定数量的网格线(您似乎已经这样做了，通过等距分布这 4 个点)。

当您插入一个点时，将其在 X 和 Y 方向上与原点的距离(整数除法)除以您的网格步长间隔。然后您会得到两个标识最近的 X/Y 网格交点的坐标。使用余数确定您的点属于网格交点的哪一侧。

如果你想变得非常复杂，你可以开始使用 kD-Trees 等......但我认为这个例子很简单，不需要任何更复杂的空间分区。