DomiterとZalikが使用するスイープラインアプローチを実装して、Javaの2D空間内の一連のポイントに対して制約付きドロネー三角形分割を生成しました。私が開発したコードが、nランダムに生成されたポイントとkそれらの間の制約エッジに対して本当に機能することを確認したいと思います。
ここで、一般的な戦略を使用して、n頂点のセットからランダムな点を選択し、次に2番目のランダムな点を選択して、それらの間にエッジがあると、制約付きドロネー三角形分割の定義から理解できるのは、制約が機能しない可能性があるためです。エッジは、平面直線グラフのエッジです。したがって、それらは交差していません。ポイントがランダムに選択された場合、交差する制約が生成されないことを確認するためにチェックを実行する必要がある場合があります。そのアプローチはまったく効率的ではないかもしれません。
したがって、制約をランダムに生成するための効率的な戦略を誰かが知っているかどうか疑問に思いました。
前もって感謝します。