将凹多边形分解为凸多边形

Question

我正在使用一个只支持凸多边形形状的游戏物理库(Box2D).但是,我希望关卡生成器能够指定凹多边形而不必担心.

那么,我怎样才能自动将凹多边形分解为凸多边形(甚至是所有三角形).速度会很酷,但实施的简便性更为重要.分手只会在游戏初始化时完成.

(我的语言是Flash/ActionScript 3,但这不重要)

Answer 1

Bernard Chazelle 和 David P. Dobkin 在 1985 年提出了一种算法：最优凸面分解。

其他方法可以在Wikipedia上找到。

Answer 2

你可能需要三角测量