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

18

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

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

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

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

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

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

Спасибо!

bigmonachus
источник
3
Просто чтобы заполнить пробелы: абстрактная алгебра - это изучение наборов элементов, которые уважают определенные правила. Как вы уже догадались, правила, которым удовлетворяют эти множества, - это такие свойства, как замыкание, элементы тождества, существование уникальных инверсий, а также переход к коммутативности, ассоциативности и т. Д. Это изучение алгебры множеств, которые не обязательно ведут себя как действительные числа. (хорошим примером являются перестановки).
Росс Снайдер
Я предполагаю, что мой второй вопрос был немного пропущен. Я знаю некоторую теорию групп. Я знаю, что такое кольцо и поле. Это просто , что в статье они определяют в абстрактной алгебре: «Ребро алгебра является абстрактная алгебра (Е, Е *, ONEXT, гниль, Флип) , удовлетворяющие свойства E1-E5 и F1-F5»
bigmonachus
[...] и я понятия не имею, что это значит. Это не алгебра над полем, не так ли?
bigmonachus

Ответы:

32

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

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

Первичные и двойственные графы

ехвост(е)голова(е)осталось(е)право(е)хвост(е)осталось(е)

е

  1. tailNext(е)хвост(е)е
  2. кувырок(е)еосталось(е)право(е)
  3. поворот(е)е

tailNext, вращать и переворачивать

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

  • право(tailNext(е))знак равноосталось(е)
  • право(кувырок(е))знак равноосталось(е)
  • право(поворот(е))знак равноголова(е)*
  • кувырок(кувырок(е))знак равное
  • поворот(поворот(поворот(поворот(е))))знак равное
  • tailNext(поворот(tailNext(поворот(е))))знак равное

е FLяпe.Flip

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

  • задний ход(е)знак равноповорот(кувырок(поворот(е)))
  • leftNext(е)знак равноповорот(tailNext(поворот(поворот(поворот(е)))))еосталось(е)

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

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

Веселиться!

Jeffε
источник
Я использовал OmniGraffle.
Джефф