下記記事の続き。
多色同時塗りのFlood Fillを実装している段階で、プリム番号のソートと、キュー管理を調整することで、結果がかなり変化することに気づいた。これを紹介したい。
面白い結果例
この後、理屈が続くので、先に面白い結果を張っておく。
FloodFillペイントの経路について
一般的なFloodFillのイメージは上記（wikipediaより）だろう。ペイントをしたエリアの近くのエリアをペイントする処理をスタックにつんで逐一処理していくが、近くのエリア判定で左右方向が優先されるとこのような結果になる。自分が作ったものは、３Dにこれを拡張しているが、格子状・グリッド状の頂点の並びをに限定しておらず、あるプリムと頂点を共有しているプリムを近くのプリムとみなしている。
今回、さらに多色同時の塗りを実装した（他の色が先に塗ったエリアは塗りつぶさずにまだ塗られていないエリアを各色がペイントしていく。）のだが、上記のWikipedia例とは異なり、スタックではなくキューで処理を進めていったところ、各色がお互いの色のエリアを奪い合うような形となり、また、どのように近くのプリム判定をし、どのようにペイントが経路をとるかによって最終的な各色のエリア分布が大きく個性的に異なることになった。
プリム番号のソートとペイント経路のカスタマイズ
今回の自分の実装では、頂点を共有しているプリムをプリム番号順にソートしている。
i[]@neighbours = sort(i[]@neighbours);このプリム番号をあらかじめソートSOPなどで並び替えるとペイントの経路が変わる。ソートSOPで行えるソートはいくつかあるが、それらを切り替えると経路が大きく変わる。
ペイントエリアの取り合い
前述した通り、ペイント処理の管理にスタックではなくキューを用いることで、各色間でペイントエリアの取り合いがおこなわれる。ランダムなプリム番号ソートを適用していた場合、均等なエリアの割り振りになり、結果ボロノイ分割のような結果が得られる。
さて、ここで、スタックとキューのどちらかではなく、どちらをタスク管理に使うかを割合でブレンドしてみたところ、形状のいびつさのコントロールをする事ができた。
スタック処理を多くすると、1つの色がエリアを広くする力が強くなり、いびつなエリア分割が行われる。キュー処理を多くするとどの色も均等にエリアを広げるようになる。これはシミュレーションのようであり、とても面白い。というか、先のソート処理と合わせてもはや立派なシミュレーションだろう。
パラメータと結果例
パラメータ記載は、Queue率（値が０で完全Stack、値が１で完全Queue）,初期ポイントの数（倍率）、ソートSOPのソートタイプとなる。
特にソートのタイプがランダムでQueue率を低めにすると、まるで地形のようなパターンが現れる。とても面白い。
長くなったのでその３に続いてしまった。
