Построение треугольной сетки – триангуляции Делоне
При построении изолиний на трехмерной однозначной поверхности, заданной набором исходных точек (хi, yi, zi), вначале строится вспомогательная сетка с узлами (хi, yi) на горизонтальной плоскости XOУ. В общем случае исходный набор точек является нерегулярным, поэтому используется треугольная сетка. Для этого на множестве точек (хi, yi) строится триангуляция, чаще всего - триангуляция Делоне. Значения zi в каждой вершине триангуляции определяют систему пространственных треугольников, являющуюся сочнолинейной интерполирующей поверхностью.
Для построения триангуляции Делоне вы можете воспользоваться вашим, ранее разработанным алгоритмом. Или воспользоваться следующим подходом для ее построения.
Триангуляцию Делоне будем стоить, опираясь на ее связь с диаграммой Вороного (см. п. 1.4.4). Идея такова: для каждой данной точки мы будем определять точку, ближайшую к данной. Тем самым мы найдем вершины ячеек Вороного, а следовательно и узлы триангуляции Делоне.
Фрагмент алгоритма построения триангуляции Делоне с комментариями и методическими рекомендациями приведен в табл. 3.Таблица 3
Листинг фрагмента программы построении алгоритма триангуляции Делоне Жми сюда