4.4. Цифровое и математическое моделирование местности

4.4.1. Формирование рельефа и ситуации

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

Таким образом, для построения рельефа и ситуации зоны проектирования формируются следующие исходные данные:

• точки, имеющие имя (Name), координаты (x, y, z), коды условных знаков, коды принадлежностей их к линиям и контурам;
• структурные линии, вдоль которых имеет место нарушение гладкости поверхности (линии обрывов, водоразделы, тальвеги, границы рек, озер, искусственных сооружений и пр.);
• ситуационные линии и контуры – данные о местности, такие как расположение лесов, рек, озер, дорог, домов и пр.

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

Поскольку в реальных проектах сложных сооружений инженер имеет дело с массивами размерностью в десятки и сотни тысяч точек, то, естественно, что современные САПР должны обладать развитыми средствами их визуального редактирования. В режиме редактирования точек, как правило, предусматривают контекстное меню. Состав команд контекстного меню зависит от количества и типа выделенных точек.

Приведем лишь несколько команд по редактированию точек.

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

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

Выделить все линии, относящиеся к точке. Выделяет все линии, проходящие через выделенную точку. Команда недоступна, если выделено несколько точек.

Копировать в слой. Копирует или перемещает выделенные точки в указанный слой.

Ситуационная/Структурная. Определяет статус точки.

Знаки… Назначение знаков выделенным точкам.

Структурные линии строят строго по рельефным точкам и по своей сути они являются трехмерными ломаными линиями (рис. 4.6, б). Следует отметить, что структурные линии не могут пересекаться, но могут примыкать друг к другу. Структурные линии могут оказывать существенное влияние на очертания поверхностей. Это их свойство будет более подробно рассмотрено в разд. 4.4.3.

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

Как ситуационные, так и структурные линии имеют атрибуты цвета, толщины и стиля. Контуры имеют атрибуты заливки цветом или текстурой (условными знаками).

Рис. 4.6. Исходные данные для построения рельефа и ситуации:
а) массив точек; б) структурные линии; в) ситуационные линии и контуры

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

4.4.2. Триангуляция Делоне и способы ее редактирования

Для моделирования поверхностей существуют различные виды структур: по горизонталям, по структурным линиям, по поперечникам к трассе или магистральному ходу, статистические [26]. На практике чаще всего используют два основных вида структур: регулярная (равномерная прямоугольная, рис. 4.7, а) и нерегулярная (триангуляционная, рис. 4.7, б).

Массив точек для регулярных моделей может быть представлен в следующем виде:

F, m, n, X₀, Y₀, Z₁₁,…, Z_1m,…, Z_nm,

где F – шаг сетки; m – число точек по горизонтали; n – число точек по вертикали; X₀, Y₀ – координаты начальной точки сетки, Z₁₁,…, Z_1m,,…, Z_nm – отметки точек в узлах сетки.

Таким образом, для однозначного представления регулярной сетки размерностью m´n требуется хранить всего m´n+5 чисел. Однако для адекватного представления поверхности с заданной точностью требуется высокая плотность точек, что сопряжено со значительной многодельностью работ по подготовке исходной информации. К тому же, в виду ограниченности быстродействия компьютеров и массивов обрабатываемых данных приходится выбирать между точностью представления (размером ячейки) и размером обрабатываемой поверхности.

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

SX_i, Y_i, Z_i, T_i, R_i, L_i,

где X_i, Y_i, Z_i – координаты i-той точки (массив i = 1,…,k); T_i, R_i, L_i – соответственно принадлежность i-той точки T_i треугольнику, связь i-той точки с R_i и L_i точками в треугольнике.

Размерность нерегулярной сетки составляет 6k, что почти в 6 раз выше размерности регулярной сетки, но, в тоже время, для адекватного отображения поверхности требуется существенно меньшее количество точек.

Задача построения поверхности способом триангуляции является одной из базовых в вычислительной геометрии. К ней сводятся многие другие, связанные с моделированием поверхностей и решением пространственных задач в машинной графике, системах автоматизированного проектирования и геоинформационных системах.

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

Рассмотрим некоторые алгоритмы построения триангуляции.

Например, триангуляция Делоне, названная в честь советского математика Б. Н. Делоне (1934 г., [10])основана на ряде практических свойств:

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

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

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

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

· Генерируется список всех возможных отрезков (рис. 4.9, а), соединяющих пары исходных точек, и он сортируется по длинам отрезков.

· Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе – отбрасывается (рис. 4.9, б).

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

Трудоемкость работы жадного алгоритма составляет N²logN , где N – число точек в массиве. В связи со столь большой трудоемкостью на практике этот алгоритм применяется редко.

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

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

Приведем лишь некоторые из возможных операций.

• Треугольник ® узлы: требуется для получения высотной отметки проектной точки, расположенной внутри конкретного треугольника. Для этого устанавливаются координаты узлов этого треугольника, а далее в уравнение плоскости, проходящей через эти три узла, подставляются координаты x,y проектной точки.
• Узел ® ребра: требуется для анализа водоотвода на рассматриваемой поверхности. По узлу устанавливается список всех смежных ребер, каждое из которых анализируется на возможность "перелива" воды.
• Треугольник ® треугольник: требуется для построения изолиний рассматриваемой поверхности. По треугольнику устанавливается список соседних с ним треугольников и на них вычисляется геометрическое место точек с заданной высотной отметкой.

