algorithm - 最快的带孔三角剖分算法？

Question

我正在为一款 RTS 游戏寻找路径，我正在根据游戏的网格构建导航网格。

我编写了一个类似于 Marching Squares 的算法，它创建并简化了 map 上可步行区域和不可步行区域之间的边界。现在我有一个只包含边的“网格”。我需要对该网格进行三角剖分，以便最终的三角剖分包含初始边，然后我可以移除不可行走的区域以在导航网格中创建孔洞。例如，我需要这样做...

三角形代表 map 上的可步行区域。这些洞代表不可行走的区域，例如山脉或建筑物。网格可以被认为是二维的，因为高度无关紧要。这显然是一个非常简化的案例。游戏中的导航网格将由数千个顶点和许多孔组成，但我可能会将其分解为更小的 block 以进行动态更新。

我看过受约束的 Delaunay 三角剖分算法，它首先创建点的 Delaunay 三角剖分，然后移除与约束边相交的任何三角形，然后重新对移除的三角形进行三角剖分。

这对我来说似乎有点多余。我的网格不需要是 Delaunay，它完全由约束边组成，所以我想尽可能跳过额外的三角剖分。有更好的算法吗？我看了又看，只能找到受约束的 Delaunay 算法。或者也许我错了，最好使用受约束的 Delaunay 算法？

我以前从头开始寻找导航网格路径，但从来没有自己生成导航网格。三角测量算法对我来说是新的。有什么见解吗？

Answer 1

Fernandez et al 2008当涉及到分解复杂域的问题时，它似乎接近最先进的技术。如果您正在寻找(可能更简单的)替代方案，作者在 p370 的第二段中列出了其他可能的算法。