如何对障碍物进行三角测量？

Question

我想三角化一个充满多边形障碍物的房间。

我特别想找一个简单的算法来实现，因为我正在测试其他功能。效率（因为它可以在一分钟内处理几十个顶点）和三角形的“质量”将不被考虑。现在我的想法是循环遍历每个顶点，检查它可以连接的其他顶点，而不会跨越以前建立的连接。这种方法是否有更简单的解决方案或缺陷？

谢谢

Answer 1

您可以对所有顶点进行三角测量，然后移除类似于alpha形状的最长边。你可以在我的主页找到一个例子：http://www.phpdevpad.de/geofence。

Answer 2

一个简单的解决方案是使用约束三角剖分，将所有多边形边添加为约束。然后，您只需标记从室外开始的域。

如果你正在寻找一个C++实现，你可以看看CGAL library，特别是this example这是做你想做的。