O（nlogn）時間で制約付きドローネ三角形分割を作成するアルゴリズム（知っている場合は研究論文へのリンク）、および再計算を必要としない制約と頂点の削除と追加を可能にするアルゴリズムを知っている人はいますかCDT全体？
2699 次
1 に答える
9
Chew 1989O(nlogn)はCDT 生成のアルゴリズムを提示し、Sloan 1992も同様です。Sloan のアルゴリズムの方が従うのが簡単だと思いますが、マイレージは異なる場合があります。
動的更新の場合、私が知っている最良のアルゴリズムは、Kallmann らによって提示されています。IIRC のアルゴリズムは制約の数に非常に敏感であるため、たとえば、制約の空間が大きく非常に動的な Minecraft のような世界での経路探索には適していません。
これらの論文はすべて 2D 空間をカバーしています。3D にしたい場合は、独自の調査を行う必要があると思います。いずれにせよ、頑張ってください。
于 2013-11-21T20:28:31.310 に答える