Построение триангуляции Делоне (модели TIN)

Задача построение сети неперекрывающихся треугольников - одна из базовых в вычислительной геометрии и широко используется в машинной графике и ГИС для моделирования поверхности и решения пространственных задач.

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

· выпуклой (если таковым будет min многоугольник, охватывающий область моделирования);

· невыпуклой (если триангуляция не является выпуклой);

· оптимальной (если сумма длин всех ребер min).

Сеть треугольников называется триангуляцией Делоне, если она удовлетворяет некоторым условиям:

1. внутрь окружности, описанной вокруг любого треугольника, не попадает ни одна из исходных точек;

2. триангуляция является выпуклой;

3. сумма min углов всех треугольников максимальна из всех возможных триангуляции;

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

Алгоритмы построения триангуляции Делоне:

Алгоритмы слияния – разбивка множества исходных точек на подмножества, построение на каждом из них триангуляции и последующее их объединение в единую сеть. Сущность одного из таких алгоритмов сводится к следующему. Множество исходных точек делится вертикальными линиями на две или более частей, после чего каждая из них разделяются горизонтальными и вертикальными линиями на примерно равные части. В результате вся область исходных точек оказывается разделенной на примитивы по 3 - 4 точки, по которым строятся 1 - 2 треугольника.

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

· разбивки ребра на два, грани - на три и т.д.;

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

Двухпроходные алгоритмы – сначала идет построение некоторой триангуляции, игнорируя условия Делоне, а затем ее перестраивают в соответствии с этими условиями.

Рис.1. Пример применения алгоритма

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

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

Фрагмент триангуляции Делоне с включенными в нее дополнительными элементами приведен на рисунке 2, где справа показаны узлы, ребра, грани и структурные линии, а слева – структурные линии местности (береговые линии, бровки оврага и др.) и точки с известными отметками.

Рис.2. Фрагмент триангуляции Делоне

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

Модель TIN легко редактируется путем перемещения узлов, вставки новых, удаления имеющихся, изменения положения одного или нескольких ребер, внедрения новых структурных линий. Такие изменения всегда затрагивают небольшую группу смежных треугольников, не требуют перестроения всей сети и осуществляются в режиме on-line, по указанию курсором на соответствующий элемент.

Фотограмметрическая технология построения цифровой модели

Фотограмметрические методы ЦМР основаны на использовании полиномов, нерегулярной сети треугольников TIN и регулярной сети DEM. Непосредственно по аэроснимкам модель рельефа строится на сети треугольников, а для ортотрансформирования, проведения горизонталей и некоторых других операций она преобразуется в регулярную модель DEM. Обязательное условие создания ЦМР - наличие элементов взаимного и внешнего ориентирования снимков, полученных в процессе построения и уравнивания фототриангуляционной сети.

Некоторое представление о размере сторон (ребер) нерегулярной сети треугольников TIN и шаге регулярной сети DEM могут дать следующие данные: для правильного отображения рельефа на плане масштаба 1:2000 путем линейной интерполяции между точками с известными высотами необходимо, чтобы среднее расстояния между ними были не менее:

· 20 м - для плоскоравнинной местности со слабой расчлененностью;

· 10 м -для волнообразной поверхности с гладкими формами;

· 5м-для сильно расчлененной местности с большим числом оврагов, промоин.

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

• «гладкая» модель - построена с помощью полиномиальной функции вида.

• «адаптивная» или «регулярная» модели TIN, построенные по точкам в узлах сетки с заданным шагом с некоторыми дополнительными условиями;

• модель, построенная по векторным объектам, полученным путем оцифровки по стереоизображению структурных линий, точки которых определены в плане и по высоте.

Полученная перечисленными способами ЦМР может быть дополнена структурными линиями, что существенно повысит ее детальность, точность и надежность. Линии водоразделов, бровки оврагов, береговые линии, тальвеги и другие структурные линии, «встроенные» в триангуляцию Делоне приблизят поверхность к реальной, что скажется на качестве последующего ортотрансформирования.

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

1. Определение границ области моделирования (глобальной области).

2.Определение границ подобластей моделирования, различающихся характером рельефа местности и возможностями применения того или иного метода построения ЦМР.

3. Построение регулярной сети со сторонами, параллельными осям X и У с шагом, зависящими от характера рельефа местности.

4. Присвоение всем узлам сетки высот, равных отметке средней плоскости снимка, номера

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

6. Построение сети неперекрывающихся треугольников с вершинами в узлах регулярной сетки (модели TIN) на основе алгоритма Делоне с ограничениями.

Операции 3-6 выполняются в автоматическом режиме, без участия оператора.

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

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

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

Эпиполярные изображения характеризуются отсутствием поперечных параллаксов наблюдаемых точек, что создает удобства для измерения стереомодели и повышает надежность работы коррелятора.

Современные средства построения ЦМР по цифровым изображениям обладают достаточно мощными технологическими средствами ее визуального и статистического контроля. Средствами такого контроля являются:

• преобразование элементов сети треугольников в пространственные объекты с последующим их вращением и визуальной оценкой локальных «выбросов»;

• расчет уклонов и анализ их экстремальных значений;

• статистический анализ экстремальных значений высот точек;

• оценка точности моделирования по уклонениям высот контрольных точек от аппроксимирующей поверхности.

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