我有一个约束delaunay三角剖分（CDT）算法，我有一个多边形（它可能是凹或凸）作为输入 . 如何使用该约束delaunay三角剖分算法将多边形分解为三角形而不引入新点？
编辑：所有三角形的并集必须等于多边形 . 因此，不能仅将CDT与边界作为约束边缘来生成三角形，因为无论输入是凹还是凸，这都会产生凸多边形 .
因为你有一个多边形而不是一个点 Cloud ，最简单的方法就是天真地三角测量然后访问每个边缘并使用简单的线 - 多边形相交测试来测试它是否在原始多边形之外 .
根据您的算法，您可以将此测试作为三角形细分的一部分进行，并跳过最后的传递 . 我确信有一个更好的方法，但这是第一个想到的 .
编辑：
我在我的triangulator上实现了它，它给出了错误的结果，因为我没有实现约束 . 如果确保使用了所有多边形边，那么我相信它应该可以工作 .
1 回答
因为你有一个多边形而不是一个点 Cloud ，最简单的方法就是天真地三角测量然后访问每个边缘并使用简单的线 - 多边形相交测试来测试它是否在原始多边形之外 .
根据您的算法，您可以将此测试作为三角形细分的一部分进行，并跳过最后的传递 . 我确信有一个更好的方法，但这是第一个想到的 .
编辑：
我在我的triangulator上实现了它，它给出了错误的结果，因为我没有实现约束 . 如果确保使用了所有多边形边，那么我相信它应该可以工作 .