4.4.3. Анализ рельефа (поверхностей)

Одной из базовых задач анализа триангуляционных поверхностей является построение разрезов: вертикальных (профилей) и горизонтальных (изолиний).

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

Изолиниями называют линии пересечения горизонтальных плоскостей уровня h с триангуляционной поверхностью.

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

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

Алгоритм построения изолиний состоит из двух шагов:

• Помечаем каждый треугольник триангуляции, по которому проходит изолинии, то есть выполняется условие min(z₁, z₂, z₃) < h < max(z₁, z₂, z₃), где z_i– высоты трех его вершин.
• Для каждого такого треугольника выполняем отслеживание такой изолинии в обе стороны от данного треугольника, пока один конец не выйдет на другой или на границу триангуляции.

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

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

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

Более наглядным отображением поверхности, по сравнению с изолиниями, является ее отображение изоконтурами, которые по природе построения близки к изолиниям. Особенно наглядным будет представление поверхности изоконтурами в цветовом спектре, которое позволяет быстро выявлять на поверхности пониженные (повышенные) места, тальвеги, водоразделы, седловины и пр.

Изоконтурами между уровнями h₁ и h₂ называется геометрическое место точек на поверхности, имеющих высоту hє(h₁, h₂).

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

Естественно, что, в зависимости от положения источника света и экспозиции элементарного участка поверхности (треугольника) одни участки поверхности будут темнее (или светлее), чем другие.

На рис. 4.13, а приведен участок поверхности, освещаемый источником света, расположенным на северо-западе; а на рис. 4.13, б приведен участок поверхности, освещаемый с юго-востока.

Как видно из рис. 4.13, данная поверхность представляет собой фрагмент дороги с примыканием. Однако контуры откосов построены с некоторыми нарушениями. Их можно скорректировать, если провести структурные линии по кромкам, бровкам дороги и подошвам откосов насыпи (рис. 4.14, а)

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

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

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

• Среди всех вершин триангуляции находятся те, которые ниже, чем все смежные вершины (две вершины являются смежными, если они соединены ребром). Таким образом, все найденные вершины являются "чашами" – местами, где будут собираться лужи на местности.
• Наполняем каждую чашу водой и находим лужи. Для этого передвигаемся от вершины в центре каждой чаши в разные стороны по рёбрам к другим вершинам до тех пор, пока какое-то ребро не перегнётся, т.е. пока мы не найдем вершину – точку перегиба поверхности. Эти точки перегиба обладают свойством, что если лужа переполнится, то через эту точку вода будет выливаться из лужи. Среди всех точек перегиба мы выбираем ту, которая имеет меньшую высоту, и на основании этого мы сможем определять емкость лужи.
• Если образовались мелкие лужи, то производиться их проверка на слияние.

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

• Строят лучи, исходящие из точки наблюдателя в разные стороны.
• Строят профили поверхностей вдоль этих лучей.
• Методом плавающего горизонта формируются видимые и невидимые части этих профилей.

Расчет объемов земляных работ при традиционном (ручном) проектировании автомобильных дорог выполняют, как правило, на основе поперечных профилей. Однако этот подход не является ни универсальным, ни наиболее точным.

На участках примыканий, пересечений дорог, транспортных развязок расчет объемов земляных работ можно выполнить по схеме вычитания объемов поверхностей (проектной и исходной). Эта задача не является тривиальной, поскольку исходная и проектная поверхности могут сколько угодно раз взаимно пересекаться, порождая зоны срезки (выемки) и засыпки (насыпи) грунта.

Алгоритм расчет объемов земляных работ как разности двух поверхностей состоит из следующих шагов:

Определяется минимальный многоугольник, охватывающий триангуляции исходную (Т1) и проектную (Т2) как пересечение охватываемых триангуляцией территорий.

Создается новая триангуляция Т и в нее вносятся в качестве структурных ребер все ребра триангуляции Т1 и Т2. Для каждого узла триангуляции Т нужно вычислить его высоты в триангуляциях Т1 и Т2 соответственно.

Для каждого треугольника новой триангуляции определяют, не пересекаются ли триангуляции Т1 и Т2 в пределах этого треугольника:

• если высоты треугольника в триангуляции Т2 выше, чем в триангуляции Т1 , то это – зона насыпи;
• если высоты треугольника в триангуляции Т2 ниже, чем в триангуляции Т1 , то это – зона выемки;
• если высоты треугольника в триангуляции Т2 те же, что и в триангуляции Т1 , то это – зона нулевых работ;
• если одна (или две) высота треугольника в триангуляции Т2 выше, чем в триангуляции Т1, а две (или одна) другие ниже, то поверхности пересекаются в пределах данного треугольника. Необходимо найти пересечение двух пространственных треугольников в виде некоторого отрезка, разделяющего треугольник на 2 части, которые в дальнейшем войдут в разные результирующие зоны: насыпи и выемки.
• Суммируются объемы насыпей и выемок.

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