c++ - ポリゴンパーティショニングと三角測量

Question

最近、凹多角形を凸多角形に切り詰める方法についてこの質問をしました。三角測量またはポリゴン分割を行うように提案されました。

私が使用しているライブラリ（SFML \ Box2D）は、凸形状のみを取ります。

これが私が知りたいことです：

1. ポリゴンの分割、またはポリゴンの三角形分割は高速ですか？

2. ポリゴンパーティショニングはどのように機能しますか/どのように機能しますか？

---

三角測量では、凸形状も作成する必要がないことを忘れないでください...

Answer 1

ポリゴン分割は、ポリゴンを凸多角形に分割します。
三角測量はそれを三角形に分割します。私が理解している限り、凸多角形を三角形に分割するのは比較的簡単なので、三角形に分割するには、最初に多角形の分割を実行する必要があります。
ポリゴンを凸多角形に分割するのは難しい部分です。私はクラスのために両方を行うプログラムを書きました、そしてあなたが望むなら私はそれを掘り下げることができます。

これが私のコードです： https ：//github.com/meshko/triangulator/tree/master/som

私は10年間触れていないので、注意してください。

Answer 2

あなたの質問に対する完全な答えではありませんが、一般的なポリゴン（凹面、凸面など）があり、それを三角測量する場合（おそらく、後続のopenGLスタイルのレンダリング用）、「制約付きドロネー三角形分割」パッケージを調べることができます。そのような例の1つは、高速で堅牢であると言われているTriangleパッケージです。

私が理解しているように、Triangleで使用されるアルゴリズムはO(nlogn)実行時の複雑さを示します。