4

画像の領域に塗りつぶしを実行する必要があります。ただし、実際に結果の画像は必要ありません。フラッドフィルによって変更されるすべてのピクセルを含む最小の長方形を知る必要があるだけです。

フルフラッドフィルを実行するよりも安価にこの長方形を計算できるフラッドフィルアルゴリズムの変形はありますか？

入力と出力の例（赤い長方形のみが必要です）：

サンプル入力画像。赤い点は開始ピクセルです。塗りつぶされる領域は、ドットhttp://www.finnw.me.uk/ffinput.pngサンプル出力を含むシアンのZ-テトロミノです。赤い長方形の位置/幅/高さのみが重要ですhttp://www.finnw.me.uk/ffoutput.png

編集：島を使用した例2：島
を使用した入力 例http://www.finnw.me.uk/ffinput2.png出力例http://www.finnw.me.uk/ffoutput2.png

例3：
偽の島の例http://www.finnw.me.uk/ffinput3.png

編集

申し訳ありませんが、ハードディスクの故障で画像が失われました。私が最初にこれを投稿したとき、SOは画像をホストしていなかったので、私はそれらを自分のサーバーに保存しました。

4

2 に答える 2

2

基本的に、bigightX、bigightY、smallestX、および leastY を決定する必要があります。

実際のエッジの右下隅を見つけます。

これを行うには、色の内側で可能な限り右 + 下に移動します。

右+下に移動できなくなった場合は、島の隅で立ち往生していないことを確認する必要があります。これを確認するには、エッジ全体をたどって、さらに右下に移動する機会を探す必要があります。実際に本当の優位性がある場合に備えて、これが発生するたびに (biggestX、biggestY、smallestX、smallestY) を追跡できます。

実際に島がある場合は、端に沿ってさらに右下に移動できる場所が最終的に見つかります。

もっと右から下に移動する機会がなく、開始点に到達した場合は、実際の優位性があります。そして、(biggestX、biggestY、smallestX、および leastY) を計算しました。

于 2010-02-14T13:38:55.063 に答える
1

考えられる方法の 1 つは、開始点からできるだけ遠く (左、上、下、右) に進み、最初の端点に戻るまで時計回りまたは反時計回りに端をたどることです。エッジをトラバースするときに、min(X,y) と max(X,Y) を追跡します。

かなり奇妙な形を塗りつぶさない限り、これにより、より少ないピクセルを表示できるはずです。

于 2010-02-14T14:04:21.073 に答える