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

Question

15

我正在使用一个游戏物理库 (Box2D)，它仅支持凸多边形形状。但是，我希望级别构建者能够轻松指定凹多边形而不必担心这个问题。

那么，如何自动将凹多边形分解为凸形或三角形呢？速度显然很重要，但易于实现更为关键。这个分解过程将仅在游戏初始化时进行。

（我的语言是 Flash/ActionScript 3，但这不应该有影响）

- Bart van Heukelom

http://mathoverflow.net/questions/60212/partitioning-a-polygon-into-convex-parts - Victor Sergienko

3个回答

3

你可能需要三角剖分技术。

- Drakosha

2

本页面介绍如何使用ActionScript 3将多边形转换为非复杂形状。由于代码很长，因此我不会在此处复制粘贴。 http://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/ 提供了详细的说明。

- benathon

我非常确定我曾经将它移植到了使用JavaScript的Box2D上。 - benathon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joey · Accepted Answer

1985年，Bernard Chazelle和David P. Dobkin提出了一种算法来解决这个问题：Optimal Convex Decompositions。在维基百科上还可以找到其他方法：Wikipedia。