Блог

У меня есть список XYZ-точек, которые расположены в равномерно распределенной решетке в плоскости XY вот так (например):

Я хочу «выложить» пространство между этими точками треугольниками, которые соединяют точку с двумя из ее ближайших (до) восьми соседей, вот так:

Как мне эффективно сделать это в Python? Наивный подход проверил бы каждую точку на наличие восьми возможных треугольников, но это крайне неэффективно из-за рассмотрения множества повторяющихся треугольников. Делая что-то вроде рассмотрения возможных треугольников в правом нижнем углу для каждой точки, вы пропустите некоторые треугольники. Существует ли какой-то общий алгоритм для этой проблемы?

Я считаю, что триангуляция Делоне не подходит, так как она всегда будет создавать выпуклую триангуляцию.

Контекст

Эта триангуляция является шагом в процессе создания 3D-сеток зданий на основе данных лидарной высоты. Когда я использую «обычные» алгоритмы для создания сеток из облаков точек (пуассон, вращающийся шар), я получаю сетки, в которых есть несколько отверстий (особенно на крутых склонах, таких как башни или стены). Я надеюсь, что смогу решить многие из этих проблем с дырами, признав, что облако точек образует равномерно расположенную решетку в плоскости XY, и триангулировав ее с этой точки зрения, как описано выше.

Рассмотрим каждую подсетку 2×2, в которой существует по крайней мере три точки a , b , c , d .

 a b

d c
 

Чтобы получить триангуляцию, подобную той, которую вы изобразили, проверьте, есть ли только три точки. Если это так, поставьте треугольник, состоящий из этих трех точек. В противном случае положите треугольники abc и acd .