c# - 作为约束 Delaunay 三角剖分的结果识别出多边形三角剖分

Question

我有一组多边形，它们可能共享公共(public)边和节点。所有这些多边形都是严格不重叠的，尽管它们可以共享一个公共(public)顶点或边。

我想批量对所有这些多边形进行三角剖分，因此，我能想到的解决方案是约束延迟三角剖分。但是Constraint Delaunay Triangulation的输出会生成不在原始多边形中的三角形。

有没有办法识别这些非多边形三角形？

编辑:Matlab has a way to do it via the inOutStatus ;我正在寻找一种独立于语言的算法。

Answer 1

许多 Delaunay 三角剖分包(例如我推荐的 Triangle )通常包含从三角剖分中自动神奇地移除“外部”三角形的选项。查看文档。

如果您的算法不是这种情况，您应该能够通过测试每个三角形的质心是否位于您指定为约束的多边形内来修剪外部三角形，通过一个点-例如在多边形测试中。这应该始终有效，因为受约束的 Delaunay 三角剖分将确保没有三角形边与多边形约束边交叉(不可能出现部分进/出三角形)。

您的问题的另一个考虑因素是您描述的批处理。大多数(如果不是全部)Delaunay 三角剖分算法的复杂性是非线性的(Triangle 实现 O(n*log(n)))，所以我认为您实际上可以通过以下方式实现加速逐个处理多边形，而不是一次处理所有多边形。