A estrutura de dados quad-edge (Delaunay / Voronoi)

2 perguntas para os geômetros computacionais ou algebristas:

Estou apenas começando a mergulhar na geometria computacional e estou adorando =)

Estou tentando ler o famoso artigo de Guibas e Stolfi chamado "Primitivos para a manipulação de subdivisões gerais e o cálculo dos diagramas de Voronoi" para implementar um algoritmo de triangulação de Delaunay. Fico tentado a pular todo o material teórico e apenas ler a descrição de sua estrutura de dados quad-edge para economizar tempo. No entanto, acho que vale a pena entender toda a matemática do artigo se a estrutura for amplamente usada ou apenas porque pode ser bonita.

A matemática é um pouco densa para mim. Não sou completamente ignorante em topologia, mas a descrição da álgebra de arestas requer conhecimento de álgebra abstrata que não tenho.

Minhas duas perguntas são: que outras aplicações da estrutura quad-edge existem além da computação em Delaunay / Voronoi? Parece uma ferramenta extremamente poderosa.

A segunda pergunta; O que é uma álgebra abstrata? Seria ótimo se você pudesse me dar uma referência a uma introdução à álgebra abstrata, apenas o suficiente para que eu possa entender a seção na álgebra de arestas.

Obrigado!

Eu acho que o formalismo de "álgebra de borda" de Guibas e Stolfi é um pouco desnecessário.

Tudo o que é realmente necessário é lembrar a distinção entre gráficos primários e duplos. Cada face do gráfico primal tem um vértice duplo correspondente f ∗ ; cada aresta e do gráfico primal tem uma aresta dupla correspondente e ∗ ; e cada vértice v do gráfico primitivo tem uma face dupla correspondente v ∗ . As arestas primárias conectam vértices primários e separam faces primárias; arestas duplas conectam vértices duplos e separam faces duplas. O dual do dual de qualquer coisa é a coisa original. Veja a Figura 4 no artigo de Guibas e Stolfi:$f$$f^*$$e$$e^*$$v$$v^*$

Guibas e Stolfi propõem pensar em cada aresta (primal ou dupla) como uma coleção de quatro arestas direcionadas e orientadas ; por simplicidade, chamarei esses dardos . Cada dardo pontos de um endpoint cauda ( → e ) para a outra extremidade da cabeça ( → e ) , e localmente separa duas faces esquerda ( → e ) e direita ( → e ) . A escolha de qual ponto final chamar cauda ( → e ) é o ponto de partida do dardo$\vec{e}$$\text{tail}(\vec{e})$$\text{head}(\vec{e})$$\text{left}(\vec{e})$$\text{right}(\vec{e})$$\text{tail}(\vec{e})$direção e a escolha de qual face chamar à é sua orientação . (Guibas e Stolfi usam "Org" e "Dest" em vez de "cauda" e "cabeça", mas eu prefiro os rótulos mais curtos, porque abreviações desnecessárias são más.)$\text{left}(\vec{e})$

Para qualquer dardo , Guibas e Stolfi associam três dardos relacionados:$\vec{e}$

1. : o dardo que sai da cauda ( → e ) em seguida no sentido anti-horário após → e .$\text{tailNext}(\vec{e})$$\text{tail}(\vec{e})$$\vec{e}$
2. : O “mesmo” dardo que → e , mas com a esquerda ( → e ) e a direita ( → e ) trocadas.$\text{flip}(\vec{e})$$\vec{e}$$\text{left}(\vec{e})$$\text{right}(\vec{e})$
3. : o dardo duplo obtido dando → e um quarto de volta no sentido anti-horário em torno de seu ponto médio.$\text{rotate}(\vec{e})$$\vec{e}$

Essas três funções satisfazem todos os tipos de identidades maravilhosas, como as seguintes:

• $\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

Além disso, dadas essas três funções, é possível definir várias outras funções úteis, como

• $\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})$

Por fim, conhecer essas funções diz tudo sobre a topologia da subdivisão e qualquer subdivisão poligonal de qualquer superfície (orientável ou não) pode ser codificada usando essas três funções.

A estrutura de dados quad-edge é uma representação particularmente conveniente de um gráfico de superfície que fornece acesso a todas essas funções, juntamente com várias outras operações em tempo constante, como inserir, excluir, contratar, expandir, e inverter bordas; dividir ou mesclar vértices ou faces; e adicionar ou excluir alças ou capas cruzadas.

Diverta-se!