由于约束Delaunay三角剖分而识别出多边形三角剖分

Question

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

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

有没有一种方法来识别这些超出多边形的三角形？

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

Answer 1

许多Delaunay三角测量包（例如Triangle，我会推荐）通常包括从三角测量中自动去除“外”三角形的选项。查看文档。

如果您的算法不是这种情况，您应该能够通过测试每个三角形的质心是否位于您指定为约束的多边形内，通过点来删除外三角形例如，在多边形测试中。这应该始终有效，因为受约束的Delaunay三角剖分将确保没有三角形边缘穿过多边形约束边缘（没有部分进/出三角形的机会）。

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