Построение ЦМР на основе структурных линий и высотных отметок (1027380), страница 2
Текст из файла (страница 2)
Другими словами, если zC < z A , то z D > z A , и наоборот.Пусть ABC – горизонтальный треугольник, т.е.z A = z B = zC . Для определения знака приращения высоты в его внутренних точках необходимо проверятьокрестность ABC, переходя к смежным треугольникамстрого по горизонтальным ребрам до тех пор, пока небудет найден негоризонтальный треугольник. Пустьэто треугольник DEF, и z E = z F = z A , а z D ≠ z A .
Еслипереход к DEF проходил только по недопустимымребрам, то знак приращения относительно уровня z Aво внутренних точках ABC такой же, как в точке D.При каждом пересечении отрезка изолинии знак приращения меняется на противоположный. Если высотыизолиний заданы корректно, то знак приращения независит от порядка проверки окрестности ABC. Вэтом можно убедиться, проверив все треугольники награнице горизонтального участка, в который входитABC. Рис.
3 иллюстрирует данную проверку: знакиприращений для пар точек D,E и G,H должны бытьразными.ECDHABмыми ребрами, причем данные цепочки начинаются изаканчиваются треугольниками с одним недопустимым ребром.Пусть некоторая цепочка начинается с треугольника ABC, а заканчивается треугольником UVW, причем BC и VW – недопустимые ребра, т.е.z B = zC = zV = zW , а точки B, C, V и W являются вершинами изолиний одного уровня.
Предположим, чтоломаная, проходящая из A в U через центры недопустимых ребер, имеет длину L, а длина самого короткого недопустимого ребра цепочки равна l. Вычислимна ломаной новую точку M по следующим правилам:Если z A ≠ zU , то полагаем, что высота вдоль ломаной от A до U изменяется линейно. Тогда M – эторавноудаленная от A и U точка ломаной (рис. 4, а), иzM = ( z A + zU ) / 2 .Если z A = zU ≠ z B , то поверхность имеет седловую точку. Будем считать, что седловой точкой M является точка пересечения ломаной и самого короткогонедопустимого ребра цепочки (рис.
4, б и в), причемz ⋅ L + zA ⋅ lzM = B.L+lЕсли z A = zU = z B , то цепочку образуют треугольники внутри замкнутой изолинии. Естественно предположить, что соответствующий участок рельефатакже является почти горизонтальным. Будем считать, что наибольшее отклонение от горизонтальнойплоскости z = z B достигается в точке M – центре самого длинного недопустимого ребра (рис. 4, г), а высота zM = z B ± Δz , где знак отклонения определяетсятак же, как и для треугольников с тремя недопустимыми ребрами.GUWVРис. 3.
Проверка знака приращения высоты для центра треугольника ABC (выделены изолинии и треугольники с недопустимыми ребрами)ПОСТРОЕНИЕ ТРИАНГУЛЯЦИИС СИЛЬНЫМИ ОГРАНИЧЕНИЯМИТреугольная сетка, на которой выполняются слабые ограничения, может содержать треугольники содним, двумя или тремя недопустимыми ребрами.
Горизонтальный треугольник ABC с тремя недопустимыми ребрами на уровне z A интерполирует участокрельефа, который реально также является почти горизонтальным. Будем считать, что центр ABC (точка O)отклоняется от z A по вертикали на фиксированнуювеличину Δz . Для определения знака отклонения необходимо проверить треугольники в окрестности ABC(алгоритм проверки приведен выше). Задав в O высоту z A ± Δz , можно заменить ABC на три треугольникаABO, BCO, CAO, содержащих по одному недопустимому ребру.Перестроим все треугольники с тремя недопустимыми ребрами.
После этого в триангуляции останутсяцепочки смежных треугольников с двумя недопусти288UMCBVCAAаMBWCBвWVVMAбUUWMCABгРис. 4. Проверка цепочек треугольников с недопустимымиребрами и добавление новой точки M: а – между изолиниями разных уровней, б и в – на участках с седловой точкой,г – внутри замкнутой изолинииВычисленная точка M должна стать новой вершиной триангуляции, и это потребует соответствующегоперестроения треугольной сетки. Для исключения возможного вырождения треугольников точку M следуетдобавлять, как в итеративном алгоритме триангуляцииДелоне [2], но перестраиваться должны только недопустимые ребра.
Полученная система треугольниковуже не будет триангуляцией Делоне, зато в ней не будут нарушены слабые ограничения. После добавленияточки M цепочка недопустимых треугольников разбивается на две более короткие (возможно, пустые) це-почки, а общее число недопустимых ребер уменьшается. Процесс заканчивается, когда недопустимых реберв триангуляции не останется.Алгоритм проверки сильных ограничений триангуляции. Предполагается, что по исходному набору точек и линий построена триангуляция со слабымиограничениями.Шаг 1. Проверка всех треугольников сетки, выделение и отметка всех недопустимых ребер.Шаг 2.
Перестроение всех треугольников с тремянедопустимыми ребрами.Шаг 3. Цикл, пока есть цепочки треугольников снедопустимыми ребрами:- обработка очередной цепочки,- вычисление новой точки M и включение ее втриангуляцию.Конец алгоритмаОбработка очередной цепочки включает выделение начального треугольника и проход по недопустимым ребрам до конечного треугольника. При этомпроизводится расчет длины ломаной вдоль цепочки, атакже поиск самого длинного и самого короткого недопустимого ребра. Добавление точки M в триангуляцию является элементарным шагом, так как треугольник, в который попадает M, известен заранее. В целомприведенный алгоритм напоминает алгоритм быстройсортировки Хоара [3]: включение точки M и разбиение цепочки на две более короткие – это полный аналог разделения сортируемого массива опорным элементом.
Поэтому совпадут и оценки трудоемкости:если в цепочку входят m треугольников, то для ееполного перестроения потребуется в среднемO (m log m) операций. Общая трудоемкость будетвполне приемлемой даже в том случае, когда исходная триангуляция с n вершинами содержит O(n) треугольников с недопустимыми ребрами.Для проверки корректности исходных данных икачества цифровой модели можно сравнить исходныеи расчетные горизонтали. Для этого необходимо построить триангуляцию с сильными ограничениями ина полученной поверхности рассчитать изолинии исходных (основных) и промежуточных уровней.
Овозможных пропусках линий, а также ошибках приопределении высот свидетельствуют:- «лишние» участки основных расчетных изолиний, которым не соответствуют исходные линии;- пересечения или касания расчетных изолиний,указывающие на наличие седловых точек поверхности;- слишком спрямленные промежуточные расчетные линии, форма которых должна соответствоватьформе двух соседних основных изолиний;- изолинии очень малого размера, построенные вокруг высотных отметок.При наличии существенных расхождений междуисходными и расчетными горизонталями может потребоваться корректировка исходных линий и/или ихвысот и перестроение модели рельефа.На рис. 5 приводятся исходные и расчетные изолинии участка местности, построенные на основетриангуляции с различными типами ограничений.Основные изолинии представлены сплошными, а дополнительные – штриховыми линиями, при этом исходные горизонтали выделены толстыми линиями.Для расчета линий строилась цифровая модель рельефа на основе триангуляции со слабыми (рис.
5, а) исильными (рис. 5, б) ограничениями. В последнемслучае также проводилось предварительное визуальное сглаживание исходных горизонталей.абРис. 5. Наборы исходных и расчетных изолиний участкарельефа: а – слабые, б – сильные ограничения триангуляцииРис. 5, а показывает, что если при построении ЦМРучитываются только обычные (слабые) ограничения, торасчетные изолинии могут оказаться совершенно непохожими на исходные. И только учет сильных ограничений позволяет получить приемлемые результаты.ЗАКЛЮЧЕНИЕПредложенный в статье новый тип сильных ограничений триангуляции позволяет более полно учитывать влияние горизонталей на форму рельефа. Эффективный алгоритм построения триангуляции с сильными ограничениями обеспечивает получение кондиционной цифровой модели рельефа в автоматическомрежиме.ЛИТЕРАТУРА1.2.3.4.Скворцов А.В.
Триангуляция Делоне и ее применение. Томск: Изд-во Том. ун-та, 2002. 128 с.Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. 478 с.Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 1989. 360 с.Костюк Ю.Л., Фукс А.Л. Предварительная обработка исходных данных для построения цифровой модели рельефа местности // ВестникТГУ. 2003. № 280. С. 281–285.Статья представлена кафедрой теоретических основ информатики факультета информатики Томского государственного университета, поступила в научную редакцию 15 мая 2003 г.289.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
