如何在圖上找到n個最接近的座標列表

Question

這裏是我的問題，我有一個masterlist，它是數據的子列表，它告訴列表的類型，一個x座標和一個y座標。如何找到使用歐幾里得距離函數的關鍵。例如在master_list的n最接近的字符串：

my_location = ['a', .59, .59] master_list = [['a', .5, .5], ['b', .3, .2], [a, .4, .4], ['b', .45, .45], ['a', .6, .6], ['b', .55, .55]] input: function(3, my_location, master_list) output: [['a', .6, .6], ['b', .55, .55], ['a', .5, .5]]

的關鍵功能應該是這樣的：鍵=開方（（X1-X2） * 2 +（Y1 - Y2） * 2

Answer 1

from math import sqrt 

location = ['a', .59, .59] 
master_list = [['a', .5, .5], 
       ['b', .3, .2], 
       ['a', .4, .4], 
       ['b', .45, .45], 
       ['a', .6, .6], 
       ['b', .55, .55]] 


def get_neighbours(distance, location, locations): 
    neighbours = []  
    for loc in locations: 
     if sqrt((location[1] - loc[1])**2 + (location[2] - loc[2])**2) < distance: 
      neighbours.append(loc) 
    return neighbours 

print get_neighbours(3, location, master_list) 

如果你想快，你應該看看2D碰撞檢測的東西..軸神韻：包圍盒，四叉樹，掃描和修剪等。

你可以做一個簡單的測試，以消除遠的節點，如果你有很多節點（否則保持代碼的簡單，不要過早優化），這可能是值得做的：

if abs(location[1] - loc[1]) > d: 
    continue 

if abs(location[2] - loc[2]) > d: 
    continue 

如果這是你的功課'不要做自己的任何好處讓別人爲你做:)