什麼比邊框更好？

我有一種情況，在那裏我有X百萬經緯度點。什麼比邊框更好？

當添加新的長/經點時，我想知道有效哪些其他點位於用戶配置的距離參數內，所以我可以將它們添加到列表中。

有什麼比包圍盒好？

我很想看到的算法，參考和幾個實現;）千恩萬謝！

2009-12-04 Setori

這只是在幾分鐘前在這裏回答：http://stackoverflow.com/questions/1847310/count-number-of-points-inside-a-circle-fast – hirschhornsalz 2009-12-04 17:06:57

請記住，長/緯是奇怪的，因爲距離根據緯度變化。如果所有數據都在一個國家內，這不是什麼大不了的事情。但我看到有人忘記在全球數據集上處理這個問題。 – Nosredna 2009-12-04 17:56:31

哦，當然，不要忘記經度是環繞的。 :-) – Nosredna 2009-12-04 17:57:59

有相當多的選項，是更好的，大多是圍繞space partitioning爲主。

一個常見的，並且通常非常好的選項（實施起來並不難）是使用KD-Tree。 Quadtrees更容易實現，但搜索速度較慢。根據您的數據分佈和您的要求，其他空間分區算法可能執行得更好，內存要求更低或其他相關問題。

來源

2009-12-04 17:07:27

我絕對同意他想做一些空間分區。然而，他將不得不修改四叉樹的概念以使其起作用，因爲它旨在用於矩形區域的二維空間。正如Nosredna正確指出的那樣，他還需要擔心包裝。 – PeterAllenWebb 2009-12-04 21:58:07

是的，但是在這些情況下可以使用quadtrees和kd樹。 Quadtrees更容易，因爲在這種情況下處理包裝變得容易得多。但是，通常情況下，您並不是在處理這樣的情況下處理全局案例，而是處理較小的區域，在這種情況下，大多數問題的問題較少。 – 2009-12-04 22:03:41

一位同事告訴我，他在使用Morton-Code作爲GIS數據的空間索引方面有很好的經驗，可能這是值得研究的問題。

來源

2009-12-04 17:06:42

我在數據庫中使用了數千萬條記錄的Morton代碼 - 它們運行良好。 – 2009-12-19 03:46:32

這種快速和骯髒的方法可能會節省你一些悲痛：地球表面劃分成1個箱。然後，您將有一個180x360元素的數組，你只需要搜索少數盒，包括包含新點盒子，所有的箱子立即圍繞它其中一個角是用戶指定的範圍內。你會發現你可以使用一些技巧來快速找出使用哪些盒子而不用考慮它們。只要不要忘記經緯度環繞。

如果您的「唯一」有幾百萬分，並且它們沒有聚集到熱點，那可能會讓您通過。

理論上優越的方法：您可以將每個點映射到三維空間，然後將它們存儲在octree中，這將使您可以在任意距離內快速找到附近的點。當然，三維空間中的距離與地球上的大圓距離稍有不同，因此您必須計算轉換系數。不過，這應該很簡單。您沒有提及實現語言，但幾乎可以肯定的是，您正在使用的任何語言都會有一個經過充分測試的八叉樹實現。如果您不介意插入第三方代碼，則此解決方案是走。

來源

2009-12-04 21:52:16 PeterAllenWebb