python - ランダムに分散されたデータを規則的なグリッドに並べ替える

Question

通常の緯度/経度グリッドで世界中に散在するデータを注文しようとしています。すべてのデータを調べて、それらが属するグリッド セルを確認し、各セルのリストに追加できます。このアプローチは長く、あまり効率的ではないように思えます。

これは新しい問題ではないと確信していますが、Web 上で解決策を見つけることができませんでした。誰か提案がありますか、または例やチュートリアルを教えてもらえますか?

Answer 1

この特定のケースでは、モートン番号を使用できます。「Spatial Keys – Memory Efficient Geohashes」というタイトルのこのブログには実装例があり、Java で書かれていますが、Python バージョンはそれほど違いはありません。

long hash = 0;
double minLat = minLatI;
double maxLat = maxLatI;
double minLon = minLonI;
double maxLon = maxLonI;
int i = 0;
while (true) {
    if (minLat  midLat) {
            hash |= 1;
            minLat = midLat;
        } else
            maxLat = midLat;
    }

    hash <<= 1;
    if (minLon  midLon) {
            hash |= 1;
            minLon = midLon;
        } else
            maxLon = midLon;
    }

    i++;
    if (i < iterations)
        hash <<= 1;
    else
        break;
}
return hash;

Morton コードの利点は、グリッドが大きいほど少ないビット (上記の反復が少ない) を計算でき、グリッドが細かいほど多くのビットを計算できることです。または、きめの細かいコードを計算し、より大きなグリッドには接頭辞を使用します。