computational-geometry - ポリゴンをポイントで定期的に埋める方法は?

Question

四角形を塗りつぶすのは簡単です。グリッドを作成するだけです。しかし、ポリゴンが無条件の場合、タスクはそれほど簡単ではなくなります。
おそらく「定期的に」は、他の点間の距離が R ± alpha となるように定式化できます。しかし、これについてはよくわかりません。
おそらく、これを達成するための既知のアルゴリズムがいくつかあります。
追加:
大きな穴がなく、ポイントが大きく集まっていないネットを生成する必要があります。

Answer 1

ポイントの力指向レイアウトを使用することについて考えたことはありますか？

ポリゴンのバウンディングボックス上にランダムに多数のポイントを分散させてから、2つの簡単なルールを繰り返し適用してそれらの位置を調整します。

1. ポイントがポリゴンの外側にある場合は、そのポイントを可能な限り最小の距離だけ移動して、そのポイントがポリゴンのエッジの最も近いポイントに収まるようにします。
2. ポイントは、それらの間の距離に反比例する力で互いに反発します。つまり、すべてのポイントについて、1つおきのポイントを考慮し、2つのポイントを直接離す反発ベクトルを計算します。ベクトルは、近接するポイントの場合は大きく、離れたポイントの場合は小さくする必要があります。ベクトルを合計し、ポイントの位置に追加します。

何度か繰り返した後、ポイントは定常状態に落ち着き、ポリゴン領域全体に均一に分布するはずです。この状態がどのくらいの速さで達成されるかは、ポリゴンのジオメトリと、ポイント間の反発力をどのようにスケーリングしたかによって異なります。

Answer 2

ポリゴンの制約付き Delaunay 三角形分割を計算し、Delaunay 改良アルゴリズムを使用できます (このキーワードで検索)。

最近、Fade2D ライブラリhttp://www.geom.at/fade2d/html/に改良を実装しました。自己交差のない任意の多角形と、結果として得られる各三角形の外接円の半径の上限を取ります。この機能は、現在のリリース 1.02 にはまだ含まれていませんが、試してみたい場合は、Linux または Win64 用の現在の開発バージョンをコンパイルできます。