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

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

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

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

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

typedef struct { quadedge_ref e [ 4 ]; } quadedge ;     typedef struct { quadedge * next ; unsigned int rot ; } quadedge_ref ;        

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

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

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

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

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

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

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

• Крылатый край
• Комбинаторные карты
• Двусвязный список ребер

• 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.