非凸均匀网格三角剖分

Question

我正在尝试对 2D 中的非凸均匀点网格进行三角剖分。我只需要在每个点的 8 个邻域中使用三角形。问题是，当使用 vtkDelaunay2D 时，我获得了违反此条件的三角形，导致（在某些配置中）凸平面图形三角剖分，即使存在非凸三角剖分。

我可以实现这种三角剖分，但我不想重新发明轮子。我可以使用哪种算法来实现此目的？

提前致谢！

Answer 1

Delaunay三角剖分的边界必然是点集的凸包。但是如果你的点在一个规则的网格上，而你只想承认只跨越一个网格步长的三角形，那为什么还要用 Delaunay 呢？只需一次遍历两行网格，并尽可能进行三角剖分。