給定一個元組座標列表，找到最近的座標到指定的座標系

這樣做的最有效方法是什麼？我目前的實施非常混亂：給定一個元組座標列表，找到最近的座標到指定的座標系

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，但這應該是一個相當普遍適用的問題。所有座標都是整數值。

來源

2014-03-14 jellyberg

我認爲[代碼審查]這將永遠是真（HTTP：//代碼審查.stackexchange.com）更適合您的問題。 –

我想在同一距離可能會碰到2個coords，對吧？ – Agostino

對不起@Michal我不知道這件事。將在未來發布。 – jellyberg

不要打擾平方根！這是一臺計算機上的慢動作。如果一座建築物比另一座建築物更近，它們之間的距離的平方也將小於到其他建築物的距離的平方。

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

來源

2014-03-14 09:18:01

我想我明白你在說什麼，但我不確定我會如何實施它。你能爲我寫一個例子嗎？ – jellyberg

刪除math.sqrt和math.fabs。 –

我已經更新了我的答案。 –

找到所有建築物的距離（N）。排序距離（Nln（N））。

這是最快的方法。

來源

2014-03-14 08:44:03 Jiminion

它說找到最近的建築物。他似乎想要一個升序列表。 – Jiminion

一些常見的技巧，你可以申請：

如果你的列表的發展慢慢地，你可以緩存distance功能（例如用裝飾或手動的字典），見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))

來源

2014-03-14 08:47:33 Bruce

給定一個元組座標列表，找到最近的座標到指定的座標系

回答

相關問題