Предварительная обработка исходных данных для построения ЦМР

УДК 519.688Ю.Л. Костюк, А.Л. ФуксПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА ИСХОДНЫХ ДАННЫХДЛЯ ПОСТРОЕНИЯ ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА МЕСТНОСТИПредлагаются новые алгоритмы предварительной обработки структурных линий рельефа, полученных на основе методовдистанционного зондирования, позволяющие получать визуально гладкие линии с минимальным числом осцилляций и узловых точек и сохраняющие топологическую корректность набора линий.Важным объектом исследования современных геоинформационных систем является земной рельеф. Как правило, исходные данные для построения цифровой моделирельефа (ЦМР) получаются с помощью методов дистанционного зондирования и представляют собой наборы высотных отметок и структурных линий, задающих дополнительные ограничения на форму рельефа.

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

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

Всоответствии с ним для каждой исходной линии необходимо выделить коридор – область допустимого расположенияданной линии, а затем внутри коридора построить по возможности плавно изменяющуюся расчетную линию, которая и будет заменять исходную.ВЫДЕЛЕНИЕ КОРИДОРАДЛЯ СТРУКТУРНОЙ ЛИНИИИсходные наборы высотных отметок и линий являются нерегулярными, поэтому, прежде всего, необходимо их структурировать на основе триангуляции сограничениями. Для этого по проекциям высотныхотметок и узловых точек линий строится триангуляция Делоне, которая далее перестраивается таким образом, чтобы проекции всех отрезков исходных линийсовпадали с ребрами треугольников.

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

Если существует допустимое пересечение двух структурных линий,то при проверке ограничений точка пересечениядолжна автоматически включаться в каждую из этихлиний и, естественно, стать узлом триангуляции. Врезультате будет действительно получена треугольнаясетка, для которой все отрезки исходных структурныхлиний совпадают с ребрами треугольников (рис. 1).Рис. 1. Триангуляция со слабыми ограничениямина основе исходных изолинийТакая сетка с заданными в ее узлах высотами используется в большинстве известных геоинформационных систем в качестве ЦМР. Однако, как показанов [6], эта модель является недопустимо грубым приближением и требует дополнительного уточнения.

Внастоящей статье треугольная сетка применяетсятолько как вспомогательная структура для выделениякоридоров исходных линий.При любом методе получения структурных линийдля каждого типа линий (горизонтали, линии обрывов, береговые линии) можно определить два значения абсолютной погрешности: ε XY – точность задания координат узлов в плоскости XOY и ε Z – точность расчета высот в узлах. Рассмотрим участокструктурной линии ABC и несколько примыкающих кнему треугольников сетки, расположенных справа походу движения вдоль линии (рис. 2).CABRBWRAVRAUURBVVWРис.

2. Расчет узловых точек границы коридора281Будем считать, что точка R на ребре AU принадлежит коридору линии ABC, если выполняются триусловия:границы L и R формируются путем последовательного добавления к ним узлов исходных границ. На каждом шаге выбираются 2 текущие точки ( li и r j ) и 2( xR − x A ) 2 + ( yR − y A ) 2 ≤ ε XY ,следующие за ними ( li +1 и r j +1 ). Далее для треуголь-zR − z A ≤ εZ ,(1)1( xR − x A ) + ( y R − y A ) ≤( xU − x A ) 2 + ( yU − y A ) 2 ,2т.е. расстояние между R и A как в плоскости XOY, таки по высоте не превышает величины погрешности, и,кроме того, точка R находится ближе к A, чем к U.Пусть RAU – это наиболее удаленная от A точка на22AU, для которой выполняются условия (1), тогда RAUпринадлежит границе коридора. Проходя по смежнымтреугольникам, расположенным вдоль линии ABCсправа, можно последовательно вычислять узловыеточки правой границы коридора RAU , RAV , RBV ,RBW . Узлы левой границы коридора рассчитываютсяаналогично путем просмотра треугольников, примыкающих к ABC слева.

