Структура данных quad-edge — это компьютерное представление топологии двухмерной или трёхмерной карты, то есть графа нарисованного на (замкнутой) поверхности. Впервые её описали Жоржи Столфи и . Это вариант более ранней структуры данных «крылатое ребро».
Обзор
Основная идея структуры «quad-edge» заключается в том, что в топологии замкнутой полигональной сетки каждое отдельное ребро находится ровно между двумя гранями и ровно между двумя вершинами.
Структура данных «quad-edge» представляет ребро вместе с рёбрами, к которым оно присоединено вокруг смежных вершин и граней, чтобы закодировать топологию графа. Пример реализации типа данных «quad-edge» выглядит следующим образом:
typedef struct { quadedge_ref e; } quadedge;
typedef struct { quadedge *next; unsigned int rot; } quadedge_ref;
Каждая структура «quad-edge» содержит четыре ссылки на структуры «quad-edge» смежных рёбер. Каждая из этих четырёх ссылок указывает на следующее ребро против часовой стрелки либо относительно вершины, либо относительно грани. Каждая из этих ссылок представляет либо исходную вершину ребра, либо левую грань, либо конечную вершину, либо правую грань. (Если принять исходное ребро за исходное направление, то поворот против часовой стрелки на 90 градусов укажет на левую грань, следующий поворот ляжет на то же ребро, но в противоположном направлении и, наконец, третий поворот укажет на правую грань). Каждая ссылка содержит указатель и направление (от 0 до 3).
Благодаря такому представлению структура: представляет граф, его двойственный граф и его зеркальное отображение. двойственный граф может быть получен простым изменением соглашения о том, что является вершиной, а что — гранью может представлять наиболее общую форму карты, допуская вершины и грани степени 1 и 2.
Основное преимущество структуры данных «Quad-Edge» заключается в том, что всё построение и модификация плоских графов могут быть выполнены с помощью двух базовых топологических операторов, а более сложные топологические операции строятся на основе этих двух: – MakeEdge[] создает ребро в новой структуре данных, представляющей пустое многообразие. – Splice[a,b] соединяет или разделяет два кольца рёбер, а также, независимо, два двойственных кольца рёбер.
Использование
Подобно структуре данных «крылатое ребро» структуры «quad-edge» используются в программах для хранения топологии двухмерной или трёхмерной полигональной сетки. Сама сетка не обязательно должна быть замкнутой, чтобы сформировать правильную структуру «quad-edge».
Использование структуры «quad-edge» значительно упрощает итерацию по топологии. Часто интерфейс к топологиям «quad-edge» осуществляется через направленные рёбра. Это позволяет двум вершинам иметь явные имена (начало и конец), а также даёт явные имена граням (левая и правая, относительно человека, стоящего в начале и смотрящего в направлении конца). Четырём рёбрам также даются имена, основанные на вершинах и гранях: начало-лево, начало-право, конец-лево и конец-право. Направленное ребро можно обратить, чтобы получить ребро в противоположном направлении.
Итерация вокруг конкретной грани требует лишь наличия одного направленного ребра, для которого эта грань находится слева (по соглашению), а затем прохода по всем рёбрам «начало-лево», пока не будет достигнуто исходное ребро.
См. также Крылатое ребро
Двусвязный список рёбер
Примечания
Литература Другая ссылка]
Ссылки 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.
Категория:САПР Категория:Структуры данных компьютерной графики