Триангуляция Делоне Определение, применение, свойства, методы построения. - презентация

1 Триангуляция Делоне Определение, применение, свойства, методы построения

2 Структура лекции Определения Определения Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

3 Литература по теме Скворцов А.В. Триангуляция Делоне и её применение. Скворцов А.В. Триангуляция Делоне и её применение. Майкл Ласло «ВГ и компьютерная графика на С++» (п.6.6). Майкл Ласло «ВГ и компьютерная графика на С++» (п.6.6).

4 Триангуляция Триангуляция – планарный граф все внутренние области которого являются треугольниками. Триангуляция – планарный граф все внутренние области которого являются треугольниками. Термин «Триангуляция» - это Термин «Триангуляция» - это граф; граф; процесс построения графа. процесс построения графа. Задача триангуляции набора точек S – задача соединения всех точек набора S непересекающимися отрезками для получения графа триангуляции. Задача триангуляции набора точек S – задача соединения всех точек набора S непересекающимися отрезками для получения графа триангуляции. Определение триангуляции Набор точек S

5 Оптимальная триангуляция – триангуляция с минимальной суммой длин всех ребер графа. Оптимальная триангуляция – триангуляция с минимальной суммой длин всех ребер графа. ! Востребованная, но очень трудоемкая задача O(2 n ) ! На практике используют аппроксимации (приближения к) оптимальной триангуляции: «Жадная» триангуляция O(N 2 *logN) «Жадная» триангуляция O(N 2 *logN) Триангуляция Делоне O(N*logN) Триангуляция Делоне O(N*logN) Определение оптимальной триангуляции

6 Триангуляция Делоне (DT(S)) – выпуклая триангуляция удовлетворяющая условию Делоне: Триангуляция Делоне (DT(S)) – выпуклая триангуляция удовлетворяющая условию Делоне: внутрь окружности описанной вокруг любого ее треугольника недолжна попадать ни одна из вершин графа. внутрь окружности описанной вокруг любого ее треугольника недолжна попадать ни одна из вершин графа. Определение триангуляции Делоне У словие Делоне выполняется У словие Делоне не выполняется Б.Н. Делоне ( )

7 Применение триангуляции Делоне В других задачах ВГ В других задачах ВГ Минимальный остов набора точек Минимальный остов набора точек Построение буферных зон Построение буферных зон Построение диаграммы Вороного (зон близости) Построение диаграммы Вороного (зон близости) Нахождение максимальной пустой окружности Нахождение максимальной пустой окружности и др. и др. В приложениях в КГ, ГИС, ГМ в САПР В приложениях в КГ, ГИС, ГМ в САПР Полигональные модели поверхностей Полигональные модели поверхностей Рельефы в ГИС, скульптуры, пром.модели, модели в играх, Рельефы в ГИС, скульптуры, пром.модели, модели в играх, Численный анализ моделей Численный анализ моделей Изолинии, Изоклины, МКЭ. Изолинии, Изоклины, МКЭ.

8 Построение минимального остова набора точек и буферных зон на основе триангуляции Делоне

9 Представление и анализ рельефов местности в ГИС-системах на основе триангуляции Делоне

10

11 Свойства любой выпуклой триангуляции 1. Для набора n точек из которых m - внутренние Количество треугольников триангуляции = n + m – 2 Количество треугольников триангуляции = n + m – 2 Количество ребер триангуляции 3n – 6 Количество ребер триангуляции 3n – 6Пример: Точек (n) – 13 Точек (n) – 13 Внутренних (m) – 4 Внутренних (m) – 4 Треугольников – 15 = Треугольников – 15 = Ребер – 26 3*13-6 = 33 Ребер – 26 3*13-6 = 33

12 Свойства триангуляции Делоне 2. Триангуляция Делоне обладает максимальной суммой минимальных углов всех треугольников среди всех возможных триангуляций. 3. Триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций. Триангуляция Делоне НЕ триангуляция Делоне

13 Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Итеративные алгоритмы ( ) Итеративные алгоритмы ( ) Методы пошаговой выборки Методы пошаговой выборки Алгоритмы прямого (пошагового) построения (3) Алгоритмы прямого (пошагового) построения (3) Методы декомпозиции Методы декомпозиции Алгоритмы слияния (2) Алгоритмы слияния (2) Методы сканирования Методы сканирования Итеративные алгоритмы с измененным порядком добавления точек (1.4) Итеративные алгоритмы с измененным порядком добавления точек (1.4) Двухпроходные алгоритмы (4) Двухпроходные алгоритмы (4)

14 Методы пошагового ввода Итеративные алгоритмы ( ) Общая схема итеративных алгоритмов построения триангуляции Делоне 1. На первых трех точках построить один треугольник 2. Цикл по всем оставшимся точкам p i набора S 3. Найти ближайший к точке p i треугольник t j текущей триангуляции 4. Если точка p i снаружи треугольника t j, то построить треугольники к ближайшему ребру. 5. Если точка p i внутри треугольника t j, то разбить треугольник на три. 6. Если точка p i на ребре, то разбить прилегающие треугольники на пары. 7. Если условие Делоне для соседей нарушилось, то перестроить соседние треугольники. Варианты ускорения поиска треугольников: Индексирование треугольников (деревья) – O(log n) Индексирование треугольников (деревья) – O(log n) Кэширование треугольников (сетки) – O(с) Кэширование треугольников (сетки) – O(с)

