给定元组坐标列表，找到与指定坐标最近的坐标

问题描述

执行此操作的最有效方法是什么？ 我目前的实现非常混乱：

def distanceTo(self, start, end):
    """Distance from cell A to cell B."""
    startx, starty = start
    endx, endy =  end
    return math.sqrt(math.pow(math.fabs(endx - startx), 2)
                     + math.pow(math.fabs(endy - starty), 2))


def findNearestBuildings(self, myCoords, buildingGroup):
    """Returns a list of buildings specified, in ascending order of distance"""
    if len(buildingGroup.sprites()) == 0:
        return None
    buildings = []
    distances = []
    for building in buildingGroup.sprites():
        distance = self.distanceTo(myCoords, building.coords)
        for i in range(len(buildings)):
            if distances[i] < distance:
                if i == len(buildings):
                    buildings.append(building)
                    distances.append(distance)
            elif distances[i] >= distance:
                buildings.insert(i, building)
                distances.insert(i, distance)
        if len(buildings) == 0:
            buildings.append(building)
            distances.append(distance)
    return buildings

什么是更有效的方法来做到这一点？ 我正在使用 PyGame 但这应该是一个相当普遍适用的问题。 所有坐标都是整数值。

您可以应用的一些常见提示：

• 如果您的列表发展缓慢，您可以缓存distance函数（例如使用装饰器或手动使用字典），请参阅

• 使用另一个规范（ max.fabs(x-x0),math.fabs(y-y0)) ）您的distance函数可能会更快：这将防止缓慢的 sqrt

• 您的平方值，无需对它们使用fabs

• 您可以使用 sorted 原语使您的函数易于阅读（除非我误解了它在做什么）

例子：

def findNearestBuildings(self, myCoords, buildingGroup):
      return sorted(buildingGroup.sprites(),key= lambda x:self.distance(x,myCoords))

不要打扰取平方根！ 它在计算机上很慢。 如果一个建筑物比另一个更近，它们之间距离的平方也将小于到其他建筑物的距离的平方。

我的意思是，如果最近的建筑物在 10 米之外，而接下来的两个最近的建筑物分别是 11 米和 12 米，那么您可以轻松地比较 100 (10^2) 并说它小于 121 (11^2) ) 和 144 (12^2) - 这将永远是正确的，因为

if a < b then a^2 < b^2  (for all positive a and b)

基本上，我的意思是这样做

return (endx - startx)*(endx-startx) + (endy - starty)*(endy - starty)