非凸均匀网格三角剖分

Question

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

我可以实现这种三角的，但我不想推倒重来。我可以使用哪种算法来实现这一点？

在此先感谢！

Answer 1

Delaunay三角剖分的边界必然是点集的凸包。但是，如果你的点是在一个规则的网格上，并且你只想要承认跨越一个网格步骤的三角形，那么为什么还要打扰德劳内呢？只需一次遍历你的网格两行，并在任何地方进行三角测量。