15 Методы пошаговой выборки Алгоритмы прямого (пошагового) построения (3) Строить сразу нужные треугольники, не перестраивая что уже построено. Общая схема алгоритмов прямого построения триангуляции Делоне Удобно использовать стек еще необработанных ребер. 1. Найти любое ребро q выпуклой оболочки набора точек S. 2. Занести ребро q в стек необработанных ребер. 3. Цикл пока стек необработанных ребер не пуст. 4. Извлечь ребро v из стека. 5. Для ребра v найти точку p, удовлетворяющую условию Делоне (соседа Делоне) 6. Если сосед Делоне p найден, то 7. Построить треугольник от ребра v к точке p. 8. Занести новые ребра нового треугольника в стек необработанных ребер. Варианты ускорения поиска соседа Делоне: Индексирование точек k-D-деревом – O(log n) Индексирование точек k-D-деревом – O(log n) Клеточное индексирование точек – O(с) Клеточное индексирование точек – O(с)

16 Процесс работы жадного алгоритма триангуляции Делоне

17 Методы декомпозиции Алгоритмы слияния (2) Разбиение на подмножества, независимая обработка, слияние результатов. Общая схема алгоритмов слияния 0. Если точек в наборе S не более 3 шт, построить непосредственно иначе 1. Разбить набор точек S на примерно равные подмножества. 1. Разбить набор точек S на примерно равные подмножества. 2. Построение триангуляции для подмножеств. 2. Построение триангуляции для подмножеств. 3. Слияние полученных триангуляций в одну. 3. Слияние полученных триангуляций в одну. Способы разделения на подмножества Ортогональными прямыми Ортогональными прямыми По диаметру выпуклой оболочки По диаметру выпуклой оболочки Полосами Полосами

18 Алгоритмы слияния (2) Способы слияния триангуляций «Удаляй и строй» (проверка до построения) «Удаляй и строй» (проверка до построения) «Строи и перестраивай» (проверка после построения) «Строи и перестраивай» (проверка после построения) «Строй, перестраивая» (проверка во время построения) «Строй, перестраивая» (проверка во время построения)

19 Общая схема итеративных методов с измененным порядком добавления точек 1. Упорядочить точки (построить перечень точек событий) 2. Цикл сканирования по всем точкам-событиям 3. Для каждой точки p i построить треугольники к предыдущему треугольнику. 4. Если условие Делоне для соседей нарушилось, то перестроить соседние треугольники. Методы сканирования Итеративные алгоритмы с измененным порядком добавления точек (1.4)

20 Методы сканирования Способы упорядочивания точек событий Прямолинейное Прямолинейное Полярное (круговое, веерообразное) Полярное (круговое, веерообразное) Полосовое Полосовое Квадратное Квадратное По кривой Гильберта По кривой Гильберта По Z-коду По Z-коду Цели: Сразу строить максимум хороших треугольников Сразу строить максимум хороших треугольников Минимизировать число перестроений Минимизировать число перестроений

21 Двухпроходные алгоритмы (4) Общая схема двухпроходных алгоритмов 1. Построить хоть какую-нибудь выпуклую триангуляцию. 2. Перестроить «неправильные треугольники» (неудовлетворяющие условию Делоне).

22 Сводные характеристики методов триангуляции Делоне Метод триангуляции Время в среднем Время в худшем Время сек / т Простотареализац. Методы пошагового ввода Методы пошагового ввода Итеративные алгоритмы ( ) Итеративные алгоритмы ( )O(n)- O(n 3/2 ) O(n 2 ) 1,5-9,2 2-5 Методы пошаговой выборки Методы пошаговой выборки Метод прямого построения (3) Метод прямого построения (3) O(n)- O(n 2 ) O(n 2 ) -2 Методы декомпозиции Методы декомпозиции Методы слияния (2) Методы слияния (2) O(n)- O(nlogn) O(nlogn)- O(n 2 ) 2,5-4,52-3 Методы сканирования Методы сканирования Итеративные с измененным порядком добавления точек (1.4) Итеративные с измененным порядком добавления точек (1.4)O(n) O(n 2 ) 1,9-5,34-5 Двухпроходные методы (4) Двухпроходные методы (4) O(n)- O(n 2 ) O(nlogn)- O(n 2 ) 2,2-15,41-5 Скворцов рекомендует: итеративный алгоритм с динамическим кэшированием

23 А сегодня о чем? О триангуляции Делоне! Определение Определение Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

24 А если чет непонятно, вам туда Скворцов А.В. Триангуляция Делоне и её применение. Скворцов А.В. Триангуляция Делоне и её применение. Майкл Ласло «ВГ и компьютерная графика на С++» (п.6.6). Майкл Ласло «ВГ и компьютерная графика на С++» (п.6.6).

25 Спасибо за внимание!! …тем кто смог не уснуть. (: