Чотириреберні сітки
Чотиригранна структура даних — це комп'ютерне представлення топологічного двовимірної або тривимірного відображення, тобто графіка, накресленого на (закритій) поверхні. Вперше його описали Хорхе Столфі[en] та Леонідас Гюйбас[en].[1] Це варіант попередньої структури даних «крилатого» ребра.
Огляд ред.
Фундаментальна ідея структури з чотирма ребрами полягає в тому, що одне ребро в закритій полігональній топології сітки розташоване рівно між двома гранями і двома вершинами. Структура даних з чотирма ребрами являє собою ребро разом з іншими ребрами, з якими воно пов'язане навколо суміжних вершин і граней для кодування топології графа. Нижче наведено приклад реалізації чотиригранного типу даних
typedef struct {
quadedge_ref e[4];
} quadedge;
typedef struct {
quadedge *next;
unsigned int rot;
} quadedge_ref;
Кожна чотиригранне ребро містить чотири посилання на сусідні чотиригранні ребра. Кожне з чотирьох посилань вказує на наступне ребро проти годинникової стрілки навколо вершини або грані. Кожне з цих посилань представляє вихідну вершину ребра, праву грань, кінцеву вершину або ліву грань. Кожна чотиригранна опорна точка вказує на чотиригранну дугу, а обертання (від 0 до 3) «руки», на яку вона вказує.
Завдяки такому представленню чотиригранник:
- представляє граф, його двоїстий граф і дзеркальне відображення.
- Двоїстий граф можна отримати, просто змінивши умову щодо того, що є вершиною, а що є гранню.
- може представляти найбільш загальну форму відображення, що допускає вершини і грані ступеня 1 і 2.
Подробиці ред.
Чотиригранна структура отримала свою назву від загального механізму, за допомогою якого вони зберігаються. Одна структура Edge концептуально зберігає посилання до двох граней, двох вершин і 4 ребер. Чотири збережені ребра — це ребра, які починаються з двох вершин, які приєднані до двох збережених граней.
Застосування ред.
Подібно до «крилатого» ребра, чотиригранні структури використовуються в програмах для зберігання топології 2D або 3D полігональної сітки . Саму сітку не потрібно приховувати, щоб сформувати дійсну чотиригранну структуру.
Використовуючи чотиригранну структуру, ітерація по топології досить проста. Часто інтерфейс до топологій чотирьох країв здійснюється через спрямовані ребра. Це дозволяє двом вершинам мати явні назви (початок і кінець), і це дає граням явні імена (ліворуч і праворуч, відносно людини, яка стоїть на початку і дивиться в напрямку кінця). Чотири ребра також мають назви на основі вершин і граней: початок-лівий, початок-правий, кінець-лівий і кінець-правий. Спрямоване ребро можна повернути, щоб створити ребро в протилежному напрямку.
Ітерація навколо певної грані треба лише одного спрямоване ребро, до якого ця грань знаходиться зліва (за згодою), а потім проходження через усі початкові ліві ребра, поки не буде досягнуто вихідне ребро.
Див. також ред.
Примітки ред.
- ↑ Stolfi, Jorge; Guibas, Leonidas J. (April 1985). Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics. 4 (2): 74‒169. doi:10.1145/282918.282923.
Посилання ред.
- https://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html A quad-edge implementation in C++.
- http://www.ic.unicamp.br/~stolfi/EXPORT/software/c/2000-05-04/libquad/ A quad-edge implementation in C.