モートン順序をExcelVBAでやってみた

この記事はExcel2010を使用しております。

当たり判定について調べていた所、モートン順序と言うものを知りました。
表だし何となくExcelで出来るんじゃ無いかと思いやってみました。
ただそれだけの記事ですので、
当たり判定についてやモートン順序について深い考察がある訳ではありませんので
予めご了承ください。

モートン順序とは

L0
0

L1
0	1
2	3

L2
0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

と言うような感じで階層を深くしてもＺ字状に数字が並ぶ順序の事を言うそうです。
その形からZ-orderとも呼ばれているそうです。

並びが綺麗と言うだけでは無く2進数で表記した場合、
先頭のbitを参照するだけで一つ上のレベルの所属番号が直ぐに割り出せる点に
その真価があるようです。

例えばL2の9は[1001]で先頭は[10]です。
L1の2は[0010]である事から、
L2の9はL1の2であると言う事が簡単に分かります。

モジュールを作る

モジュールの作成には
http://marupeke296.com/COL_2D_No8_QuadTree.html
こちらのサイトを参考にさせて頂きました。

Excel2010にはビットをシフトする演算子が実装されていないので
ビットを左にシフトするコードを作ります。

Private Function BitLShift(ByVal num1 As Variant, ByVal num2 As Variant) As Variant
    BitLShift = num1 * (2 ^ num2)
End Function

次に参考にさせて頂いたサイトにある擬似コードを元に
1つずつビットを左に１つシフトするコードを作ります。

Private Function BitSeparate32(ByVal num As Variant)
    num = (num Or (BitLShift(num, 8))) And &HFF00FF
    num = (num Or (BitLShift(num, 4))) And &HF0F0F0F
    num = (num Or (BitLShift(num, 2))) And &H33333333
    BitSeparate32 = (num Or (BitLShift(num, 1))) And &H55555555
End Function

最後にモートン順序の番号を返すコードを作ります。
これをセルに関数として使用します。

Public Function XYtoMotton(ByVal x As Variant, ByVal y As Variant)
    XYtoMotton = (BitSeparate32(x) Or BitLShift(BitSeparate32(y), 1))
End Function

シートでモートン順序をやってみる

XYtoMotton(x,y) をセルに配置します。

引数は
x には =COLUMN()-1
y には =ROW()-1
とします。

これでA1セルから始まるモートン順序になりました。

これを =DEC2BIN() 関数で2進数に表すと

となります。

色分けした通り、
先頭のビットで4つの塊が区別され対応している事が分かります。
並び方が綺麗で面白いですね。
私はまだ眺めることしか出来ていませんが、
モートン順序は色々な応用ができそうな気がしてきますね。