我正在寻找一种算法，如closest pair of points algorithm
我没有设置所有点之间的任意距离，而是设置了一个网格系统，其中4个点分别是右上角，右下角，左上角和左下角 . 这使得所有点之间的距离保持不变 .
例如，如果我要在这个网格上放置一个外部点，我需要找到它将在哪个网格方格，假设找到最接近的4个点（给我网格方块的终点） .
我打算为最近的点实现算法，但由于这些点彼此之间的距离都相同，所以我不知道这是否值得使用更高效的算法 .
我真的不需要对答案进行详细解释，只是朝着正确的方向前进 .
1 回答
我认为这是2维度？很简单，您可以这样做 - 我使用类似的技术在大规模数据挖掘项目中快速优化空间聚类 .
将您的坐标空间划分为X和Y方向上的固定数量的网格线（您似乎已经完成了这一点，通过均匀间隔这4个点） .
插入点时，将其距离（整数除法）与X和Y方向上的原点除以网格步长间隔 . 然后你留下两个坐标，标识最近的X / Y网格交叉点 . 使用余数来确定您的点所属的网格交叉点的哪一侧 .
如果你想变得非常复杂，你可以开始使用kD-Trees等...但我认为这个例子很简单，不能保证更复杂的空间分区 .