给定一个元组坐标列表，找到一个特定坐标最近的坐标

Question

最有效的方法是什么？我目前的实施非常混乱：

def distanceTo(self, start, end):
    """Distance from cell A to cell B. Look at me, using PYTHAGORUS like a real man."""
    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，但这应该是一个普遍适用的问题。所有坐标都是整数值。在

Answer 1

你可以应用一些常见的技巧：

• 如果您的列表进展缓慢，您可以缓存distance函数（例如使用修饰符或手动使用dict），请参见Here for examples and links

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

• 你的平方值，不需要对它们使用fabs

• 您可以使用排序原语使您的函数易于阅读（除非我误解了它的作用）

示例：

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

Answer 2

计算到所有建筑物的距离（N）。 排序距离（Nln（N））。在

那是最快的方法。在

Answer 3

别费心去求平方根了！它在计算机上是slo-o-o-w。如果一栋楼比另一栋楼近，它们之间距离的平方也将小于到其他建筑物距离的平方。在

我的意思是，如果最近的建筑是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)

基本上，我是想这么做的

^{pr2}$