caching - 2D キャッシュに適したデータ構造と空間充填曲線

Question

Peano 曲線などの空間充填曲線は、物理的な空間的局所性を維持するため、線形アドレス空間でキャッシュに適したデータ構造を維持するのに役立つと読みました。

ただし、実際にそれらを使用する方法はわかりません。これらの曲線のいずれかに、線形アドレスを (x,y) 座標に、またはその逆にすばやく変換するための式がありますか? それ以外の場合、特定の座標のペアを検索するときにメモリ内のどこを参照するかをどのように判断すればよいでしょうか? 例は非常に役に立ちます。

Answer 1

コメントに記載されているように、座標をバイナリに変換してインターリーブします。次に、quadkey が必要な場合は、基数 4 の数値として扱います。