python - 给定元组坐标列表，找到最接近指定坐标的坐标

Question

最有效的方法是什么？我当前的实现非常困惑:

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 但这应该是一个相当普遍适用的问题。所有坐标均为整数值。

Answer 1

不用费心去求平方根!它在计算机上是 slo-o-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)

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

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