小编Har*_*and的帖子

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

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

我如何在 Python 中有效地完成此操作？ 一种简单的方法会检查每个点是否有八个可能的三角形，但由于考虑了许多重复的三角形，这是非常低效的。考虑每个点右下角可能存在的三角形之类的事情，会错过一些三角形。这个问题有通用的算法吗？

我认为 Delaunay 三角剖分是不合适的，因为它总是会创建凸三角剖分。

语境

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