Представление ППЛГ Реберный список с двойными связями (РСДС)
массивы входов:
• по вершинам head_V [1..n]
• по граням head_F [1..l]
V
head_V
v1 1
v2 2
v3 4
v4 7
v5 6
F
head_F
f1 1
f2 2
f3 4
f4 7
06.04.2007 |
Геометрический поиск |
11 |
|
Локализация точки 2 |
|
Представление ППЛГ Реберный список с двойными связями (РСДС)
Процедура «Инцидентные ребра»
(см. файл MS Word «РеберныйСписокДС»)
06.04.2007 |
Геометрический поиск |
12 |
|
Локализация точки 2 |
|
Представление ППЛГ Реберный список с двойными связями (РСДС)
Процедура «Граница грани» (см. файл MS Word «РеберныйСписокДС»)
06.04.2007 |
Геометрический поиск |
13 |
|
Локализация точки 2 |
|
Метод цепей (продолжение)
Множество C = {C1, …, Cr } называется
полным множеством монотонных цепей графа, если:
r
1. C j G
j1
2.Для i, j 1..r (I j): те узлы из Ci ,, которые не являются узлами Cj,, лежат по одну сторону от Cj,.
06.04.2007 |
Геометрический поиск |
14 |
|
Локализация точки 2 |
|
Построение ПММЦ Балансировка весов ребер
1 |
1 |
1 |
|
|
|
1 |
1 |
1 |
|
||
|
|
2
1 1
11
1 |
1 |
|
1 |
1
1 1
3
2 1
2 1
06.04.2007 |
Геометрический поиск |
15 |
|
Локализация точки 2 |
|
Регуляризация графа Метод заметания
06.04.2007 |
Геометрический поиск |
16 |
|
Локализация точки 2 |
|
Метод детализации триангуляции
См. Документ MWord «Локализация точки» (п.1.3) в папке «Лекция 5»
06.04.2007 |
Геометрический поиск |
17 |
|
Локализация точки 2 |
|
Локализация точки
Метод трапеций (Зайделя) будет позже
Конец лекции
06.04.2007 |
Геометрический поиск |
18 |
|
Локализация точки 2 |
|