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

18

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!

bigmonachus
fonte
3
Apenas para preencher as lacunas: a álgebra abstrata é o estudo de conjuntos de elementos que respeitam certas regras. Como você deve ter adivinhado, as regras que esses conjuntos atendem são propriedades como fechamento, elementos de identidade, existência de inversos únicos e, à medida que se procede comutatividade, associatividade, etc. É o estudo da álgebra em conjuntos que não se comportam necessariamente como os números reais (um bom exemplo são permutações).
Ross Snider
Acho que minha segunda pergunta foi um pouco falhada. Eu conheço alguma teoria de grupo. Eu sei o que são anéis e campos. No artigo, eles definem uma álgebra abstrata: "Uma álgebra de aresta é uma álgebra abstrata (E, E *, Onext, Rot, Flip, Flip) que satisfaz as propriedades E1-E5 e F1-F5"
bigmonachus
[...] e eu não tenho ideia do que isso significa. Não é uma álgebra sobre um campo, é?
Bigmonachus

Respostas:

32

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:ffeevv

Gráficos primários e duplos

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 dardoetail(e)head(e)left(e)right(e)tail(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.)left(e)

Para qualquer dardo , Guibas e Stolfi associam três dardos relacionados:e

  1. : o dardo que sai da cauda ( e ) em seguida no sentido anti-horário apóse .tailNext(e)tail(e)e
  2. : O “mesmo” dardo quee , mas com a esquerda ( e ) e a direita ( e ) trocadas.flip(e)eleft(e)right(e)
  3. : o dardo duplo obtido dandoe um quarto de volta no sentido anti-horário em torno de seu ponto médio.rotate(e)e

tailNext, girar e virar

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

  • right(tailNext(e))=left(e)
  • right(flip(e))=left(e)
  • right(rotate(e))=head(e)
  • flip(flip(e))=e
  • rotate(rotate(rotate(rotate(e))))=e
  • tailNext(rotate(tailNext(rotate(e))))=e

e Flipe.Flip

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

  • reverse(e)=rotate(flip(rotate(e)))
  • leftNext(e)=rotate(tailNext(rotate(rotate(rotate(e)))))eleft(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!

Jeffε
fonte
Eu usei o OmniGraffle.
Jeffε