制約付きdelaunay三角形分割を生成するために制約エッジをランダムに生成する

Question

DomiterとZalikがJavaの2D空間内の点のセットに対して制約付きDelaunay三角形分割を生成するために使用する掃引線アプローチを実装しました。私は、私が開発したコードがnランダムに生成されたポイントとk制約エッジの間で本当に動作することを確認したい。

ここでは、一般的な戦略を使用して、nの頂点のセットからランダムな点を選択してから、2番目のランダムな点を選択し、それらの間にエッジを持たせることができます。これは、制約付きDelaunay三角形分割は制約辺が平面の直線グラフの辺であることです。したがって、それらは交差していません。点がランダムに選択された場合、交差制約を生成しないことを決定するためにチェックを実行する必要があります。そのアプローチは効率的ではないかもしれません。

こうして、誰かが無作為に制約を生成する効率的な戦略を知っているかどうか疑問に思っていました。

ありがとうございます。

Answer 1

あなたは2つの段階のプロセスを試みることができる：

• は、ランダムな点の小さなセットを生成し、非制約ドロネー三角形分割を構築します。この小さな三角形分割のエッジからランダムに選択して、拘束エッジのセットを作成することができます。明らかに、エッジは三角形分割から来ているので、交差しないでしょう。

• 追加セットのランダムポイントをデータセットに追加し、フルセットの制約付きDelaunay三角形分割を構築し、以前に見つかった制約エッジを適用します。

私はこの方法は、非交差を構築する効率的な方法であろうと信じているが、より良いアプローチは、実際のデータを用いてテストするかもしれない、三角測量のコードに設定制約されたデータをランダム化。

Triangleパッケージには、この点で有用なベンチマークジオメトリがいくつか含まれています。

これが役に立ちます。