python - 如何对不规则形状的晶格进行三角剖分？

Question

我有一个 XYZ 点列表，它们排列在 XY 平面中均匀间隔的晶格中，如下所示(例如):

我想用三角形来“平铺”这些点之间的空间，这些三角形将一个点连接到它的直接(最多)八个邻居中的两个，如下所示:

我如何有效地在 Python 中执行此操作？
一种简单的方法会检查每个点是否有八个可能的三角形，但由于考虑了许多重复的三角形，因此效率非常低。做一些事情，比如考虑每个点右下角可能的三角形，会错过一些三角形。这个问题有一些通用的算法吗？
我相信 Delaunay 三角剖分是不合适的，因为它总是会创建一个凸三角剖分。



语境
这种三角测量是从 LIDAR 高度数据生成建筑物 3D 网格过程中的一个步骤。当我使用“通常的”算法从点云(泊松、旋转球)生成网格时，我最终得到的网格中有许多孔(尤其是在塔或墙等陡峭的斜坡上)。我希望我可以通过识别点云在 XY 平面中形成均匀间隔的晶格并从上述角度对其进行三角剖分来解决很多这些孔问题。

Answer 1

考虑每个 2x2 子网格，其中至少有三个点 a , b , c , d存在。

a b

d c

要获得像您所描绘的那样的三角剖分，请测试是否只有三个点。如果是这样，请放置一个由这三个点组成的三角形。否则，放置三角形 abc和 acd .