Триангуляционная модель поверхностей

Триангуляционная модель данных (нерегулярная триангуляционная сеть, TIN) предназначена для описания поверхностей. В качестве моделируемой поверхности может выступать рельеф земной поверхности (рис. 2.10) или распределение какого-то параметра по земной поверхности, например, загрязнения окружающей среды, количества выпадающих осадков или среднегодовой температуры.

Рис. 2.10. Триангуляционная модель поверхности Земли

Заметим, что для моделирования поверхностей может использоваться и растровая модель, когда в каждом пикселе растра задается высота моделируемой поверхности. Однако триангуляционная модель имеет ряд преимуществ по сравнению с растровой. В первую очередь, это более высокая точность моделирования и обычно меньшие затраты памяти. Во-вторых, в триангуляционной модели можно в явном виде представлять резкие изломы поверхности, т.е. точки и линии, вдоль которых резко меняется кривизна поверхности (вершины гор, границы оврагов, обрывы рек, границы искусственных сооружений). В растровой модели предполагается, что вся моделируемая поверхность является гладкой поверхностью.

Исходными данными для построения триангуляционной модели поверхности служат высотные отметки, изолинии, а также различные структурные линии, меняющие форму поверхности.

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

Триангуляция может быть различного вида. В триангуляционной модели данных используется так называемая триангуляция Делоне с ограничениями, в которой треугольники строятся так, чтобы они были «максимально равносторонними», а точнее так, что внутрь окружности, описанной вокруг любого треугольника, по возможности не должны попадать узлы триангуляции (рис. 2.11).

Так как триангуляция определена на плоскости, то для моделирования поверхностей в каждом узле триангуляции дополнительно добавляется еще одна координата – высотная отметка. При этом поверхность как бы «вытягивается из плоскости».

Рис. 2.11. Пример триангуляции Делоне с демонстрацией условия Делоне

Такие триангуляционные модели поверхностей обычно относят к классу так называемых 2,5-мерных моделей, подчеркивая, что, несмотря на наличие z -координат, это не 3-мерная модель, т.к. не любая поверхность может быть описана такой моделью. Например, в этой модели нельзя описать внутреннюю структуру пещеры и склоны горы, являющиеся вертикальными или имеющими отрицательный уклон. На практике, при необходимости моделирования строго вертикальных граней (стены зданий) грани делают «почти» вертикальными, вводя дополнительные узлы в триангуляцию.

Триангуляционная модель данных содержит 3 основных типа данных: узлы, ребра и треугольники (рис. 2.12).

Рис. 2.12. Связи объектов в триангуляционной модели данных

Узлы в триангуляции характеризуются координатами .

Ребра в триангуляции являются отрезками, соединяющими два некоторые узла. Большинство рёбер в триангуляции в явном виде не представляются, т.к. их можно всегда косвенно получить через треугольники. В явном виде представляются только особые ребра, для которых нужно хранить дополнительную информацию, например, признак структурности линии или то, что поверхность не сохраняет гладкость вдоль этой линии.

Треугольники в триангуляции описываются ссылками на 3 образующих узла, а также ссылками на смежные треугольники и особые ребра. Ссылки на смежные треугольники и ребра нужны только для ускорения операций анализа поверхности, а для отображения на карте не нужны.