最快的三角测量算法带孔？
我正在为RTS游戏寻找路径，我正在游戏网格中构建导航网格。
我写了一个类似于前进方块的算法，它可以创建和简化地图中可走和不可走区域之间的边界。 现在我有一个只包含边的“网格”。 我需要对这个网格进行三角剖分，以便最终的三角剖分包含最初的边缘，然后我可以移除不可走区域以在导航网格中创建孔。 例如，我需要这样做...
三角形代表地图的可行走区域。 这些洞代表不可行走的地区，如山脉或建筑物。 网格可以被认为是2D，因为高度是不相关的。 这显然是一个非常简单的情况。 游戏中的导航网格将包含数千个顶点和多个孔，但我可以将其分解为更小的块以进行动态更新。
我研究了约束Delaunay三角剖分算法，它首先创建Delaunay三角剖分点，然后移除与约束边相交的任何三角形，然后重新对已去除的三角形进行三角剖分。
这对我的目的来说似乎有点多余。 我的网格不需要是Delaunay，它完全由受约束的边组成，所以如果可能的话，我想跳过额外的三角网。 有更好的算法吗？ 我看了看，只能找到约束Delaunay算法。 或者，也许我错了，有约束的Delaunay算法会是最好的？
我之前完成了从头开始的导航网格路径查找，但从未自己生成导航网格。 三角测量算法对我来说是新的。 任何见解？
费尔南德斯等人2008似乎接近最先进的解决复杂领域的问题。 如果您正在寻找（可能更简单）的替代方案，作者在p370的第二段列出了其他可能的算法。
链接地址: http://www.djcxy.com/p/37187.html