18

XKCDコミック195では、ヒルベルト曲線を使用してインターネットアドレス空間のマップのデザインが提案されているため、同様のIPアドレスのアイテムがクラスター化されます。

IPアドレスが与えられた場合、そのようなマップ上でその2D座標（0から1の範囲）をどのように計算しますか？

4

3 に答える 3

14

ヒルベルト曲線はフラクタルであるため、これは非常に簡単です。つまり、再帰的です。これは、各正方形を水平方向と垂直方向に二等分し、4つの部分に分割することによって機能します。したがって、一度に2ビットのIPアドレスを左から取得し、それらを使用して象限を決定し、次の2ビットを使用して、正方形全体ではなくその象限を使用します。アドレスのすべてのビットを使い果たしました。

各正方形の曲線の基本的な形状は馬蹄形です。

0 3
 1 2

ここで、番号は上位2ビットに対応するため、トラバーサル順序を決定します。xkcdマップでは、この正方形が最高レベルの走査順序です。おそらく回転および/または反射され、この形状は各2x2の正方形に存在します。

「馬蹄形」が各サブスクエアでどのように方向付けられているかの決定は、1つのルールによって決定されます。つまり0、0スクエアのコーナーは、より大きなスクエアのコーナーにあります。したがって、0上記に対応するサブスクエアは、次の順序でトラバースする必要があります

01
 3 2

そして、前の正方形全体を見て4ビットを表示すると、正方形の次の分割のために次の形状が得られます。

00 01 32 33
 03 02 31 30
 10 13 20 23
 11 12 21 22

これは、正方形が常に次のレベルで分割される方法です。さて、続行するには、後の2つのビットに焦点を合わせ、これらのビットの馬蹄形がどのように方向付けられているかに応じて、このより詳細な形状を方向付け、同様の分割を続けます。

実際の座標を決定するために、各2ビットは実数座標の2進精度の1ビットを決定します。したがって、最初のレベルでは、座標の2進ポイント（[0,1]範囲内の座標を想定）xの後0の最初のビットは、アドレスの最初の2ビットに値0または1が付いているかどうか1です。同様に、y座標の最初のビットは0、最初の2ビットの値がまたはであるかどう1か2です。座標にビットを追加するかどうかを決定するには0、1そのレベルで馬蹄形の方向を確認する必要があります。

編集：私はアルゴリズムを作り始めました、そしてそれは結局それほど難しくないことがわかりました、それでここにいくつかの疑似Cがあります。バイナリ定数に接尾辞を使用し、整数をビットの配列として扱うため、これは疑似ですbが、適切なCに変更するのはそれほど難しくありません。

コードでposは、は方向の3ビット整数です。最初の2ビットは0正方形のx座標とy座標であり、3番目のビットは。1と同じx座標を持っているかどうかを示します0。の初期値はposです。これは、の座標がと同じx座標を持つ011bことを意味します。はアドレスであり、2ビット整数の要素配列として扱われ、最上位ビットから始まります。0(0, 1)10adn

double x = 0.0, y = 0.0;
double xinc, yinc;
pos = 011b;
for (int i = 0; i < n; i++) {
    switch (ad[i]) {
        case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break;
        case 1: xinc = pos[0] ^ ~pos[2]; yinc = pos[1] ^ pos[2]; break;
        case 2: xinc = ~pos[0]; yinc = ~pos[1]; break;
        case 3: xinc = pos[0] ^ pos[2]; yinc = pos[1] ^ ~pos[2];
            pos = ~pos; break;
    }
    x += xinc / (1 << (i+1)); y += yinc / (1 << (i+1));
}

いくつかの8ビットプレフィックスを使用してテストし、xkcdマップに従って正しく配置したので、コードが正しいとある程度確信しています。

于 2009-12-29T21:27:11.040 に答える
5

基本的に、ビットのペア、MSBからLSBを使用して、数値を分解します。ビットのペアは、位置が左上（0）左下（1）右下（2）または右上（3）の象限にあるかどうかを、数値をシフトするにつれて細かくなるスケールで示します。

さらに、「向き」を追跡する必要があります。これは、現在の規模で使用されている巻線です。最初の巻線は上記のとおり（UL、LL、LR、UR）であり、最終的にどの象限に到達するかに応じて、次のスケールダウンでの巻線は現在の巻線から（-90、0、0、+ 90回転）です。 。

したがって、オフセットを累積できます。

私が0,0から始めて、最初のペアが2を与え、オフセットを0.5、0.5にシフトするとします。右下の曲がりは私の最初の曲がり角と同じです。次のペアはスケールを小さくするので、私の調整の長さは0.25になります。

このペアは3なので、x座標のみを変換し、.75、.5になります。これで巻線が回転し、次のスケールダウンは（LR、LL、UL、UR）になります。アドレスのビットがなくなるまで、スケールは.125などになります。

于 2009-12-29T21:14:29.833 に答える
0

ヒルベルト曲線のウィキペディアコードに基づいて、現在の位置を（（x、y）座標として）追跡し、n個のセルにアクセスした後にその位置を返すことができると思います。次に、[0..1]にスケーリングされた位置は、ヒルベルト曲線が完成するときにどれだけ高く幅が広くなるかによって異なります。

from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level:
        right(angle)
        hilbert(level - 1, -angle)
        forward(size)
        left(angle)
        hilbert(level - 1, angle)
        forward(size)
        hilbert(level - 1, angle)
        left(angle)
        forward(size)
        hilbert(level - 1, -angle)
        right(angle)

確かに、これは閉じた形のソリューションではなく、力ずくのソリューションになります。

于 2009-12-29T21:16:16.523 に答える