JAVAの最適化(4)

program Java

今日は９０度回転のアルゴリズムについて考えてみます。
通常であれば、新しいイメージをnewして、そこに回転した画像を置いていきます。

public rotate90( ){
    byte[] newbuf = new byte[ width * height ];
    int sp = width * height - width;
    int spi = 0;
    int j = sp + spi;
    for( int i = 0 ; i <= width * height ; i++ ){
        newbuf[ j ] = pixelbuf[ i ];
        j -= width;
        if( j < 0 ){
            spi++;
            j = sp + spi;
        }
    }
    int tmp = width;
    width = height;
    height = tmp;

    pixelbuf = newbuf;
}

こんな感じでしょうか。
しかし、携帯において、画像１つ分のnewというのは、決して軽い処理ではありません。
なんとかして、newしないで画像を回転できないものかと考えてみました。
まず、2x3のイメージがあるとして、

0 1
2 3
4 5

このイメージを、

0 1
2 3 → 4 2 0
4 5    5 3 1

こうやって出来ればいいわけですね。
これが１次元配列になっているので、

0 → 4
1 → 2
2 → 0
3 → 5
4 → 3
5 → 1

こんな変換さえ出来ればいいと。
で、その式は、

j = width * (height - 1) - (i % height) * width + i / height;

となります。
で、それぞれiとjを交換してやれば出来上がりヽ(´ー｀)ノ


違います(・∀・)


ちょっとシミュレートしてみると分かりますけど、

最初の状態
0 1 2
3 4 5

0番目と4番目を交換
4 1 2
3 0 5

1番目と2番目を交換
4 2 1
3 0 5

2番目と0番目を交換
1 2 4
3 0 5

２番目には０が入らなければならないのに、４が入ってしまいました。これは失敗です。
なぜこうなってしまったかというと、０と４は既に交換されているからです。
本当は０があったところには、４が入ってしまっているので、０と交換することが出来ないのです。
なんとかして、０を探し出して、２番目の値と交換してやる必要があります。


まず、０はどこにあるかというと、４番目にあります。
なぜ４番目にあるかというと、０番目と４番目を交換したからです。
どうやって４という数字を出したかというと、

j = width * (height - 1) - (i % height) * width + i / height;

この式のｉに、０を代入した結果がそうなったからです。
つまり、既に交換されてしまっている番号の場合は、交換されてしまった先を上記の式で求めて、交換されていない番号と交換するのです。
交換されてしまっている番号とは、交換元より小さい数字のことです。
今回の場合は、２番目と０番目なので、交換元（２）より交換先（０）の方が小さいです。
なので、０からもう一度上記の式で計算して、４という数字を出して、２番目と４番目を交換することになります。

2番目と0番目を交換……出来ない
0番目から4番目を算出
2番目と4番目を交換
4 2 0
3 1 5

3番目と5番目を交換
4 2 0
5 1 3

4番目と3番目を交換……出来ない
3番目から5番目を算出
4番目と5番目を交換
4 2 0
5 3 1

5番目と1番目を交換……出来ない
1番目から2番目を算出
5番目と2番目を交換……出来ない
2番目から4番目を算出
5番目と4番目を交換……出来ない
4番目から3番目を算出
5番目と3番目を交換……出来ない
3番目から5番目を算出
5番目と5番目を交換
4 2 0
5 3 1

最後の１つは別に計算する必要はないですが、こうやって、自分以上の数字になるまで変換をして、自分以上の数字になれば交換をします。


これで９０度回転を実装してみます。

public void rotate90( ){
    int i,j;
    byte tmp;
    for( i = 0 ; i < width * height ; i++ ){
        j = i;
        do{
            j = width * (height - 1) - (j % height) * width
                + j / height;
        }while( j < i );
        tmp = pixelbuf[ i ];
        pixelbuf[ i ] = pixelbuf[ j ];
        pixelbuf[ j ] = tmp;
    }
    i = width;
    width = height;
    height = i;
}

出来上がりヽ(´ー｀)ノ


これでnewせずに９０度回転を実装できましたが、その代わり、最後の方はかなりの計算量になりそうです。
最後の方は、式を使って検索するのではなくて、自分の位置からシーケンシャルに探していった方が速いかもしれないですね。


とりあえずこれと同じようにして、２７０度回転も実装出来ます。
で、１８０度回転はflipX()とflipY()をすれば同じ結果が得られるので、そうすることにします。


こうして、９０度ごとの回転アルゴリズムの実装が出来ましたとさ。ちゃんちゃん。


……ほんとにこのアルゴリズムで大丈夫なのかなぁ（;´Д｀）