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

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

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

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

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

Структура даних

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

ПЗСР складається з трьох типів об'єктів; вершин, півребер і граней. Ці об'єкти головно містять «вказівники» на інші об'єкти. Це можуть бути вказівники 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

Посилання

• The DCEL Data Structure for 3D Graphics by Ryan Holmes
• The DCEL data structure: a C++ implementation