Четырехугольный - Quad-edge

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

Обзор

Структура данных с четырьмя ребрами:

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

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

Подробности

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

Использует

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

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

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

Смотрите также

Рекомендации

внешняя ссылка