在沒有已知方程的圖中找到最近點的高效算法

Question

我以問題的形式提出這個問題，因爲我的快速和骯髒的實現似乎足夠好。不過，我很好奇什麼是更好的實施。

我有一個真實世界的數據圖。沒有重複的X值，並且X值以整個圖的一致率增加，但Y數據基於現實世界的輸出。我想以編程方式從任意給定點P找到圖上最近的點。我試圖找到一個有效的（即快速）算法來做到這一點。我不需要確切的最近點，我可以解決一個「近乎」最接近的點。

明顯的懶惰解決方案是增加圖中的每個點，計算距離，然後找到距離的最小值。然而，對於大型圖，這在理論上可能很慢;我想要的東西太慢了。

由於我只需要一個近似最接近的點，我想象最理想的最快方程將涉及生成一個最佳擬合線，並使用該線來計算實時點應該在哪裏;但這聽起來像是我不會承擔的一個潛在的數學頭痛。

我的解決方案是一種破解，因爲我認爲我的點P不是任意的，即我假設P通常接近我的圖形線，當發生這種情況時，我可以將遠處的X值從考慮。我計算與P共享X座標的線上點的距離是多近，並使用該點與P之間的距離來計算可能是更接近點的最大/最小X值。

我不禁感覺應該有一個更快的算法，然後我的解決方案（這是唯一有用的，因爲我假設99％的時間我的點P將是一個點已接近線已經）。我試着用google搜索更好的算法，但發現很多算法不太適合，在所有不合適的算法混亂中很難找到我正在尋找的東西。那麼，這裏有沒有人有一個更有效的建議算法？請記住，我不需要一個完整的算法，因爲我已經爲我的需求工作，我只是好奇什麼是適當的解決方案。

Answer 1

如果你可以使用一個數據結構，空間搜索（包括最近的鄰居）一些常見的數據結構...

• 四叉樹（和八叉樹等）。
• kd-tree
• bsp樹（僅適用於一組靜態點）。
• R樹

R樹採用的是多種變體。它與B +樹非常密切相關，但是（取決於變體）葉節點中項目（點）的不同排序。

希爾伯特R樹使用基於希爾伯特曲線的點的嚴格排序。希爾伯特曲線（或者說它的泛化）非常適用於排列多維數據，因此空間中的附近點通常以線性排序靠近。

原則上，希爾伯特排序可以通過對一組簡單的點進行排序來應用。這種自然的聚類意味着搜索通常只需要在數組中搜索幾個相當短的跨度 - 複雜的是你需要計算出它們的跨度。

我曾經有一個關於做希爾伯特曲線排序計算的好論文的鏈接，但是我失去了它。基於格雷碼的排序會更簡單，但在羣集方面效率不高。事實上，格雷碼和希爾伯特曲線之間有很深的聯繫 - 我失去的紙張使用格雷碼相關的功能相當多。

EDIT - 我發現，鏈路 - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490

Answer 2

比方說，你的觀點P=(x,y)和你的真實世界的數據是一個函數y=f(x)

第1步：計算r=|f(x)-y|。

步驟2：查找I的最近點到P：在間隔I=(x-r,x+r)

步驟3查找點。

Answer 3

如果將[x，y]點存儲在quadtree中，則可以快速找到最接近的點（如O（log n））。我認爲這是你可以做的最好的事情，而不需要假設點的前景。這裏沒有重複這個算法，而是看看這個link。

您的解決方案非常好，通過檢查點的變化如何不能計算沿x軸的點數量的邊界，您需要檢查而不是使用任意一點。