algorithm - 如何对一个有障碍物的房间进行三角测量？

Question

我想对一个充满多边形障碍物的房间进行三角测量。

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

谢谢

Answer 1

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

如果您正在寻找 C++ 实现，您可以查看CGAL 库，尤其是这个正在执行您想要的操作的示例。

Answer 2

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