Edited at

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

More than 3 years have passed since last update.

この記事は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字状に数字が並ぶ順序の事を言うそうです。

その形から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つずつビットを左に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セルから始まるモートン順序になりました。

image

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

image

となります。

色分けした通り、

先頭のビットで4つの塊が区別され対応している事が分かります。

並び方が綺麗で面白いですね。

私はまだ眺めることしか出来ていませんが、

モートン順序は色々な応用ができそうな気がしてきますね。