將凹多邊形分解爲凸多邊形

Question

我正在使用僅支持凸多邊形形狀的遊戲物理庫（Box2D）。但是，我希望關卡生成器能夠指定凹多邊形，而不必擔心這一點。

那麼，我該如何自動將凹多邊形分解爲凸多邊形（甚至是所有三角形）。 速度會很酷，但易於實施更重要。拆分只能在遊戲初始化時完成。

（我的語言是Flash/ActionScript 3的，但是這不應該的問題）

Answer 1

你probabaly需要triangulation

Answer 2

伯納德·查澤爾和David P.多布金在1985年提出了一個算法：Optimal Convex Decompositions。

其他方法可以在Wikipedia找到。

Answer 3

本頁說明如何使用ActionScript 3將多邊形轉換爲非複雜形狀。代碼很大，因此我不會在此複製粘貼。

http://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/