空間充填曲線エクスプローラー
線には長さがあっても面積はなく、正方形には面積があります。それでも、線を折り曲げて、正方形のあらゆる部分を通るようにすることができます。まず、いくつかのマスと、それらを通る一本の折れ曲がった線から始めます。すべてのマスをさらに小さなマスに分け、そのすべてを通るように線を折り曲げます。これを繰り返します。ペンがヒルベルト曲線、ペアノ曲線、その仲間たちをレベルごとに描いていく様子を眺めてから、曲線上の好きな場所にペンを置いて、線のどの点が正方形のどのマスに入るかを確かめてみましょう。 空間充填曲線とは、グリッドのすべてのマスを通る一本の線です。レベルが上がるたびに、すべてのマスがさらに小さなマスに分けられ、線は折れ曲がりながらそのすべてを通ります。「再生」を押すと、ペンが各レベルを始点から終点まで描いていく様子を見られます。「ステップ」を押すと、次のレベルを描きます。ヒルベルト曲線、ムーア曲線、ペアノ曲線、Zオーダー、ゴスパーの flowsnake、シェルピンスキーの矢じり曲線から選べます。図の上、その下の色付きの線の上、または「ペン」スライダーをクリックまたはドラッグすると、ペンを曲線に沿って動かせます。「位置」のタイルには、ステップの番号と、そのステップがあるマスが表示されます。色は線に沿って移り変わるので、色の近いマスどうしは、ステップも近いということです。
使い方
- 「再生」を押してペンが各レベルを始点から終点まで描く様子を見るか、「ステップ」を押して次のレベルを描きます。「レベル」をドラッグすると、好きなレベルに移れます。
- ヒルベルト曲線、ムーア曲線、ペアノ曲線、Zオーダー、ゴスパー曲線、シェルピンスキーの矢じり曲線から選びます。
- 図の上、その下の色付きの線の上、または「ペン」スライダーをクリックまたはドラッグして、ペンを曲線に沿って動かします。
- タイルで線分の数、長さ、フラクタル次元、ペンの位置を読み取ります。
すべてのマスを通る線
レベル n のヒルベルト曲線は、2ⁿ × 2ⁿ 個のマスからなるグリッドを通り、各マスを一度ずつ訪れ、つねに隣のマスへ進みます。レベル1は、4つのマスを通るただ一つの折れ曲がりです。レベルが一つ上がるたびに、すべてのマスが4つの小さなマスに、すべてのステップがこの折れ曲がりの小さな複製に置き換わり、複製は端と端がつながるように向きを変えられます。4ⁿ 個のマスを通る線は 4ⁿ − 1 ステップからなり、長さは正方形の一辺の 2ⁿ − 2⁻ⁿ 倍です。図の大きさは変わらないまま、長さはレベルごとにほぼ倍になります。ペアノ曲線は、マスごとに9つのマスを使い、S字の折れ曲がりで同じことをします。ムーア曲線は、四つのヒルベルト曲線をつないで閉じたループにします。
数直線から正方形へ
図の下の色付きの線は0から1までの数直線で、曲線はその数直線を正方形の中に折りたたんだものです。ペンを動かすと、「位置」のタイルが、ペンがどのステップにあり、それがどのマスなのかを教えてくれます。ヒルベルト曲線では、番号の近いステップはつねに近くのマスにあります。これは色を見ればわかります。それぞれの色が、ひとかたまりになっているからです。地図や画像などの二次元データを一次元のメモリに保存するのにヒルベルト曲線が使われるのは、このためです。Zオーダーのほうが計算は簡単です。マスの座標は、ステップ番号のビットを順番に配り分けただけのものだからです。しかし、Zオーダーはジャンプします。ステップのほぼ半分は、隣のマスへ進みません。
ほかの形を埋める曲線
ゴスパー曲線、別名 flowsnake は、三角形のグリッドの上で各線分を七つの線分に置き換え、フラクタルな海岸線をもつ形、ゴスパー島を埋めます。その次元は、正方形を埋める曲線と同じく 2(log 7 / log √7)です。シェルピンスキーの矢じり曲線は、各線分を、長さが半分の三つの線分に置き換えます。面積を埋めることは決してなく、シェルピンスキーの三角形に近づいていきます。その次元は log 3 / log 2 ≈ 1.585 で、線と面の中間です。
よくある質問
線がどうして正方形を埋められるのですか?
どのレベルも、単独では正方形を埋めていません。どのレベルも、長さがあって面積のない、ふつうの線です。しかし、レベルを重ねるうちに線は落ち着いていきます。線に沿って決まった割合だけ進んだところにある点は、レベルが変わっても動く幅がだんだん小さくなり、すべてのレベルの極限は、正方形のすべての点を通る連続な曲線になります。ジュゼッペ・ペアノは1890年にそのような曲線が存在することを証明し、当時の数学者たちを驚かせました。
曲線はすべての点をちょうど一度ずつ通るのですか?
どのレベルも、そのグリッドのすべてのマスをちょうど一度ずつ通ります。しかし極限の曲線は、正方形のいくつかの点を二度以上通らなければなりません。1879年にオイゲン・ネットーが、線を正方形の上へ連続かつ一対一に写すことはできないと証明したからです。ヒルベルト曲線は、いくつかの点を二度、三度、あるいは四度通ります。
ヒルベルト曲線とZオーダーの違いは何ですか?
どちらも、グリッドのマスを長い一列に並べます。ヒルベルト曲線はつねに隣のマスへ進むので、列の中で近いマスはグリッドの中でも近くにあります。Zオーダーは、二つの座標のビットを交互に並べるだけなので計算は速いのですが、ステップのほぼ半分がジャンプで、なかには正方形全体をまたぐものもあります。「長さ」のタイルが、ジャンプの数を数えています。
空間充填曲線は何に使われていますか?
二次元のデータを、隣どうしを近くに保ったまま一次元の順序に並べるのに使われます。データベースや地図サービスは、ヒルベルト曲線に沿って、あるいはZオーダーで場所にインデックスを付けます。画像処理ソフトは、丸め誤差を分散させるために、ヒルベルト曲線に沿ってピクセルをたどります。インターネットのアドレス空間の地図では、関連するアドレスを隣り合わせに保つためにこの曲線が使われます。
シェルピンスキーの矢じり曲線は、なぜ正方形を埋めないのですか?
各線分を、長さが半分の三つの部分にしか分けないからです。面積を埋めるには四つ必要です。この曲線は、面積がなく、次元が log 3 / log 2 ≈ 1.585 の図形であるシェルピンスキーの三角形に近づいていきます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