問題タブ [flood-fill]

HTML Canvas で使用するために JavaScript でフラッド フィル アルゴリズムを実装した人はいますか?

私の要件は単純です: 境界色が指定された点での色の特定のデルタよりも大きい任意の色である、単一の点から始まる単一の色でフラッドします。

アップデート：

以下に、フラッド フィルの独自の実装を記述しました。遅いですが、正確です。時間の約 37% は、プロトタイプ フレームワークの一部である 2 つの低レベルの配列関数に費やされています。それらはプッシュとポップによって呼び出されると思います。残りの時間のほとんどは、メイン ループで費やされます。

ところで、これを呼び出すときは、カスタムの stopFunction を使用します。

このコードのパフォーマンスを改善する方法がわかる方がいらっしゃいましたら、よろしくお願いいたします。基本的な考え方は次のとおりです。1) シード カラーは、フラッディングを開始する時点の初期カラーです。2) 上、右、下、左の 1 ピクセルの 4 つの隣接点を試します。3) ポイントが範囲外または既に訪問済みの場合はスキップします。4) それ以外の場合は、ポイントを興味深いポイントのスタックにプッシュします。5) スタックから次の興味深いポイントを取り出します。6) そのポイントの色が停止色 (stopFunction で定義されている) である場合、そのポイントの処理を停止し、ステップ 5 にスキップします。 7) そうでない場合は、ステップ 2 にスキップします。 8) 訪問する興味深いポイントがもうない場合、ループを停止します。

ポイントが訪問されたことを記憶するには、ピクセルと同じ数の要素を持つ配列が必要です。

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

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

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

サンプル入力画像。赤い点は開始ピクセルです。塗りつぶされる領域は、ドット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は画像をホストしていなかったので、私はそれらを自分のサーバーに保存しました。

2点のグリッドを取得しました。各ポイントが他のポイントよりも先に到達できる正方形の量を計算したいと思います。現在、私は FloodFill-Algoritm を実装しています。これは、1 つのポイントが到達できる正方形の量を計算できます。

そのアルゴリズムを変更して、両方のポイントに対して同時に、または少なくとも 1 つずつ「フラッディング」を行うにはどうすればよいですか?

アドビが提供するものは十分な柔軟性がないため、ActionScript3で独自の塗りつぶし関数を作成しようとしています（ターゲットカラーは1つしか指定できませんが、ターゲットカラーの範囲を指定したいと思います）。

だから、私がこれまでに思いついたひどいコードはこれです：

かなり基本的な再帰関数..しかし、明らかにこの方法を使用すると、フラッシュプレーヤーは私をクラップスします:)誰かがこれに対する解決策を手に入れましたか？乾杯！

レイヤーを使ったベクター描画プログラムを作りたいのですが、透明・不透明を使わないようにするために、最下層から最上位レイヤーまで各図形を1つのビットマップに描画したいです。塗りつぶしについては、形状を塗りつぶしたいと思います。私の問題は、描画されて塗りつぶされた形状がある場合、次の形状が少し重なり、新しい形状の境界線が他の形状と同じであり、塗りつぶしが部分的にしか塗りつぶされないことです。ターゲット カラーを使用するのではなく、フラッドフィルの実際の境界を見つけることができる形状の座標を指定する方法はありますか? ありがとう

Java で再帰的な Flood 塗りつぶしアルゴリズムを使用して、画像の一部の領域を塗りつぶしています。イメージが非常に小さい場合は問題なく動作しますが、イメージが大きくなると、JVM からスタック オーバー フロー エラーが発生します。

これが、独自のスタックで Flood Fill を使用してメソッドを再実装する必要がある理由です。（私は、この種の場合にそれを行うための最良の方法であることを読みました）

誰かがそれをコーディングする方法を説明できますか? （手元にコードがない場合は、アルゴリズムの疑似コードで問題ありません）

私はインターネットでたくさん読んだことがありますが、よく理解できませんでした。

編集:再帰コードを追加しました

ありがとう！

パスの長さではなく、かかる時間を気にする場合の優れたパスファインディングアルゴリズムは何ですか。

また、パスをまったく気にせず、到達可能性を確認したいだけの場合は、より高速なアルゴリズムがあります。

（Flood Fillは、この種のものに適したアルゴリズムですか？）

私の最後のCLRSの質問で成功したので、ここに別の質問があります。

アルゴリズム入門、第2版、p。501-502では、互いに素な集合のリンクリスト表現が記述されており、各リストメンバーは次の3つのフィールドを維持しています。

• セットメンバー
• nextオブジェクトへのポインタ
• 最初のオブジェクト（セット）に戻るポインタrepresentative。

リンクリストは、単一の「リンク」オブジェクトタイプのみを使用して実装できますが、教科書には、「ヘッド」リンクと「テール」リンクへのポインタを含む補助的な「リンクリスト」オブジェクトが示されています。「テール」へのポインタがあると操作が簡単になるため、小さいセットのリンクをそれに追加し始めるためにUnion(x, y)、大きいセットのすべてのリンクをトラバースする必要はありません。xy

ただし、テールリンクへの参照を取得するには、各リンクオブジェクトが4番目のフィールド（リンクリスト補助オブジェクト自体への参照）を維持する必要があるように思われます。その場合は、リンクリストオブジェクトを完全に削除し、その4番目のフィールドを使用してテールを直接ポイントしてみませんか？

これは本文の省略だと思いますか？

子供向けのアプリを作ろうとしています。異なる画像になります。そして、それらの画像は、星、ボール、または他の同様の画像のように、さまざまな閉じた形になります。私はiPhoneで描く方法を知っています。色の選び方やブラシのサイズ変更などを知っています。

私が知りたいのは、色を選択することです。画像に触れると、触れた座標の周りの閉じた領域を塗りつぶす必要があります。出来ますか？どうすればいいですか？（たとえば、ボールの内側に触れる場合、ボールは1つの色で塗りつぶされている必要があります）

配列にフラッド フィルを適用する方法を知りたかったのですが、私の配列は 2 次元であり、新しいローマン フォント タイプの文字境界が含まれています。境界線には 1 が含まれ、内側と外側はすべて 0 です。内部のみを0ではなくすべて1で埋めたい。しかし、より多くのメモリを必要としないロジックが必要です。したがって、再帰とスタックまたはキューを避けてください