获取范围内的键/从存储为元组的字典键中查找最近的邻居

Question

我有一本以坐标为键的字典。默认情况下，它们是3维的，比如dictionary[(x,y,z)]=values，但是可以是任何维，因此不能硬编码3维代码。在

我需要找到在新坐标的某个半径范围内是否还有其他值，我理想的做法是不必导入任何插件，比如numpy。在

我最初的想法是将输入分割成一个立方体，然后检查没有匹配的点，但是很明显这只限于整数坐标，并且会以指数形式增长（半径为5需要729倍的处理），而且我的初始代码对于相对较小的值至少需要一分钟，我真的负担不起。在

我听说找到最近的邻居可能是最好的方法，理想情况下，减少使用范围为+-一定数量的键会很好，但我不知道当使用了更多的one point时，你会怎么做。
以下是我目前所知的方法：

dimensions = 3
minimumDistance = 0.9

#example dictionary + input
dictionary[(0,0,0)]=[]
dictionary[(0,0,1)]=[]
keyToAdd = [0,1,1]

closestMatch = 2**1000
tooClose = False

for keys in dictionary:

    #calculate distance to new point
    originalCoordinates = str(split( dictionary[keys], "," ) ).replace("(","").replace(")","")
    for i in range(dimensions):
        distanceToPoint = #do pythagors with originalCoordinates and keyToAdd

    #if you want the overall closest match
    if distanceToPoint < closestMatch:
        closestMatch = distanceToPoint

    #if you want to just check it's not within that radius
    if distanceToPoint < minimumDistance:
        tooClose = True
        break

但是，以这种方式执行计算可能仍然运行得非常慢（它必须对数百万个值执行此操作）。我已经搜索过这个问题，但大多数人似乎都有更简单的数据集来完成这个任务。如果有人能给我点建议，我将不胜感激。在

Answer 1

你说你需要确定在特定点的给定半径内是否有任何关键点。因此，您只需扫描按键，计算每个按键到该点的距离，直到在指定半径内找到一个按键为止。（如果将半径的平方与平方比较，就可以避免实际距离所需的平方根。）

一种优化方法是根据键与点之间的“曼哈顿距离”（也就是说，添加组件偏移量）对键进行排序，因为欧几里德距离永远不会小于这个值。这样可以避免一些更昂贵的计算（虽然我不认为你需要三角函数）。在

如果，正如你在后面的问题中所建议的那样，你需要处理多个点，显然你可以单独处理每一个点，或者你可以找到这些点的中心，并以此为基础进行排序。在