我正在尝试根据 WAD 文件中包含的信息为 Doom 2 关卡创建多边形。我已经完成了墙壁,剩下的就是“公寓”、地板和天花板区域。 Doom map 分为“扇区”,每个扇区都评估为一个平坦的复杂多边形。
将一个简单的凸多边形分解成三角形很容易,因为有很多算法可以解决这个问题。但是许多扇形多边形是凹形的,有些甚至在其他扇形所在的地方有“洞”。这是一个示例,其中一个特别复杂的多边形以橙色显示:http://screencast.com/t/BNKuzRVy8
谁能推荐一种算法,或者更好的 C# 代码,将这种复杂的多边形分解成三角形?
我知道 WAD 文件包含 NODE、SEG、SUBSECTOR 信息等,这些信息间接描述了这种方式的故障。但它特别复杂。我不需要 b-tree 结构。我想避免必须将所有这些信息解析出来并将它们拼凑在一起,因为我单独从扇区信息中获得了复杂的多边形结构。
最佳答案
寻找耳夹三角测量方法,一个好的起点是这个 David Elbery article .
关于c# - 分解复杂多边形的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9613873/