algorithm - 网格点算法（在网格中寻找点）

Question

我正在寻找一种算法，例如最近的点对算法

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

例如，如果我要在这个网格上放置一个外部点，我需要找到它所在的网格正方形，假设通过找到最近的 4 个点（给我网格正方形的端点）。

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

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

Answer 1

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

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

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

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