Подвійно зв'язаний список ребер

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Подвійно зв'язаний список ребер (англ. doubly connected edge list) або півреберна структура даних (англ. half-edge data structure) — це структура даних, що представляє вкладення планарного графу на площину або багатогранник у 3D. Ця структура даних забезпечує дієву маніпуляцію топологічною інформацією пов'язаною з об'єктами, що розглядаються (вершини, ребра, грані). Її використовують багато алгоритмів обчислювальної геометрії для обробки полігонального розбиття площини, часто згадуваних як планарні прямолінійні графи. Наприклад, діаграму Вороного зазвичай представляють як ПЗСР всередині обмежувального прямокутника.

Цю структуру даних вперше представили Мюллер і Препарата[1] для представлення тривимірного опуклого політопа.

Пізніше набули поширення змінені варіанти структури, але назва залишилась.

Звичайно структуру використовують для зв'язних графів, однак ПЗСР можна використовувати і для незв'язних графів також.

Структура даних[ред. | ред. код]

Кожне півребро має рівно одне попереднє півребро, одне наступне півребро і близнюка

ПЗСР складається з трьох типів об'єктів; вершин, півребер і граней. Ці об'єкти головно містять «вказівники» на інші об'єкти. Це можуть бути C/C++ вказівники, що містять адресу в пам'яті інших об'єктів або логічний індекс чи індекс у масиві, або інший тип адресації. Неодмінною властивістю є можливість прямого доступа до об'єкта на який посилаються, без пошуку.

Вершина[ред. | ред. код]

Вершина містить єдиний ПЗСР вказівник, який вказує на будь-яке півребро для якого ця вершина є початком.

Півребро[ред. | ред. код]

Півребро містить вказівник на вершину з якої воно починається, вказівник на грань і два вказівники на півребра, один на близнюка і один на наступне півребро. Вказівник на грань посилається на грань, що ліворуч від півребра, тоді як вказівник на півребро близнюка посилається на правий бік ребра, який доповнює його до цілого ребра.

Грань[ред. | ред. код]

Грань містить єдиний вказівник на будь-яке півребро, що посилається на цю грань.

Примітки[ред. | ред. код]

  1. Muller, D. E. ; Preparata, F. P. «Finding the Intersection of Two Convex Polyhedra», Tech. Rept. UIUC, 1977, 38pp, also Theoretical Computer Science", Vol. 7, 1978, 217—236

Посилання[ред. | ред. код]