15

複雑な（ただし自己交差しない）ポリゴンを穴で三角形分割して、結果の三角形がすべてポリゴンの内側に配置され、そのポリゴンを完全に覆い、ドロネー三角形の規則に従うようにします。

もちろん、すべてのポイントに対してDelaunay三角形分割を作成することもできますが、ポリゴンの一部のエッジが結果の三角形分割に含まれないのではないかと心配しています。

それで、そのような三角測量は可能ですか？はいの場合、どうすればそれを行うことができますか？

念のため-ポリゴンの内側軸の近似を作成するために必要です（結果の三角形のすべての円周点を接続することで実行できることを願っています）。

4

2 に答える 2

11

制約付きのドロネー三角形分割が必要なようです。「穴」は、三角形分割で途切れないように入力エッジを制約することで実装できます。

実装については、 Triangleおよびpoly2triプロジェクトを参照してください。

于 2011-04-26T19:46:08.393 に答える
4

これは、RTSゲームでnavmeshを実行するときに思いついた方法の1つです。これは自作であり、サードパーティのツールは使用されていないことに注意してください。実装とバグ修正には約3週間かかりました。

  1. すべてのポイントをDelaunay三角形分割にフィードします（最も均一な三角形を取得するため）
  2. 穴の輪郭に沿ってチェックし、輪郭に一致するようにDelaunayによって生成されたポリゴンペアを反転します
  3. 穴の内側をクリップします

結果（plzは紫色のアウトラインを無視します）：

ここに画像の説明を入力してください

于 2013-12-04T13:33:48.093 に答える