Квад-реберная структура данных: топологическое представление многогранников.
Quad-edge
Квад-ребро: структура данных для представления топологии 2D/3D карт. Вариант крылатых рёбер, разработанный Stolfi и Guibas. Эффективное хранение графов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Структура данных с четырьмя ребрами — это компьютерное представление топологии двумерной или трехмерной карты, то есть графа, нарисованного на (замкнутой) поверхности. Она была впервые описана Хорхе Столфи и Леонидасом Ж. Гибасом. Это вариант более ранней структуры данных «крылатых ребер».
A quad edge data structure is a computer representation of the topology of a two dimensional or three dimensional map, that is, a graph drawn on a (closed) surface. It was first described by Jorge Stolfi and Leonidas J. Guibas. It is a variant of the earlier winged edge data structure.
Подробности
Структура четырехрёберных элементов (quad edge structure) получила своё название от общего механизма, используемого для их хранения. Одна структура ребра концептуально хранит ссылки на до двух граней, двух вершин и 4 рёбер. Эти четыре ребра – это рёбра, начинающиеся с двух вершин, примыкающих к двум сохранённым граням.
The quad edge structure gets its name from the general mechanism by which they are stored. A single Edge structure conceptually stores references to up to two faces, two vertices, and 4 edges. The four edges stored are the edges starting with the two vertices that are attached to the two stored faces.
Применение
Как и структура крылатых ребер, четырехгранные структуры используются в программах для хранения топологии 2D или 3D полигональной сетки. Сама сетка не обязательно должна быть замкнутой для формирования корректной четырехгранной структуры. Использование четырехгранной структуры значительно упрощает итерацию по топологии. Часто интерфейс к четырехгранным топологиям реализован через ориентированные ребра. Это позволяет явно именовать две вершины (начало и конец), а также давать имена граням (левая и правая, относительно наблюдателя, стоящего в начале и смотрящего в направлении конца). Четыре ребра также получают имена, основанные на вершинах и гранях: начало-лево, начало-право, конец-лево и конец-право. Ориентированное ребро можно инвертировать для получения ребра в противоположном направлении. Для итерации вокруг конкретной грани достаточно иметь одно ориентированное ребро, для которого эта грань находится слева (по соглашению), а затем последовательно переходить по всем ребрам "начало-лево", пока не будет достигнуто исходное ребро.
Much like Winged Edge, quad edge structures are used in programs to store the topology of a 2D or 3D polygonal mesh. The mesh itself does not need to be closed in order to form a valid quad edge structure. Using a quad edge structure, iterating through the topology is quite easy. Often, the interface to quad edge topologies is through directed edges. This allows the two vertices to have explicit names (start and end), and this gives faces explicit names as well (left and right, relative to a person standing on start and looking in the direction of end). The four edges are also given names, based on the vertices and faces: start left, start right, end left, and end right. A directed edge can be reversed to generate the edge in the opposite direction. Iterating around a particular face only requires having a single directed edge to which that face is on the left (by convention) and then walking through all of the start left edges until the original edge is reached.