Триангуляция Делоне

Исходными данными для построения TIN является набор точек с координатами X, Y, Z. Задача заключается в том, чтобы по этому набору точек создать сеть смежных непересекающихся треугольников.

Задача построения триангуляции по набору точек является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она

+

широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач.

Наибольшее распространение в ГИС получила триангуляция Делоне (Delaunay), которая названа по имени ее автора советского математика Бориса Николаевича Делоне (1890-1980). По определению Делоне три точки формируют треугольник в триангуляции тогда и только тогда, когда в окружности, описанной вокруг этого треугольника нет других точек разбиения. Каждый ограничивающий треугольник круг не содержит точек из набора внутри его.

Один из алгоритмов построения триангуляции Делоне основан на генерировании полигонов Тиссена (Thiessen) или Вороного. Для этого поверхность разбивается на области, в которых каждая точка расположена ближе всего к некоторому узлу сети – генерирующей точке. Полученные границы называют полигонами Тиссена или полигонами Вороного. Две точки соединяются линией в триангуляции Делоне, если их полигоны Тиссена имеют общую границу. Этот метод позволяет получить требуемые треугольники. Полигоны Тиссена используются также при анализе близости.