2.12 Системы автоматизированного проектирования автодорог
1.Триангуляция Делоне. Принцип и порядок построения.
В современных программных продуктах для выполнения триангуляции используют алгоритм, предложенный российским ученым Б.Н. Делоне. Сущность алгоритма триангуляции заключается в следующем. В произвольное место горизонтальной проекции поверхности помещают окружность малого радиуса таким образом, чтобы ни одна съемочная точка не попала внутрь окружности. Затем увеличивают радиус окружности, не передвигая ее центра до тех пор, пока она не наткнется на некоторые съемочные точки. Далее, сохраняя то условие, чтобы точки лежали на границе окружности, увеличивают ее радиус и одновременно отодвигают ее центр. Этот процесс продолжают до тех пор, пока окружность не коснется, как минимум, трех точек. Дальнейшее увеличение радиуса становится невозможным, а найденные три точки образуют первый треугольник. Взяв две точки полученного треугольника, строят новую окружность на образовавшемся ребре и увеличивают ее радиус одновременно с перемещением центра в сторону, противоположную третьей вершине треугольника, до тех пор, пока окружность не коснется следующей точки. Таким путем образуется еще один треугольник. Процесс повторяют до тех пор, пока все точки поверхности не будут охвачены треугольной сетью. Поверхности внутри каждого треугольника, вершинами которого являются точки с известными координатами x, y, z представляет собой плоскость. Высотная отметка z любой точки с координатами x, y в плане, находящейся внутри треугольника определяется по формуле: z=Ax + By + C, где A, B, C - коэффициенты уравнения плоскости, построенной по трем точкам, образующих треугольник.
Триангуляция Делоне и способы ее редактирования
Массив точек для регулярных моделей может быть представлен в следующем виде:
F, m, n, X0, Y0, Z11,…, Z1m,…, Znm,
где F – шаг сетки; m – число точек по горизонтали; n – число точек по вертикали; X0, Y0 – координаты начальной точки сетки, Z11,…, Z1m,,…, Znm – отметки точек в узлах сетки.
Таким образом, для однозначного представления регулярной сетки размерностью mn требуется хранить всего mn+5 чисел. Однако для адекватного представления поверхности с заданной точностью требуется высокая плотность точек, что сопряжено со значительной многодельностью работ по подготовке исходной информации. К тому же, в виду ограниченности быстродействия компьютеров и массивов обрабатываемых данных приходится выбирать между точностью представления (размером ячейки) и размером обрабатываемой поверхности.
Для нерегулярных моделей массив точек описывается последовательностью:
Xi, Yi, Zi, Ti, Ri, Li,
где Xi, Yi, Zi – координаты i-той точки (массив i = 1,…,k); Ti, Ri, Li – соответственно принадлежность i-той точки Ti треугольнику, связь i-той точки с Ri и Li точками в треугольнике.
Размерность нерегулярной сетки составляет 6k, что почти в 6 раз выше размерности регулярной сетки, но, в тоже время, для адекватного отображения поверхности требуется существенно меньшее количество точек.
Задача построения поверхности способом триангуляции является одной из базовых в вычислительной геометрии. К ней сводятся многие другие, связанные с моделированием поверхностей и решением пространственных задач в машинной графике, системах автоматизированного проектирования и геоинформационных системах.
Задачей построения триангуляции по заданному набору точек называется задача соединения точек непересекающимися отрезками так, чтобы образовалась триангуляция. Эта задача не является однозначной, поэтому возникает вопрос, какая из двух различных триангуляций лучше (оптимальна)?
Рассмотрим некоторые алгоритмы построения триангуляции.
Триангуляция Делоне, названная в честь советского математика Б. Н. Делоне (1934 г.), основана на ряде практических свойств:
триангуляция, удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции;
пара соседних треугольников триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этих двух треугольников;
триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трех его соседей (если они существуют).
триангуляция Делоне обладает максимальной суммой минимальных углов всех своих треугольников среди всех возможных триангуляций;
триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций.
Триангуляцию Делоне можно получить из любой другой триангуляции по тому же массиву точек, последовательно перестраивая пары соседних треугольников СABC и DBCD, не удовлетворяющих свойствам Делоне, в пары треугольников DABD и DACD (рис. 4.8). Такую операцию называют флип.
Рис. 4.8. Перестроение треугольников (флип)
Важно, что операцию флип можно применять не только в составе алгоритма построения оптимальной триангуляции поверхности, но и в составе инструментов диалогового ее редактирования, что позволяет получать желаемые для проектировщика свойства этой поверхности.
Другим алгоритмом, который достаточно просто и наглядно демонстрирует последовательность построения оптимальной триангуляции, является жадный алгоритм. В качестве условия оптимизации здесь принята минимальная сумма длин всех ребер среди всех возможных триангуляций, построенных на тех же исходных точках. Этот алгоритм выполняется всего в 2 шага.
Генерируется список всех возможных отрезков (рис.а), соединяющих пары исходных точек, и он сортируется по длинам отрезков.
Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе – отбрасывается (рис.б).
В триангуляции можно выделить 3 основных вида объектов: узлы (точки, вершины), ребра (отрезки) и треугольники. В процессе выполнения конкретных проектных задач возникает необходимость выполнения вычислительных операций с этими объектами. Приведем лишь некоторые из возможных операций.
Треугольник узлы: требуется для получения высотной отметки проектной точки, расположенной внутри конкретного треугольника. Для этого устанавливаются координаты узлов (вершин) этого треугольника, а далее - в уравнение плоскости, проходящей через эти три узла, подставляются координаты x,y проектной точки.
Узел ребра: требуется для анализа водоотвода на рассматриваемой поверхности. По узлу устанавливается список всех смежных ребер, каждое из которых анализируется на возможность "перелива" воды.
Треугольник треугольник: требуется для построения изолиний рассматриваемой поверхности. По треугольнику устанавливается список соседних с ним треугольников и на них вычисляется геометрическое место точек с заданной высотной отметкой.