[2d三角剖分给定一组边界点

Question

假设我有一个二进制图像，并且检测到边界像素。基于边界像素，我要进行三角剖分，如下所示。

我应该为该算法查找什么关键字？我查看了Delaunay三角剖分，但根据我的理解，我也需要内部点才能使它起作用。

此图源自this paper。他们称此为“自适应三角形网格”，并声称使用CGAL生成它，但我在“自适应三角形网格”上进行了搜索，并遍历了CGAL的所有文档，但找不到任何相关内容。有人可以指出正确的方向吗？

Answer 1

[我认为您正在寻找的是约束Delaunay三角剖分（CDT），但您可能还会看到它被称为Conforming Delaunay三角剖分（这是“ conformed constrained ...”的缩写）。我在https://github.com/gwlucastrig/Tinfour/wiki/About-the-Constrained-Delaunay-Triangulation上发布了描述CDT的页面。您指定的多边形将限制Delaunay中边缘的整体位置。在https://github.com/gwlucastrig/Tinfour/wiki/Tutorial-Using-Polygon-Based-Constraints，还有一些有关您尝试执行的操作的更多信息。第二篇文章可能是有用的思想来源，但其中的某些讨论与特定的API有关。

您发布的图像中的多边形看起来是凸的。 Delaunay的边界将是凸的。因此，如果多边形是凸形的，则不会在多边形外部放置任何边。但是，如果您的多边形包含一些凹面，则多边形外部将存在边。 Delaunay API的任何体面实现都将使您的代码能够区分边缘是否在约束内。

您发布的图片似乎经历了某种Delaunay细化，该过程是将顶点插入到网格中以创建更坚固的三角形。您会注意到图片中没有“瘦”三角形，并且边界附近有很多小三角形。这些特征是改进技术的典型特征。如果您使用的API不包含优化方法，那么您仍然会获得有效的Delaunay，但从美学角度来看可能并不那么令人满意。代替完善的实现，您可以简单地让代码查找瘦三角形并将其外接圆心插入网格中。

Answer 2

嗯，我首先指出符合CDT的已经是Delaunay。细化算法只是改善了三角形的总体形状。当将网格用于某些数值计算时，细化具有优势。但这并不是每个应用程序都绝对需要的。例如，我使用非精炼网格来计算湖泊和水库的体积和表面积，并且工作得很好（请参见https://github.com/gwlucastrig/Tinfour/wiki/Using-the-Delaunay-to-Compute-Lake-Volume-Part-1）。

有两种主要的Delaunay优化算法：Ruppert和Chew的Second算法。两者都通过在人工网格的有利位置插入人工点来进行操作。鲁珀特（Ruppert's）是两者中的较大者，并保证所有三角形均满足Delaunay准则。咀嚼器产生的三角形更好一些，但我认为不能保证Delaunay。

[我在http://2011.cccg.ca/PDFschedule/papers/paper91.pdf处找到了有关Chew算法的文章，图6给出了精细化功能的良好视觉概念。

我已经计划使用Ruppert的算法在自己的软件库中实现Delaunay Refinement。有一些技术挑战使我慢下来。我相信，如果您寻找Jonathan Shewchuk真正出色的Triangle软件包，或者CGAL库或Java拓扑套件（https://locationtech.github.io/jts/），您会找到一些实现。