Пример коридора для изолинииприведен на рис. 3.ника li r j r j +1 и точки li +1 проверяется условие Делоне( li +1 находится вне окружности, описанной околотреугольника). При его выполнении текущими n-мивершинами новых границ становятся li и r j +1 , в противном случае треугольником Делоне будет li r j li +1 , ав новые границы добавляются точки li +1 и r j .i := 1 ; j := 1 ; n := 1 ;L[1] := l[1] ; R[1] := r[1] ;пока ( i < m ) или ( j < k ) циклn := n + 1 ;если i = m то началоL[n] := l[i ] ; R[n] := r[ j + 1] ; j := j + 1 ;конецинес j = k то началоL[n] := l[i + 1] ; R[n] := r[ j ] ; i := i + 1 ;конецинес li +1 вне описанной окружности li r j r j +1то началоL[n] := l[i ] ; R[n] := r[ j + 1] ; j := j + 1 ;конециначе началоL[n] := l[i + 1] ; R[n] := r[ j ] ; i := i + 1 ;конецкцКонец алгоритмаРис.

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

пары начальных и парыконечных узлов участка границ, будет весьма сложной задачей, так как границы коридора вычисляютсянезависимо, а число их узлов может существенно различаться. Данную проблему можно решить путем использования кратных узлов границ. Приведем алгоритм модификации границ коридора для незамкнутойструктурной линии, выходящей на границы треугольной сетки. Этот алгоритм фактически строит внутрикоридора триангуляцию Делоне.Алгоритм модификации границ коридораПредполагается, что заданы наборы из m узлов liлевой и k узлов r j правой границы коридора. Новые282Данный алгоритм имеет линейную трудоемкостьO (k + m) . Новые границы включают одинаковое число n узловых точек, n = m + k − 1 , причем для любых pи q, 1 ≤ p ≤ q ≤ n , узлы L p ,..., Lq на левой границе иR p ,..., Rq на правой соответствуют одному участкукоридора.

Новые границы отличаются от исходныхтолько наличием кратных узлов, поэтому форма самого коридора не изменяется. Приведенный алгоритмможно легко модифицировать для обработки коридоров структурных линий, не выходящих на границутриангуляции или замкнутых – нужно только правильно выделять начальные и конечные узлы границ.ПОСТРОЕНИЕ ЛИНИИ ВНУТРИ КОРИДОРАРасчетная структурная линия, которая будет заменять исходную, должна целиком лежать внутри коридора и изменяться по возможности плавно. Преждевсего, необходимо избавиться от лишних узловых точек и уменьшить осцилляцию линии. В [1] в качественачального приближения расчетной линии предлагается использовать ломаную линию минимальной длины с заданными начальной и конечной точками, атакже приводится эффективный алгоритм ее построения.

Эта ломаная по форме подобна резиновой нити сдвумя закрепленными концами, растянутой внутрикоридора, поэтому она имеет минимальное число осцилляций (рис. 4).Рис. 4. Ломаная минимальной длины в коридореРисунок иллюстрирует характерное свойство ломаной минимальной длины – на участках выпуклости(вогнутости) она прижимается к левой или правойгранице коридора, а на участках перегиба переходит содной границы на другую. С этим связан и основнойее недостаток: для замкнутых выпуклых линий онавсегда совпадает с одной из границ.Учитывая, что на самом деле требуется строить нелинию минимальной длины, а линию с минимальнымчислом осцилляций, причем, желательно, проходящую недалеко от центра коридора, можно предложить следующую последовательность действий:- Построение коридора и ломаной минимальнойдлины в нем.- Модификация коридора, при которой все вершины границ Li или Ri , совпадающие с узлами ломаной, сдвигаются к центру коридора (к центру соответствующих отрезков Li Ri ).- Построение ломаной минимальной длины в модифицированном коридоре.В результате узлы полученной ломаной располагаются, в основном, в центре начального коридора,число осцилляций увеличивается незначительно, апорядок трудоемкости построения ломаной не увеличивается.