2維近似數據的二進制搜索算法

Question

這是我的具體問題。我需要寫一個算法：

1）注意到這兩個數組：

A）的約3000郵政編碼（或郵編數組，如果你是在美國），與經度和緯度的它們覆蓋的區域的中心點（即，每個數組元素對應的3個數字）

b）中的約120,000位置的陣列，其由經度和緯度

2）的每一個位置轉換成其中心點郵政編碼與給定的經度和緯度接近

請注意，位置的經度和緯度不太可能與郵政編碼數組中的精確匹配。這就是爲什麼我要尋找郵政編碼區域中心點的最短距離。

我知道如何計算兩個經度/緯度對之間的距離。我也明白，接近郵政編碼區域的中心位置並不一定意味着您位於該郵編所覆蓋的區域 - 如果您位於非常大的郵政編碼區域但靠近邊界，則可以靠近相鄰郵政區域的中心點。但是，在這種情況下，我不必考慮這一點 - 到中心點的最短距離就足夠了。

解決此問題的一種非常簡單的方法是訪問120,000個位置中的每個位置，並通過計算與每個3000個郵政編碼中心點的距離來找到離中心點最近的郵政編碼。這意味着3000 x 120,000 = 360,000,000的距離計算。

如果郵政編碼和地點位於一維空間（即用1號碼而不是2號碼標識），我可以簡單地按照其一維中心點對郵政編碼數組進行排序，然後在郵政編碼中進行二進制搜索陣列爲每個位置。

所以我想我正在尋找的是一種排序郵政編碼中心點經度和緯度的二維空間的方法，因此我可以對每個位置執行二維二進制搜索。我已經看到了這個問題的解決方案，但這些只適用於直接匹配，而我正在尋找中心點最接近到給定的位置。

我正在考慮緩存解決方案，但是如果有一個快速的二維二進制搜索，我可以使用，這將使解決方案更簡單。

這將是批處理程序的一部分，所以我不算毫秒，但也不需要幾天。它每月運行一次，無需人工干預。

Answer 1

您可以使用空間填充曲線和quadkey而不是四叉樹或空間索引。有一些非常有趣的SFF，例如希爾伯特曲線和具有非常有趣模式的摩爾曲線。