Четырехгранная структура данных (Делоне / Вороной)

2 вопроса для вычислительных геометров или алгебраистов:

Я только начинаю погружаться в вычислительную геометрию, и мне это нравится =)

Я пытаюсь прочитать знаменитую статью Гибаса и Столфи под названием «Примитивы для манипулирования общими подразделениями и вычисления диаграмм Вороного» с целью реализации алгоритма триангуляции Делоне. Я испытываю желание пропустить все теоретические вещи и просто прочитать описание их четырехугольной структуры данных, чтобы сэкономить время. Тем не менее, я думаю, что стоит понять всю математику в статье, если структура широко используется, или просто потому, что она может быть красивой.

Для меня математика немного сложна. Я не совсем в курсе топологии, но описание их краевой алгебры требует знания абстрактной алгебры, которой у меня нет.

Мои два вопроса: Какие существуют другие применения структуры с четырьмя ребрами, кроме вычисления Делоне / Вороного? Это похоже на чрезвычайно мощный инструмент.

Второй вопрос; Что такое абстрактная алгебра? Было бы здорово, если бы вы дали мне ссылку на введение в абстрактную алгебру, достаточно, чтобы я мог понять раздел об их алгебре ребер.

Спасибо!

Я думаю, что формализм «краевой алгебры» Гибаса и Столфи немного ненужен.

Все, что действительно необходимо, - это помнить различие между первичным и двойственным графами. Каждая грань первичного графа имеет соответствующую двойственную вершину f ∗ ; каждому ребру e основного графа соответствует двойственное ребро e ∗ ; и каждая вершина v основного графа имеет соответствующую двойственную грань v ∗ . Первичные ребра соединяют первичные вершины и отдельные первичные грани; двойные ребра соединяют двойные вершины и отдельные двойные грани. Двойственный дуал чего-либо - это оригинальная вещь. Смотрите рисунок 4 в статье Гибаса и Столфи:$f$$f^*$$e$$e^*$$v$$v^*$

$\vec{e}$$\text{tail}(\vec{e})$$\text{head}(\vec{e})$$\text{left}(\vec{e})$$\text{right}(\vec{e})$$\text{tail}(\vec{e})$$\text{left}(\vec{e})$

$\vec{e}$

1. $\text{tailNext}(\vec{e})$$\text{tail}(\vec{e})$$\vec{e}$
2. $\text{flip}(\vec{e})$$\vec{e}$$\text{left}(\vec{e})$$\text{right}(\vec{e})$
3. $\text{rotate}(\vec{e})$$\vec{e}$

Эти три функции удовлетворяют всем видам замечательных идентичностей, таких как следующее:

• $\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
• $\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
• $\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
• $\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

$e~Flip$e.Flip

Кроме того, учитывая эти три функции, можно определить несколько других полезных функций, таких как

• $\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$
• $\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$$\vec{e}$$\text{left}(\vec{e})$

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

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

Веселиться!