дві елєменти списку верхової суміжності.
Ємнісна складність цієї Структури S 1 (n) =4 | Е + п? 13, де | Е - Кількість ребер тріангуляції. При цьом, если списки суміжності зберігаються як двусвязний структури, то S l (і) =19n.
На рис. 3.2 приводитися приклад структури, заснованої на вершинах, для тріангуляції множини з 7 точок [37].
Структура, заснован на ТРИКУТНИК, кодує Т - V и Т - Т отношения суміжності ї містіть список трікутніків. Кожний елемент цього списку відповідає Деяк трикутнику t и містіть номери вершин трикутника t и номера трікутніків, суміжніх з t по ребру. Обоє ЦІ множини, вершин и трікутніків, упорядковуються в напрямку проти вартового стрілкі. Номер трикутника, розташованого напроти Першої вершини, вказується Першів. Ємнісна складність цієї Структури S n (n) =12 n .
засновання на ребрах Подання тріангуляції - MWER (modified winged-edge representation) - містіть три списки: ребер, вершин и трікутніків. Кожний елемент реберного списку, что відповідає Деяк ребру е, містіть номера двох вершин - кінців цього ребра, номери двох трікутніків, суміжніх по Цьом ребру, и номера двох ребер edge [0] и edge [l]. Если P 1 и Р 2 -вершиною ребра е , то edge [0] - це перше зустрінуте после е ребро тріангуляції при обертанні вокруг pi против вартового стрілкі; и edge [l] - це перше, зустрінуте после е ребро тріангуляції при обертанні вокруг Р 2 против вартового стрілкі.
У списку вершин для кожної вершини v i зберігається покажчик на перший з елементів реберного списку, у Який входити v i . У списку трікутніків для шкірного трикутника t зберігається покажчик на Деяк елемент реберного списку, у Який входити t . Таким чином, список вершин кодує частковий V - E відношення суміжності, список трікутніків кодує частковий Т - E відношення.
Делоне -тріангуляція
Делоне -тріангуляцією DT (V) множини V назівається граф, двоїчній діаграмі Вороного для V. Інакше Кажучи, це тріангуляція G (V, Е), для якої е=(v i , v j ) E тоді й только тоді, коли полігоні Вороного, відповідні v i , та v j , суміжні по ребру ( сусіди Вороного ). На схемі наведена Діаграма множини Вороного V для n =16 и двоїчна до неї Делоне-тріангуляція (рис. 3.3) [10].
ТРИКУТНИК Делоне-тріангуляції мают следующие Властивості: по-перше, окружність, описана вокруг будь-которого трикутника TR (v i , v j , v k ) , що не містіть усередіні собі точок з V; по-одному, мінімальній розмір кутів всех трікутніків максімізованій. Перша властівість назівається крітерієм кола (circle criterion). Друга властівість назівається крітерієм мінімаксу кута (МАХ-MIN angle criterion). Доведено, что обидвоє Критерії еквівалентні ї будь-який TR (v i , v j , v k ) є Делоне-трикутником (Належить Делоне-тріангуляції) тоді й только тоді, коли ВІН задовольняє крітерію кола.
Процедура локальної оптімізації LOP (local optimization) назівається наступна процедура. Нехай е - Внутрішнє ребро (на про...
