分解复杂多边形的算法

Question

我想从包含在WAD文件中的信息创建Doom 2级别的多边形。我已经完成了墙壁，剩下的只是'平面'，地板和天花板区域。 Doom地图被分成'部门'，每个部门评估为一个扁平的复杂多边形。

将一个简单的凸多边形分解为三角形将很容易，因为有很多这样的算法。但是很多部门的多边形都是凹形的，有些甚至有其他部门在其中的“洞”。下面是一个例子，一个特别复杂的聚合物显示为橙色：http://screencast.com/t/BNKuzRVy8

任何人都可以推荐一种算法，或更好的C＃代码，将这种复杂的聚合分解成三角形？

我知道WAD文件包含NODE，SEG，SUBSECTOR等信息，它们以这种方式间接描述了故障。但它特别复杂。我不需要b-tree结构。我想避免必须将所有这些信息解析出来，并将它们拼凑在一起，因为我仅从部门信息中获得了复杂的聚合结构。

Answer 1

寻找耳廓三角测量法，一个好的起点是这个大卫埃尔伯里article。