找到最近的XY座標

Question

我已經在2D圖像中獲得了一個點，例如給定圖片中的紅點和一組n點藍點（x1，y1）...（xn，yn），我想以比嘗試所有點更好的方式找到最接近（x0，y0）的點。喜歡有最好的解決方案。如果您有任何類似的課程，我們將不勝感激。

Answer 1

我們可以建議的大多數解決方案都取決於多一點的知識，我會立即斷言並說，除非您已經知道時間不夠。即有成千上萬的藍點，或者你必須在短時間內進行數千次這樣的計算。 「Linear Search」將爲您提供足夠好的服務。

不要打擾計算實際距離，保存自己計算平方根並將其用作「距離」。

大多數其他方法使用更復雜的數據結構來排列點的幾何排列方式。但是實施起來很困難。

Answer 2

有許多方法來此，最常見的可能是使用某種形式的空間分割，以加快搜索，這樣它不是爲O（n）。有關詳細信息，請參閱維基百科上的Nearest neighbor search。