оторого Е - це максимальна підмножіна в Р, таке, что Ніякі два ребра з Е НЕ перетінаються.
Будь-яка планарная тріангуляція множини В з и крапок, п b з якіх належати границі опуклої Оболонков множини V, має 2 (і - 1) - п b трікутніків и 3 (п - 1 ) - п b ребер.
Тріангуляція множини точок у пространстве
Нехай Р - множини з п крапок у пространстве Е , де d - розмірність простору. Р назівається множини в загально положенні, если розмірність лінійного простору, натягнутого на будь-яку его підмножіну з (d + 1) крапок , дорівнює d. Симплексом назівається опукла оболонка множини з (d + 1) -ої точки в загально положенні. Тріангуляцією множини Р назівається розбівка внутрішності опуклої Оболонков Р на симплекс, вершинами якіх є крапки з Р.
Для трівімірного простору тріангуляція множини Р - це розбівка опуклої Оболонков, СН (Р), на тетраедрі так, что Р містіть Чотири вершини шкірного тетраедра й Не містіть Ніякі Інші его крапки, и перетінання будь-якіх двох тетраедрів або порожнє, або є їхньою загальною гранню (Термін грань тут Варто розуміті в узагальненому змісті, як опуклу Оболонков підмножіні вершин тетраедра; таким чином, грань может буті вершиною, ребром, трикутником).
Структури Подання тріангуляції поверхні
Між переважно про єктами, что визначаються будь-яку тріангуляцію поверхні - вершинами, ребрами й ТРИКУТНИК - может буті Визначи 9 МОЖЛИВИЙ отношений взаємної суміжності, як показано на схемі (рис. 3.1), де Кожна стрілка позначає впорядкованим відношення между парою про єктів, V - вершини, Е -ребра, T -трікутнікі [37].
Кожне ребро тріангуляції однозначно візначається двома своими кінцямі, шкірні двовімірна грань обмежена трьома ребрами й трьома вершинами. Структура даних для кодування тріангуляції звічайна містіть список основних об'єктів - Одне або немного Із множини Е, V, Т - и Деяка множини отношений суміжності.
Рис.3.1
Складність Структури даних, что представляет розбівка поверхні, підрозділяється на ємнісну ї тимчасову складність. Ємнісна складність оцінюється пам'яттю, необхідної для зберігання закодованіх отношений суміжності. Тимчасова складність Структури даних оцінюється складністю алгоритмів, Які могут відновіті з даної Структури неявно закодовані в ній отношения суміжності.
известно, что Кожне з п'яти отношений взаємної суміжності VE, EE, TE, VV и TV й достатньо для однозначного Подання плоскої тріангуляції. Найбільше часто для кодування тріангуляції вікорістаються структури, засновані на вершинах (vertex-based) i структури, засновані на ТРИКУТНИК. Vertex застосвуються у ГІС Arc Info и зберігаються при вікорістанні файлів * .e00.
Структура, заснован на вершинах, кодує VV відношення суміжності ї містіть дві списки: список верхової суміжності й список вершин, у якому для кожної вершини v, утрімується покажчик на елемент списку верхової суміжності, з которого почінається подсписок суміжності вершини V i. Список суміжності складається з" ?? ідспісків суміжності вершин, розташованіх один за одним у порядку зростання номерів вершин. Кожний елемент списку суміжності вершини v i відповідає ребру тріангуляції v i , v j . Перше поле в запісі цього ребра - номер вершини v i , друге поле - покажчик на елемент структури, что відповідає ребру тріангуляції v i , v k , что віпліває за ребром v i , v j , при обході вокруг вершини v i , проти вартового стрілкі. Кожному ребру тріангуляції відповідають...
