c# - 使用约束 delaunay 三角剖分对多边形进行三角剖分

Question

我有一个约束 delaunay 三角剖分 (CDT) 算法，我有一个多边形(它可以是凹面或凸面)作为输入。如何在不引入新点的情况下使用该约束 delaunay 三角剖分算法将多边形分解为三角形？

编辑:所有三角形的并集必须等于多边形。所以不能只将CDT连同边界作为约束边来生成三角形，因为无论输入是凹的还是凸的，这都会产生凸多边形。

Answer 1

由于您有一个多边形而不是点云，最简单的方法是简单地进行三角测量，然后访问每条边并使用简单的线-多边形相交测试来测试它是否在原始多边形之外。

根据您的算法，您可以将此测试作为三角形 segmentation 的一部分进行，并跳过最后的通过。我敢肯定有更好的方法，但这是第一个想到的方法。

编辑:

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