1. Introdução
 

Problema: Dado um conjunto finito S de pontos no espaço tridimensional, encontrar o fecho convexo (conv(S)) dos pontos de S.

É desejável que o algoritmo que resolva o problema acima devolva como resposta uma estrutura de conv(S) contendo informações de adjacência. Por exemplo:

- dado um vértice v em conv(S), determinar todos os vértices adjacentes a v em conv(S);

- dada uma aresta e em conv(S), determinar todas as faces que compartilham e em conv(S);

- dada uma face f em conv(S), determinar todos os vértices de f em conv(S); e assim por diante...

Existem várias maneiras de representarmos o poliedro conv(S). Por exemplo, a estrutura Lista de Faces - aqui,  cada face é representada através de uma lista ordenada de vértices. Assim, um poliedro é representado por uma lista de suas faces (polígonos) que compõe a sua superfície. Neste caso, temos apenas uma informação de adjacência: a dentre vértices de uma mesma face. A desvantagem aqui é que gastaríamos muito tempo para determinarmos outros tipos de adjacências, como por exemplo, se quisermos determinar todas as faces adjacentes a um dado vértice ou uma dada aresta, etc.

Veremos outras estruturas de dados mais eficientes para representarmos o poliedro conv(S): a estrutura de dados winged-edge, a estrutura DCEL (doubly connected edge list) e a estrutura  quad-edge.

(Note que estas estruturas podem ser utilizadas para representarmos grafos planares.)
 
 
 
 
 

2. Estrutura de dados  winged-edge
 

Esta estrutura possibilita encontrarmos todos os tipos de adjacência, de forma eficiente, entre vértices, arestas e faces de um poliedro. Ela é composta de três listas:

- lista de vértices, onde cada estrutura de um vértice v armazena as coordenadas (x, y, z) de v, além de um apontador para uma aresta arbitrária incidente a v, denotada por av(v);

- lista de faces, onde cada estrutura de uma face f armazena um apontador para uma aresta arbitrária af(f) contida na fronteira de f;

- lista de arestas, onde cada estrutura de uma aresta e tem basicamente oito campos:

    - dois apontadores v1(e) e v2(e), apontando para os dois vértices extremos de e;

    - dois apontadores para as duas faces incidentes a e, fccw(e) (counter clockwise) e fcw(e) (clockwise);

    - quatro apontadores para as arestas adjacentes a e (as "wings" de e); pccw(e) (previous counter clockwise), nccw(e) (next counter clockwise), pcw(e) (previous clockwise) e ncw(e) (next clockwise);

A representação da estrutura da aresta é dada pela figura abaixo:
 

Exemplo 1.1: A estrutura de dados winged-edge correspondente ao cubo da figura 2:
 

vértice	(x, y, z)	av
p1	(1, 0, 0)	e1
p2	(1, 1, 0)	e2
p3	(1, 1, 1)	e3
p4	(1, 0, 1)	e4
p5	(0, 0, 0)	e9
p6	(0, 1, 0)	e10
p7	(0, 1, 1)	e11
p8	(0, 0, 1)	e12

 

face	af
f1	e1
f2	e2
f3	e10
f4	e12
f5	e1
f6	e3

 

aresta	v1	v2	fccw	fcw	pccw	nccw	pcw	ncw
e1	p1	p2	f1	f5	e4	e2	e5	e8
e2	p2	p3	f1	f2	e1	e3	e6	e5
e3	p3	p4	f1	f6	e2	e4	e7	e6
e4	p4	p1	f1	f4	e3	e1	e8	e7
e5	p1	p5	f5	f4	e1	e9	e12	e4
e6	p2	p6	f2	f5	e2	e10	e9	e1
e7	p3	p7	f6	f2	e3	e11	e10	e2
e8	p4	p8	f4	f6	e4	e12	e11	e3
e9	p6	p6	f5	f3	e8	e5	e10	e12
e10	p6	p7	f2	f3	e5	e6	e11	e9
e11	p7	p8	f6	f3	e6	e7	e12	e10
e12	p8	p5	f4	f3	e7	e8	e9	e11

 
 
 
 

3. Estrutura de dados DCEL
 

Esta estrutura é bem parecida com a estrutura winged-edge vista anteriormente. Aqui, temos também as listas de vértices, de faces e de arestas. As estruturas dos vértices e das faces são iguais ao da estrutura winged-edge, mas a estrutura da aresta é diferente:

- a estrutura de uma aresta e consiste basicamente de quatro campos: V1(e) e V2(e) são os apontadores para os vértices extremos de e; F1(e) e F2(e) são apontadores para as faces esquerda e direita, respectivamente, em relação a aresta e, pela orientação dada pelos seus vértices extremos; e dois apontadores de arestas P1(e) (que aponta para a próxima aresta no sentido anti-horário em torno de V1) e P2(e) (que aponta para a próxima aresta no sentido anti-horário em torno de V2), respectivamente.

A representação da estrutura da aresta é dada pela figura abaixo:
 

Exemplo 3.1. O exemplo a seguir é mostrado na figura 4: a representação DCEL de um polígono onde A é sua face externa e B é a sua face interna.
 

Exemplo 3.2. Na figura 5 é mostrado a representação DCEL de um polígono sem aresta "solta".
 

4. Estrutura de dados quad-edge
 

Nesta estrutura, cada aresta é dividida em quatro quad-edges, possibilitando uma visão simétrica total sobre o grafo primal e o grafo dual, conforme pode ser vista na figura 6. Um contador r de dois bits é usado para endereçar um slot num registro de aresta e de quatro quad-edges. Um bit adicional f denota o flipped status por aresta.

A estrutura quad-edge é definida formalmente como três operações de arestas: Onext(), Rot() e Flip(). Uma quad-edge é representada como uma tripla (e, r, f) com um registro e de quatro quad-edges, e[0] até e[3] incidentes na aresta corrente, r pertencente a {0, 1, 2, 3} e f  pertencente a {0, 1}.
 

Um exemplo de aplicação bem útil, é a utilização da estrutura quad-edge para a representação de uma triangularização de Delauney e seu respectivo diagrama de Voronoi.
 

5. Referências
 

[1] http://www.cs.ruu.nl/CGAL/Information/index.html

    - Using Generic Programming for Designing a Data Structure for Polyhedral Surfaces
      Lutz Kettner, Inst. of Theoretical Computer Science, ETH Zurich, CH-8092 Zurich, Switzerland.

    - Colored DCEL for Boolean Operations in 2D
      Wolfgang Freiseisen, 31. January 1998.

[2] http://www.cs.cmu.edu/~quake/tripaper/triangle2.html