ポリゴン内の凹面 (非凸面) の周りにボロノイ図を生成する必要があります。オンラインで方法を探しましたが、これを行う方法を理解できませんでした。基本的に、ポイントの凸包を生成し、デュアル ポイントを計算して、これらのポイント間にエッジ ネットワークを構築します。ただし、内側のポリゴンのエッジに出会うときは、凸包のように形状のエッジのように見える必要があります。したがって、これを実行して境界ですべてのエッジをクリッピングすると、内側のポリゴンの境界に適切なエッジがあり、内側のポリゴンの両側にセルがないボロノイ図になります。
例を挙げましょう：
これに関する問題は、セルが内側のポリゴン エッジを横切り、セル構造とポリゴン形状の間に視覚的な関係がないことです。
この問題にアプローチする方法を知っている人はいますか? すでにこれを行っているか、私が達成しようとしていることに近づいているアルゴリズムはありますか?
あらゆる種類の入力に感謝します！
準拠する Delaunay 三角形分割 (つまり、ポリゴンのエッジを制約として含む三角形分割) を構築し、ボロノイ図を双対として形成することができる場合があります。適合する三角形分割により、三角形分割のエッジが制約エッジと交差しないことが保証されます。すべての制約エッジが三角形分割のエッジになります。
このタイプのアプローチのリファレンスとして、こちらの Triangle パッケージをご覧ください。私の経験では、高速で堅牢なライブラリですが、.NET で書かれてcいませんjava。
この段階では、ダイアグラムでポイント (ボロノイ中心) がどのように生成されるかを理解できません。Triangle パッケージは Delaunay リファインメント メッシュ生成をサポートしていますが、ポリゴン ドメインでメッシュ生成を実際に行う場合は、考慮すべき他のアプローチがあるかもしれません。
編集: 一般的な線分のボロノイ図を直接作成することもできるようです。ここでVRONI ライブラリを確認してください。あなたのコメントに対処する - 一般的な多角形の境界にも準拠する均一なボロノイ図を常に期待できるかどうかはわかりません。多角形の境界の形状によって、境界のボロノイ セルに最大の寸法が課されることが予想されます。
お役に立てれば。
明らかに、より大きな多角形の制約に対してボロノイ図を生成する必要があります。あなたはそれを多角形と呼んでいますが、あなたの例の図にはスプラインベースのエッジがあることに気付きました. それは今は忘れましょう。
あなたがしたいことは、かなり等しい長さのエッジを持つ（あなたによって生成されたか、別のソースから生成されたかにかかわらず）包含ポリゴンから始めることを確実にすることです。分散係数を使用すると、これがより自然に見えます。私はおそらく10〜20％の分散に行きます。
ほぼ同じ長さのライン セグメントで囲まれたポリゴンを含むようになったので、ボロノイ図の生成を開始するための基礎ができました。コンテナーの各エッジについて:
各ポイントを段階的に生成すると、アルゴリズムが凹型コンテナーの各凸型「構成領域」を放射状に分割することがわかり始めます。
何のためのリストなのか疑問に思うかもしれません。明らかに、まだ完了していません。必要なボロノイ テッセレーション全体の一部しか生成していません。凹面空間のこれらの「境界」セルを作成したら、境界セルが既に存在するよりも境界の近くに新しいセルを生成したくない場合は、その領域内にのみそれらを配置する必要があります。境界セルのソース ポイントのリストを維持することにより、作成するその他のポイントがその領域内にあることを確認できます。これは、バッファ ゾーンを確保するために内部ミンコフスキー和を計算することに少し似ています。これで、この派生した凹面の残りのセルをランダム化して完成させることができます。
(警告: この前のステップには注意が必要です。「通路」領域が狭すぎる場合、この派生空間の境界が重なり合い、単純ではない多角形ができて、あなたの努力にもかかわらず間違った場所にポイント. 解決策は、エッジからの最大配置距離が最小通路幅の半分を超えないようにすることです...または、ミンコフスキーの合計を含む他の幾何学的手段を1つの可能性として使用します、縮退した派生ポリゴンに巻き込まれないようにします。マルチポリゴン、つまりフラグメントで終了する可能性は十分にあります。)
私はまだこの方法を自分で適用したことはありませんが、解決すべきバグは確かにありますが、一般的な考え方で正しい方向に進むことができると思います。
次のような論文を探してください。
1979 年に書かれた、Kirkpatrick、David Gによる「連続スケルトンの効率的な計算」 。
要約は次のとおりです。
任意の n 行多角形図形の骨格を構築するための O(n lgn) アルゴリズムを提示します。このアルゴリズムは、一般化されたボロノイ図を構築するための O(n lgn) アルゴリズムに基づいています (私たちの一般化では、点セットを端点でのみ交差するように制約された線分のセットに置き換えます)。一般化されたボロノイ ダイアグラム アルゴリズムは、2 つの任意の (標準) ボロノイ ダイアグラムを結合するために線形時間アルゴリズムを使用します。
「線分のセットは、端点でのみ交差するように制約されています」は、あなたが説明する凹型多角形です。