Модификация триангуляции Делоне для создания моделей рельефа

Во многих разделах науки и техники таких как: цифровая фотограмметрия, авиационная навигация, геология, разработка тренажерных комплексов, 3D - моделирование, компьютерная игровая индустрия и др. стоит задача создания модели рельефа земной поверхности конкретного участка местности. Зачастую на данный участок можно найти уже готовые цифровые карты требуемого масштаба, содержащие информацию о рельефе в виде изолиний, отметок высот, отметок урезов воды и т.п. Вообще говоря такая карта уже является некоторой моделью рельефа, однако она мало приспособлена для дальнейшего машинного использования, ее необходимо преобразовать в вид, удобный для применения.
В настоящее время получили распространение два основных вида цифровых моделей - триангуляционное и матричное представление рельефа. Матрица рельефа представляет собой регулярную двумерную таблицу, координатно-привязанную к местности, в ячейках которой хранятся значения высот, соответствующие либо центру ячейки, либо среднему значению высоты по площади данной ячейки. Основное достоинство матрицы - возможность быстрого доступа к ее элементам, недостаток - большие объемы хранимой и зачастую избыточной информации.
Триангуляционная модель представляет собой сеть треугольников, опирающихся своими вершинами на нерегулярно-расположенные на земной поверхности точки. Плоскости треугольников аппроксимируют рельеф местности. Во многих случаях, особенно когда исходных точек немного и они расположены нерегулярно, данная модель описывает рельеф значительно более экономно, чем матрица, с точки зрения объемов хранимой информации. Следует отметить, что существуют достаточно эффективные методы пересчета одной модели в другую.
Несмотря на то, что методы триангуляции (разбиение пространства на треугольные области) развиваются уже достаточно продолжительное время и список литературы, посвященной этим вопросам, весьма внушителен, например [1, 2, 3 и др.], до сих пор является актуальным разработка методов триангуляции, оптимизированных с точки зрения создания модели рельефа по исходным данным типа изолиний и отметок высот. Чтобы понять, какие недостатки присущи известным методам триангуляции, обратимся к следующему примеру.


На рис.1 приведен пример триангуляции Делоне некоторого участка местности, рельеф которого задан горизонталями (изолиниями рельефа). Всем горизонталям в данном случае приписаны разные значения высот - от 100 до 300 метров. Данный пример имеет весьма типичное расположение горизонталей для местностей с руслом нешироких рек или горных отрогов. Алгоритм триангуляции Делоне не анализирует значения высот, основным его правилом является стремление породить треугольники с равными сторонами, отсюда и недостатки. Если на основе такой триангуляции построить профиль рельефа местности по линии, омеченной на Рис. 1, то можно заметить, что в средней его части появляется ровная горизонтальная площадка (Рис. 3).


С математической точки зрения ее появление объясняется очень просто. При вычислении высоты средней части профиля (как видно из Рис.1) используются треугольники, все три вершины которых лежат на одной горизонтали, т. е. имеют равную высоту, а следовательно и плоскости треугольников расположены горизонтально.
Однако совершенно очевидно, что местность в средней части профиля не является плоской, а имеет прогиб вниз. То есть налицо явное противоречие результата вычислений и экспертной оценки. Если в данном месте карты (местности) имеется русло реки и есть отметка уреза воды, то вопрос с правильной триангуляцией решается достаточно просто - достаточно внести данную отметку в исходные данные триангуляции. К сожалению на самых подходящих и общедоступных в настоящее время цифровых топографических картах масштаба 1 : 200 000 отметки урезов воды стоят крайне редко, а на горных отрогах отметок высот и вовсе не бывает. Каким же образом в данной ситуации получить более правильную модель рельефа?
Этого можно добиться, если заставить алгоритм триангуляции строить треугольники, опирающиеся не на одну и ту же горизонталь, а на разные. Другими словами, среди вершин создаваемых треугольников должна быть, по возможности, хотя бы одна вершина, высота которой отличается от высот двух других.
Как уже было отмечено выше алгоритм Делоне старается разбить область триангуляции на равносторонние треугольники. На очередном шаге алгоритма к текущему ребру для образования треугольника присоединяется точка (из числа тех, которые можно использовать для создания треугольника), которая удовлетворяет определенному критерию. Этот критерий формулируется очень просто: минимальность радиуса описанной вокруг треугольника окружности. Теперь становится ясно как следует модифицировать этот критерий. Необходимо ввести в алгоритм приоритетность: в первую очередь необходимо рассматривать те точки, которые совместно с текущим ребром образуют треугольник с разными значениями высот вершин. Если таких точек множество, то для выбора оптимальной из них следует воспользоваться обычным критерием Делоне. Если приоритетных точек не найдено, то для анализа остальных также используется критерий Делоне.
Реализация предложенной модификации алгоритма Делоне дала результат, представленный на Рис.2. Из рисунка видно, что требуемый результат достигнут, что особенно характерно для участка, по которому был построен профиль. Новый профиль дал следующий график (Рис.4), который хорошо согласуется с представлением человека (эксперта) о том, какой вид должен иметь профиль на данном участке.

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

Литература
1. Скворцов А.В. "Триангуляция Делоне и ее применение" изд. Томского ун-та, 2002 г.
2. Майкл Ласло. "Вычислительная геометрия и компьютерная графика на С++" - М.: "Издательство БИНОМ", 1997. - 304 с.
3. Jonathan Richard Shewchuk, Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22(1-3):21-74, May 2002.

На главную

Хостинг от uCoz