3

インターレース順に線を引くプログラム（フラクタル）があります。もともと、H描画する線を指定して、フレーム数を決定し、フレームNごとに描画しN、次にフレームごとに描画しますN+1。

たとえば、との場合H = 10、N = 3次の順序で描画します。

0, 3, 6, 9,
1, 4, 7,
2, 5, 8.

しかし、バンドが徐々に太くなり、長い間描画されていない間に大きな領域が残るのが好きではありませんでした。そのため、この方法は、すぐに続く線ではなく、各グループの中点線を再帰的に描画するように拡張されました。次に例を示します。

0, (32)          # S (step size) = 32
8, (24)          # S = 16
4, (12)          # S = 8
2, 6, (10)       # S = 4
1, 3, 5, 7, 9.   # S = 2

（括弧内の数字は範囲外であり、描画されていません。）アルゴリズムは非常に単純です。

Set S to a power of 2 greater than N*2, set F = 0.
While S > 1:
    Draw frame F.
    Set F = F + S.
    If F >= H, then set S = S / 2; set F = S / 2.

最後のステップサイズで奇数のフレームを描画する場合、最初の（煩わしい）方法と同じように単純な順序で描画されます。4フレームごとなども同じです。いくつかの中間フレームがすでに描画されているので、それほど悪くはありません。

ただし、同じ順列を各ステップサイズの要素に再帰的に適用できます。上記の例では、最後の行は次のように変更されます。

1,      # the 0th element, S' = 16
9,      # 4th, S' = 8
5,      # 2nd, S' = 4
3, 7.   # 1st and 3rd, S' = 2

前の行には、再帰を有効にするには要素が少なすぎます。ただし、N十分に大きい場合、一部の行では複数レベルの再帰が必要になる場合があります。対応する要素が3つ以上あるステップサイズは、再帰的に並べ替えることができます。

質問1.N要素のこの順列の一般名はありますか？それを使用して追加の資料を見つけることができますか？存在する可能性のある同様の例にも興味があります。私がこれをやりたいと思った最初の人だったら、私は驚きます。

質問2.それを計算するために使用できるいくつかのテクニックはありますか？私はCで働いていますが、この段階ではアルゴリズムレベルにもっと興味があります。私は（理由の範囲内で）他の言語のコードを読んでうれしいです。

私はまだその実装に取り​​組んでいません。最初に順列を事前計算することを期待しています（上記の前の方法のアルゴリズムとは異なります）。しかし、前の方法と同様に、複雑さを事前に計算せずに次のフレームを描画する簡単な方法があるかどうかにも興味があります。

4

1 に答える 1

3

一次元の一様分布列を構築しようとしているように聞こえます。順列は、インデックスのバイナリ表現を逆にすることで計算できます。

def rev(num_bits, i):
    j = 0
    for k in xrange(num_bits):
        j = (j << 1) | (i & 1)
        i >>= 1
    return j

使用例：

>>> [rev(4,i) for i in xrange(16)]
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

一般的なnで動作するバリアント：

def rev(n, i):
    j = 0
    while n >= 2:
        m = i & 1
        if m:
            j += (n + 1) >> 1
        n = (n + 1 - m) >> 1
        i >>= 1
    return j

>>> [rev(10,i) for i in xrange(10)]
[0, 5, 3, 8, 2, 7, 4, 9, 1, 6]
于 2011-11-18T02:01:00.793 に答える