使用约束delaunay三角剖分三角剖分多边形

Question

我有一个约束delaunay三角剖分（CDT）算法，我有一个多边形（它可以是凹面或凸面）作为输入。如何使用约束Delaunay三角剖分算法将多边形分解为三角形而不引入新点？

编辑：所有三角形的联合必须等于多边形。因此，不能仅将CDT和边界作为约束边缘来生成三角形，因为无论输入是凹面还是凸面，这都会产生凸多边形。

Answer 1

，因为你有一个多边形，而不是一个点云将很天真三角然后访问每个边和测试，看它是否是使用简单的线条，多边形相交测试原多边形之外的最简单方法。

根据您的算法，你可以做这个测试的三角形细分的一部分，跳过在最后的传球。我确信有一个更好的方法，但这是第一个想到的。

编辑：

我实现了这个在我的三角仪，它给了错误的结果，因为我没有实现的约束。如果你确保使用了所有的多边形边缘，那么我相信它应该可以工作。