Четырехгранный

Структура с четырьмя ребрами данных — это компьютерное представление топологии двумерной или ) трехмерной карты , то есть графа , нарисованного на (замкнутой поверхности . Впервые он был описан Хорхе Столфи и Леонидасом Дж. Гибасом . ^[1] Это вариант более ранней структуры данных с крылатым краем .

Обзор

Фундаментальная идея, лежащая в основе структуры четырех ребер, заключается в признании того, что одно ребро в топологии замкнутой многоугольной сетки находится ровно между двумя гранями и ровно двумя вершинами.

Структура данных с четырьмя ребрами представляет собой ребро вместе с ребрами, с которыми оно соединено вокруг соседних вершин и граней, для кодирования топологии графа. Пример реализации типа данных Quad-Edge выглядит следующим образом.

typedef struct {
  quadedge_ref e[4];
} quadedge;

typedef struct {
  quadedge *next;
  unsigned int rot;
} quadedge_ref;

Каждое четырехгранное ребро содержит четыре ссылки на соседние четырехгранные ребра. Каждая из четырех ссылок указывает на следующее ребро против часовой стрелки вокруг вершины или грани. Каждая из этих ссылок представляет либо исходную вершину ребра, правую грань, конечную вершину или левую грань. Каждая опорная точка четырехгранного ребра указывает на четырехгранное ребро и поворот (от 0 до 3) «рукава», на которое оно указывает.

Благодаря такому представлению четырехребро:

представляет граф, его двойник и его зеркальное отображение.
двойственный граф можно получить, просто изменив соглашение о том, что такое вершина и что такое грань; и
может представлять наиболее общую форму карты, допускающую вершины и грани степени 1 и 2.

Подробности

Структура с четырьмя ребрами получила свое название от общего механизма их хранения. Одна структура Edge концептуально хранит ссылки на две грани, две вершины и четыре ребра. Четыре сохраненных ребра — это ребра, начинающиеся с двух вершин, прикрепленных к двум сохраненным граням.

Использование

Как и Winged Edge , структуры с четырьмя ребрами используются в программах для хранения топологии 2D или 3D полигональной сетки . Саму сетку не обязательно закрывать, чтобы сформировать действительную четырехгранную структуру.

Используя структуру с четырьмя ребрами, перебирать топологию довольно легко. Часто интерфейс к топологиям с четырьмя ребрами осуществляется через направленные ребра. Это позволяет двум вершинам иметь явные имена (начало и конец), а также дает явные имена лицам (левое и правое, относительно человека, стоящего в начале и смотрящего в направлении конца). Четырем ребрам также присвоены имена в зависимости от вершин и граней: начало слева, начало справа, конец слева и конец справа. Направленное ребро можно изменить на противоположное, чтобы создать ребро в противоположном направлении.

Для итерации вокруг определенной грани требуется только иметь одно направленное ребро, по отношению к которому эта грань находится слева (по соглашению), а затем пройти через все начальные левые ребра, пока не будет достигнуто исходное ребро.

См. также

Ссылки

^ Столфи, Хорхе; Гибас, Леонидас Дж. (апрель 1985 г.). «Примитивы для манипуляций с общими делениями и вычисления диаграмм Вороного» . Транзакции ACM с графикой . 4 (2): 74–169. дои : 10.1145/282918.282923 . S2CID 52852815 .

Внешние ссылки

https://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html Реализация четырехгранников на C++ .
http://www.ic.unicamp.br/~stolfi/EXPORT/software/c/2000-05-04/libquad/ Реализация четырехгранного интерфейса на C. языке

[1] Столфи, Хорхе; Гибас, Леонидас Дж. (апрель 1985 г.). «Примитивы для манипуляций с общими делениями и вычисления диаграмм Вороного» . Транзакции ACM с графикой . 4 (2): 74–169. дои : 10.1145/282918.282923 . S2CID 52852815 .

[1]