3

穴のあるベクトル多角形があるとします。接続されたセグメントを描画して塗りつぶす必要があります。もちろん、穴があるので、単一の連続したポリラインを使用して埋めることはできません。パスを時々中断し、スキップされた領域に移動して、そこで別のポリラインを開始する必要があります。

私の目標は、ポリゴン全体を埋めるために必要な一連のポリラインを見つけることです。最小のセットを見つけることができれば(つまり、多角形を最小数の中断で埋めることができる方法)、より良い結果が得られます。

おまけの質問:部分的な密度で塗りつぶすにはどうすればよいですか? たとえば、100% の密度で塗りつぶしたくはありませんが、50% の密度が必要です (これには、塗りつぶし線が互いに平行で、幅が 1 単位であると仮定して、2 単位の距離に配置する必要があります) ）。

フラッド フィル アルゴリズムに関連するものはたくさんありますが、ここでは同様の質問を見つけることができませんでした。

アイデアや指針はありますか？

更新:ウィキペディアからのこの写真は、架空の洪水経路を示しています。ビットマップを使用してそれを行うことができると思います。ただし、ベクターポリゴンがあります。ラスタライズすればいいの？

パスの例

4

1 に答える 1

1

ここでは、線間の距離を1単位と想定しています。ポリラインの最小数を見つける保証のない大まかな実装は次のとおりです。

  1. 空のポリラインのセットから始めます。
  2. ポリゴンのminxとmaxxを決定します。
  3. xをxminからxmaxに、1ステップでループします。線Lはxの垂直線です。
    • 垂直線Lをポリゴンと交差させます（迅速なアルゴリズム、見つけやすい）。これにより、一連のセグメントが得られます：{（x、y1）-（x、y2）}。
    • すべてのポリライン、およびすべてのセグメントについて、セグメント+ポリラインの終わりをマージします（以下の注1を参照）。セグメントとポリラインをマージするときは、ポリラインの最後に（セグメントに結合するために）小さなストレッチを追加し、セグメント自体を追加します。それを使用してマージできないすべてのセグメントについて、グローバルセットに新しいポリラインを追加します。
  4. 最後に、可能であればポリラインを再度マージしてみてください（端が互いに接近しています）。

新しいセグメントを既存のポリラインにマージするための最適なアルゴリズムは、簡単に見つけることができる必要があります（yでハッシュする）。そうでない場合は、ブルートフォースアルゴリズムで十分です。

  1. ポリゴンに無数の穴がない場合は、ラインスキャンごとの新しいセグメントの数が多すぎないようにする必要があります。
  2. すべてのステップでのグローバルポリラインの数が多すぎないようにする必要があります。
  3. 全体ではなく、各ポリラインの終了セグメントとのみ比較します。

注（1）を追加：ポリゴンのエッジがほぼ垂直である場合をカバーするために、マージプロセスでは、yデルタだけでなく、2つのy範囲が重なっている場合（つまり、ポリラインのy範囲の終わり）にマージを許可する必要があります。オーバーラップセグメントのy範囲）。

于 2012-02-04T13:16:30.913 に答える