分解复杂多边形的算法

Question

我正在尝试从WAD文件中包含的信息创建DOOM 2级别的多边形。我已经完成了墙壁，剩下的一切都是“单位”，地板和天花板区域。厄运地图分为“扇区”，每个地图都会评估到平坦的复杂多边形。

将简单的凸多边形分解为三角形是容易的，因为它有很多算法。但是许多部门的策略是凹形的，有些甚至有一些“洞”，其他部门在其中。以下是一个示例，具有特别复杂的poly以橙色显示： http://screencast.com/t/bnkuzrvy8

任何人都可以推荐算法，或者更好的C＃代码，这将使这种复杂的多个分解为三角形？

我知道WAD文件包括节点，SEG，子级信息等。间接地描述了这种方式的崩溃。但它特别复杂。我不需要B树结构。我想避免不得不将所有这些信息解析出来并将其成功，因为我只有来自扇区信息的复杂多结构。

Answer 1

寻找耳朵剪切三角测量方法，一个好的起点是这个David elbery 文章。