top of page

COMPUTAÇÃO

Disciplina: Diagrama de Voronoi

Computação do Diagrama de Voronoi Generalizado com Hardware Gráfico

 

 

1. Introdução

O problema da construção do diagrama de Voronoi generalizado consiste é o seguinte: dado um conjunto de objetos geométricos no plano (pontos, segmentos de reta, polígono, curvas), construir a subdivisão planar em que cada região é formada pelo conjunto de pontos mais próximos de um determinado objeto que de qualquer outro.

 

Para o caso particular em que todos os objetos são pontos, o problema pode ser resolvido de forma analítica (exata) em tempo O(n log n). São dois os algoritmos básicos com essa característica: um deles, o algoritmo de Fortune, baseia-se na ordenação prévia dos pontos em uma das dimensões e na construção, por varredura, do diagrama de Voronoi; o outro algoritmo é também baseado na ordenação prévia dos pontos, mas seguida de uma rotina de divisão-e-conquista. Ambos os algoritmos são ótimos, já que o problema de ordenação pode ser reduzido ao problema de construção do diagrama de Voronoi em tempo o(n log n).

 

Quando apenas pontos são considerados, o diagrama de Voronoi tem uma estrutura relativamente simples. Nesse caso, cada uma das regiões de Voronoi é formada pela interseção de n-1 semiplanos (sendo n o número de pontos do conjunto inicial) e, portanto, é um polígono. No entanto, quando se aumenta a complexidade dos objetos geométricos analisados, o problema torna-se muito mais difícil. Uma região de Voronoi pode estar limitada não apenas por segmentos de reta, mas também por curvas de maior ordem. Um ponto e uma reta, por exemplo, podem determinar uma fronteira parabólica.

 

Em vista dessa maior complexidade, não se conhecem algoritmos ao mesmo tempo eficientes e robustos para resolver analiticamente o problema da construção do diagrama de Voronoi generalizado. Algoritmos aproximados são boas alternativas nesse caso. Este trabalho apresenta um algoritmo desse tipo, originalmente descrito por Hoff, Culver, Keyser, Lin e Manocha. Trata-se de um algoritmo é muito eficiente para a representação de diagramas de Voronoi na tela do computador, já que se utiliza de primitivas fornecidas pelo hardware gráfico (placa de vídeo).

 

 

2. O Algoritmo

Quando o diagrama de Voronoi deve ser representado sobre um espaço discreto (como a tela de computador, em que cada pixel pode ter uma única cor), há um algoritmo relativamente simples para sua construção. Para cada ponto (pixel) p, calcula-se sua distância a cada um dos objetos do conjunto inicial. O pixel pertencerá à região de Voronoi associada ao objeto cuja distância a p for mínima. Apesar de parecer pouco eficiente, é essa a idéia básica do algoritmo sugerido por Hoff, Culver, Keyser, Lin e Manocha. Com auxílio do hardware gráfico, o algoritmo torna-se bastante eficiente.

 

2.1. Função Distância

O algoritmo baseia-se no conceito de função distância, dA(x,y). Dado um objeto geométrico A, o valor dA(x,y) nada mais é que a distância do ponto (x,y) a A. A região de Voronoi associada a A corresponde ao subconjunto dos pontos (x,y) do plano (ou dos pixels na tela) para os quais dA(x,y) não é maior que dB(x,y), para qualquer outro objeto geométrico B da entrada. Em outras palavras, apesar de a função distância dA(x,y) "atuar" sobre todos os pontos da tela, ela só se manifesta para os pontos na região de Voronoi de A.

 

O algoritmo sugerido utiliza a representação geométrica da função distância. Como se trata de uma função de duas variáveis, sua representação requer três dimensões. Considere que o eixo que representa a distância tem zero no plano em que estão os objetos geométricos (o plano da tela, nesse caso) e cresce "para baixo", ou seja, para além do plano, do ponto de vista do observador (para dentro do monitor). Como dA(x,y) é uma função não-negativa, ela estará totalmente contida no semiplano além do plano em que estão os objetos da entrada.

 

Consideremos o caso mais simples, em que o objeto A é um ponto. Nessa situação, é fácil verificar que a função distância terá a forma de um cone reto com ápice em A(item a da figura abaixo). Basta notar que a função vale zero em A e tem crescimento linear ao longo de qualquer semi-reta (raio) com origiem em A, o que caracteriza um cone. Como o valor da função é exatamente igual ao raio (é essa a definição da função), o cone é reto.

 

Quando A é um segmento de reta, sua função distância tem forma ligeiramente mais complexa. A forma mais simples de descrevê-la é como resultado da interação de três funções: uma para cada extremidade e uma para o "interior" do segmento. Cada extremidade é um ponto e, portanto, tem um cone reto como função distância. Para o interior do segmento, a função cresce linearmente ao longo de qualquer semi-reta do plano com origem no segmento e perpendicular a ele, formando uma "tenda" (item bda figura). A função distância para o segmento como um todo, portanto, é formada pela composição de uma "tenda" com dois "semicones".

2.2. Descrição do Algoritmo

Uma vez definida a função distância de um objeto geométrico, o algoritmo de Hoff, Culver, Keyser, Lin e Manocha torna-se trivial. Inicialmente, a cada objeto A da entrada é atribuída uma cor distinta. Em seguida, constroem-se, com as cores escolhidas, as representações geométricas das funções distância dos objetos. Dessa forma, são geradas diversas superfícies tridimensionais (cones e tendas, para pontos e segmentos de reta), cada uma das quais cobrindo inteiramente a tela quando projetada sobre ela. Para criar o diagrama de Voronoi, basta pintar cada pixel com a cor da superfície mais próxima ao plano da tela no ponto.

 

A eficiência desse algoritmo depende de duas operações básicas: a construção da representação geométrica das funções distância e a determinação de qual superfície está mais próxima do plano da tela. Conforme se verá, ambas as operações podem ser realizadas de forma muito eficiente com auxílio do hardware gráfico (placa de vídeo).

  • Representação Geométrica das Funções Distância - Cada função distância é representada por uma mesh triangular. Um cone pode ser aproximado por um fan de triângulos, cada qual com um lado em comum com o seguinte (e com o anterior) e tendo como um dos vértices o ponto cuja função distância se quer representar. A tenda é ainda mais simples: cada uma de suas "abas", um retângulo, pode ser representada por um par de triângulos. O hardware gráfico é capaz de fazer rapidamente a interpolação linear dos vértices dos triângulos para calcular a altura (nesse caso, a função distância) dos pontos interiores. Observe que, apesar a função distância aplicar-se a um domínio infinito, na prática ele está restrito à janela em que o diagrama de Voronoi será representado. Para garantir uma cobertura completa da janela, basta que os cones tenham raios iguais à diagonal da janela; da mesma forma, é esse o comprimento máximo das projeções paralelas de cada aba de tenda sobre a tela.

  • Determinação da Superfície mais Próxima - A determinação de qual superfície está mais próxima do plano da tela num determinado ponto (pixel) pode ser feita automaticamente pelo hardware gráfico. Além da cor (armazenada no color buffer), cada pixel tem associado a si uma profundidade, armazenada no Z-buffer. Quando numa mesma imagem a projeção de diversos triângulos (a unidade básica para representação de superfícieis) incide sobre o mesmo pixel, a cor armazenada na posição correspondente do frame buffer será exatamente a do triângulo mais próximo no ponto de projeção. O Z-buffer armazena a profundidade desse ponto. Quando um novo triângulo é adicionado, basta uma consulta ao Z-buffer para verificar se ele deve de fato ser desenhado ou não. Se for desenhado (ou seja, se ocolor buffer for atualizado), o Z-buffer será modificado.

 

Em resumo, o algoritmo se resume em criar uma cena com as meshes triangulares correspondentes às funções distância de cada um dos objetos da entrada. O hardwaregráfico automaticamente faz a interpolação dos triângulos e a escolha de qual superfície deve ser representada em cada pixel. Utilizando uma projeção paralela das superfícies, o resultado é justamente o diagrama de Voronoi dos objetos de entrada.

 

2.3. Complexidade

Seja n o número de objetos de entrada e M x M o tamanho da tela (um quadrado com M pixels de lado). Para cada um dos n objetos da entrada, o algoritmo deve criar a representação poligonal de sua função distância. Para cada uma dessas representações, o hardware gráfico deverá testar todos os pontos da tela. Assim sendo, o algoritmo tem complexidade 

Repare que não foi considerado o tempo necessário para de fato criar a representação poligonal da função de entrada. Pode-se considerar que esse tempo é assintoticamente dominado pelo termo M² da expressão de complexidade. Afinal, o número de pixels utilizados para criar a representação poligonal não pode ser assintoticamente maior que o total de pixels na tela.

É importante mencionar ainda o grau de paralelismo em placas de vídeo pode ser muito alto. O termo M² na expressão só será válido se o paralelismo for baixo; se for muito alto (e nada impede que o seja), o algoritmo pode ser assintoticamente mais rápido na prática.

 

 

 

3. Erros

O algoritmo para determinação do diagrama de Voronoi generalizado de um conjunto de objetos geométricos apresentado no item anterior está sujeito a uma série de erros. Esta seção discute cada uma das possíveis fontes de imprecisão e mostra como é possível controlá-las, limitando o erro total do algoritmo.

 

3.1. Erros na Distância

É possível que a distância de um pixel a um ou mais objetos do conjunto de entrada seja computada de forma imprecisa. Isso pode fazer com que o pixel seja incluído na região de Voronoi associada a um objeto que na verdade não é o mais próximo. São três as principais fontes de erros de distância:

  • erro de meshing: as funções distância associadas a objetos geométricos, que são contínuas, são aproximadas no algoritmo por um conjunto de polígonos que compartilham arestas em comum. Um cone, por exemplo, é representado como um fan de triângulos. Como se trata de uma aproximação, é evidente que estará sujeita a erros. Esse tipo de erro é um dos mais importantes e será tratado com mais detalhes na seção 3.3.

  • erro na representação de curvas: para representar a função distância de curvas genéricas, o algoritmo as aproxima por linhas poligonais. É importante que o número de segmentos utilizados para esse fim não seja pequeno demais: quanto maior for a distância entre a curva aproximada e a original, maior será o erro na representação da função distância.

  • erro de precisão do hardware: como qualquer algoritmo geométrico que trabalha com números de precisão fixa (inteiros, float ou mesmo double), a determinação do Diagrama de Voronoi está sujeita a Problemas de Arredondamento.

 

3.2. Erros Combinatórios

Enquanto os erros na distância são de natureza quantitativa, os erros combinatórios são qualitativos. Trata-se de situações em que a topologia do diagrama de Voronoi apresenta imprecisões. Pode haver casos em que o algoritmo apresenta como vizinhas duas regiões que não o são quando o problema é resolvido analiticamente. Pode ocorrer também o contrário: duas regiões que não deveriam compartilhar uma aresta o fazem. Em casos extremos, toda a região de Voronoi associada a um objeto da entrada pode desaparcer. São três as causas básicas desse tipo de erro:

  • erro na distância: qualquer tipo de erro na distância pode vir a provocar erros combinatórios;

  • erro de precisão do Z-buffer: em algumas situações, a precisão de representação da coordenada z no Z-buffer pode ser insuficiente para que a cor de um pixel seja determinada corretamente;

  • erro de resolução: essa é talvez a principal fonte de erros combinatórios. O algoritmo trabalha sobre uma versão discretizada do espaço. Cada pixel, por menor que seja, corresponde a um conjunto teoricamente infinito de pontos. Com freqüência, o mesmo pixel deve representar ao mesmo tempo pontos que pertenceriam a diferentes regiões de Voronoi. Evidentemente, ele só poderá assumir uma das possíveis cores. Devido a uma limitação na resolução, podem-se perder informações importantes nesse momento. Se a estrutura topológica do problema for realmente importante para a aplicação, pode-se amenizar o problema aumentando-se a resolução nas regiões em que o problema ocorre. A figura abaixo ilustra algumas dessas situações. Os dois primeiros quadros mostram como uma região pode simplesmente desaparecer. Os dois últimos mostram um caso em que as fronteiras são representadas incorretamente.

3.3. Erros de Meshing

Quando se representa um cone por um fan de triângulos, inevitavelmente ocorrerão erros de distância. Seriam necessários infinitos triângulos para que se representasse perfeitamente o cone. Um corte do cone (paralelo à base) é uma circunferência; no fan de triângulos, é um polígono regular. Evidentemente, quanto maior for o número de lados do polígono (ou o número de triângulos no cone), menor será o erro.

A figura abaixo mostra como pode ser calculado o erro de distância quando a projeção de cada triângulo sobre a base tem ângulo interno, no ápice, igual a a:

Analisando-se o triângulo retângulo assinalado na figura, observa-se que:

 

 

 

 

 

Essa equação permite que se determine maior valor possível de a (ou seja, o menor número de triângulos necessário) para que se obtenha um erro não inferior a e. Suponha que se deseje que o erro seja inferior à largura de um pixel. Para garantir que as funções distância cobrirão todos os pixels da janela (que potencialmente fazem parte de suas regiões de Voronoi), o raio dos cones (R) deve ser igual à medida da diagonal da janela. Utilizando-se esse fato na equação acima, pode-se calcular o número de triângulos necessários para representar cada cone para diferentes tamanhos de tela:

4. Heurística para Aceleração

Apesar de o hardware gráfico normalmente ser muito rápido, é inevitável que o algoritmo se torne lento para um número relativamente grande de objetos. Mesmo o objeto mais simples, um ponto, dá origem a uma superfície (cônica) que não só cobre toda a tela, mas também possui partes fora da tela (descartadas pelo hardware gráfico). De fato, como o cone tem raio igual à diagonal de tela, sua projeção tem área aproximadamente igual a 6,28 vezes a área da tela.

 

O raio do cone é calculado para a situação de pior caso, em que o ponto está em um dos cantos da tela e é o mais próximo do pixel no canto oposto. O cone é gerado de forma a cobrir a maior região de Voronoi concebível. Quando o número de pontos é grande, entretanto, a maioria das regiões de Voronoi poderia estar contida em círculos (projeções dos cones) muito menores.

 

Idealmente, para cada ponto P da entrada deveria ser criado um cone de raio igual à maior distância entre P e um pixel de sua região de Voronoi. Evidentemente, não é possível fazer isso sem resolver o próprio problema da determinação do diagrama de Voronoi. Entretanto, métodos heurísticos permitem limitar o raio dos cones a valores muito menores que a diagonal da tela. Essa seção trata de uma heurística desenvolvida para o caso específico em que todos os objetos da entrada são pontos (mais adiante, serão apresentadas sugestões de como adaptá-la para objetos genéricos).

 

4.1. Regiões de Voronoi

A Região de Voronoi de um ponto P, V(P), é, por definição, formada pela Interseção dos Semiplanos que contêm P determinados pelas mediatrizes dos segmentos que ligam P a cada um dos outros pontos da entrada. A adição de um novo ponto jamais aumentará a região de Voronoi de P: se o novo semiplano contiver totalmente a região de Voronoi de P, ela permanecerá inalterada; caso contrário, será reduzida.

Outra maneira de se interpretar esse fato é a seguinte: a região de Voronoi de P determinada por um subconjunto dos pontos da entrada, V'(P), contém a região de Voronoi de P determinada por todos os pontos do conjunto, V(P). Assim sendo, um limite superior para o raio do círculo que contém V(P) pode ser obtido calculando-se o raio de um círculo que contenha V'(P).

 

É essa a idéia básica da heurística: para cada ponto P, encontrar um subconjunto S(P) dos demais pontos de entrada que forneça uma boa estimativa para a região de Voronoi de P e, a partir dela, encontrar um limite superior para o raio do triângulo. "Boa estimativa", nesse caso, significa uma região de raio tão pequeno quanto possível. Evidentemente, isso deve ser feito de forma rápida; a heurística não pode ser o gargalo do algoritmo como um todo.

 

4.2. Algoritmo - Linhas Gerais

Em linhas gerais, a Heurística implementada é a seguinte:

1. Divide-se a tela em K² Células Quadradas de Lado M/K.

Entrada

Entrada com a Grid

2. Associa-se a cada célula um bucket inicialmente vazio; em seguida, insere-se cada ponto P no bucket correspondente (quando houver mais de um ponto na mesma célula, apenas um deles deve ser inserido bucket associado).

Entrada com Grid

Buckets correspondentes

3. Para cada ponto P da entrada, selecionam-se para compor S(P) os pontos presentes nos buckets correspondentes às quatro células vizinhas (na diagonal) à célula em que P está; feito isso, calcula-se o raio de V'(P) (a região de Voronoi de P induzida pelos quatro vizinhos), usado como limite superior para o raio de V(P).

Vizinhos escolhidos para S(P)
(P é o ponto vermelho)

Região de Voronoi induzida 
pelos quatro vizinhos

Observe que o quadrilátero formado pelos pontos vizinhos mencionados no item 3 obrigatoriamente contém o ponto P (isso só é verdade porque foram escolhidos os vizinhos diagonais). Essa é uma condição necessária e suficiente para que V'(P) seja limitada.

 

Uma análise mais cuidadosa desse algoritmo revela que, da forma como foi apresentado, ele não está completo. Há uma série de casos especiais não tratados, que serão analisados nos itens que se seguem.

 

4.3. Bordas

Um primeiro caso especial é o dos pontos presentes nas células da borda, i.e., que fazem fronteira com os limites da tela. Tais células não no máximo duas células vizinhas na diagonal, mas são necessárias quatro para que se garanta a criação de uma região de Voronoi fechada. Para tratar esse problema, criam-se células falsas, além das bordas. O ponto representante de cada uma delas é também um ponto falso, obtido a partir da "reflexão" de um ponto da entrada em relação à borda. A figura abaixo mostra como isso seria feito no caso do exemplo mostrado até aqui (os pontos mais claros são os falsos):

Grid original

Grid com bordas

Na figura, cada ponto falso é criado a partir da reflexão (em relação à borda) do ponto que representa a célula real vizinha à célula falsa. Se não houver um ponto na célula vizinha, também a célula falsa permanecerá vazia. As quatro células "de canto" são tratadas de forma especial. Os pontos escolhidos para representá-las são obtidos pela reflexão (em relação ao canto da tela) do ponto da entrada mais próximo (do canto).

 

Por construção, os pontos extras poderão ser utilizados de forma correta para limitar a região de Voronoi associada a qualquer um dos pontos originais. Sejam P e Q dois pontos originais e Q' um ponto falso criado a partir da reflexão de Q sobre a borda. Seja P o ponto cuja região de Voronoi se deseja estimar. Deseja-se provar que, se Q' for utilizado como vizinho, nenhum pixel da região de Voronoi de P será indevidamente excluído.

 

A prova é feita por contradição. Suponha que exista um pixel p da tela pertencente à região de Voronoi de P erradamente excluído pela ação de Q', ou seja, que pertença à região de Voronoi de P e esteja mais próximo de Q' que de P. Pela construção de Q' (obtido pela reflexão de Q na borda), qualquer ponto dentro dos limites da tela estará mais próximo de Q que de Q'. Em especial, isso significa que p está mais próximo de Q que de Q'. Como p está mais próximo de Q' que de P, conclui-se que p está mais próximo de Q que de P. Como Q faz parte do conjunto de objetos de entrada, p não pode pertencer à região de Voronoi de P, o que é uma contradição.

 

4.4. Células Vazias

Mesmo após a criação dos pontos, é possível que células (tanto internas quanto próximas à borda) permanecam sem ou ou mais de seus quatro vizinhos. Há várias maneiras de se resolver esse problema. A estratégia utilizada é verificar não apenas a primeira célula vizinha ao ponto P testado, mas todas as células numa determinada direção (até que seja encontrada alguma que contém um ponto). O exemplo a seguir mostra como isso deve ser feito:

Vizinhança expandida

Repare que, caso se ultrapasse a borda da tela, a busca deve prosseguir paralelamente a ela, se necessário. Como as quatro células dos cantos nunca estarão vazias (a menos que a própria entrada seja nula), o algoritmo sempre termina. Além disso, fornece sempre quatro pontos, cada um dos quais em um dos quadrantes determinados pelo ponto P.

 

4.5. Tamanho das Regiões de Voronoi

Os procedimentos adotados até aqui garantem que, para cada ponto da entrada, será possível encontrar uma região de Voronoi limitada que o contém. Entretanto, é possível que o raio dessa região seja muito grande; pode chegar a ser maior que a própria diagonal da tela. Evidentemente, regiões de raio grande são indesejáveis, já que em nada contribuem para a aceleração do algoritmo.

 

A figura abaixo mostra o tipo de situação que leva a uma região indesejada. Esse fato ocorrerá sempre que o ponto P estiver muito próximo de um dos lados do quadrilátero. A maneira mais simples de medir essa proximidade é medir o ângulo de visão do lado por P. Na figura observa-se que BPC mede quase 180 graus.

Vizinhança expandida

Para evitar A figura abaixo mostra o tipo de situação que leva a uma região indesejada. Esse fato ocorrerá sempre que o ponto P estiver muito próximo de um dos lados do quadrilátero. A maneira mais simples de medir essa proximidade é medir o ângulo de visão do lado por P. Na figura, o ângulo BPC mede quase 180 graus.

 

A figura abaixo mostra o tipo de situação que leva a uma região indesejada. Esse fato ocorrerá sempre que o ponto P estiver muito próximo de um dos lados do quadrilátero. Outra maneira de observar a mesma situação é analisar o ângulo de visão do lado por P. Se o ponto estiver muito próximo do lado, esse ângulo estrá próximo de 180 graus (é esse o caso do ângulo BPC na figura).

 

Foram adotadas 3 estratégias para evitar que esse tipo de problema ocorresse:

  • Para que a célula vizinha seja considerada, seu representante deve tem uma distância mínima m (tanto na horizontal quanto na vertical) do ponto P. Se essa distância mínima não for observada, a célula vizinha deve ser tratada como uma célula vazia (outra célula mais distante é escolhida utilizando-se o conceito de "vizinhança expandida", ilustrado na subseção anterior).

  • Os pontos falsos devem ser criados de forma que estejam a uma distância de pelo menos m da borda. Para isso, basta testar, depois da reflexão (utilizada para criar os pontos fantasmas), se a distância mínima é válida. Caso não seja, basta afastar o ponto da borda ao longo da direção normal a ela. No caso dos pontos dos cantos, esse afastamento pode ocorrer na horizontal, na vertical ou em ambas as direções, até que o ponto esteja suficientemente distante da tela.

  • Para diminuir a probabilidade de problemas, adota-se a política de escolher como representante de um bucket o ponto que estiver mais distante das bordas (lembre-se de que apenas um ponto é escolhido).

 

4.6. Eficiência da Estratégia de Aceleração

Uma medida efetiva da eficiência da estratégia de aceleração é o fator de cobertura dos cones, definido pela razão entre a área coberta pelas projeções dos cones em relação ao plano da tela e a área efetivamente visível da janela em que o diagrama é apresentado. Na versão original do algoritmo, o fator de cobertura de cada cone é fixo e vale aproximadamente 6,28 (2p). Com o esquema de aceleração, cada cone tem seu próprio fator de cobertura.

 

Alguns testes preliminares indicaram que o número de células em que a tela é dividida deve ser aproximadamente igual ao número de pontos na entrada para maximizar a eficiência do algoritmo. Com essa estratégia, para 200 pontos (e 225 células) foi possível reduzir o fator de cobertura total (considerando todos os cones) de aproximadamente 1250 para valores entre 15 e 25, para uma distribuição aleatória uniforme de pontos.

 

 

 

 

5. Extensões e Variações

A idéia básica do algoritmo apresentado pode ser adapatada facilmente para resolver variações do problema de Voronoi. Entre elas, destacam-se:

  • Diagrama de Voronoi para pontos mais distantes. Para representá-lo, basta inverter o sentido de crescimento da função distância. Dessa forma, o triângulo escolhido pelo Z-buffer será o que tem o maior valor da função distância. Esse triângulo tem justamente a cor do ponto da entrada mais distante desse pixel.

  • Diagrama de Voronoi de pontos com peso. Uma versão do problema de Voronoi atribui pesos aos objetos. Dessa forma, as fronteiras das regiões de Voronoi deixam de ser pontos que equidistam de dois objetos e passam a ser pontos cujas distâncias aos objetos são correspondentes às razões entre seus pesos. Esse efeito pode ser simulado facilmente alterando-se a inclinação do cone.

  • Diagrama de Voronoi em três dimensões. O algoritmo apresentado nesse trabalho pode ser adaptado para três dimensões. Para isso, entre outras modificações, é necessário alterar as funções distância dos diversos objetos.

  • Extração da estrutura topológica do diagrama de Voronoi e da triangulação de Delaunay. Da forma como foi proposto, o algoritmo tem uma peculiaridade: apesar de exibir na tela o diagrama de Voronoi de um conjunto de objetos, sua estrutura topológica é, do ponto de vista do código, desconhecida. Afinal, boa parte dos cálculos é feita pelo hardware gráfico. É possível, no entanto, fazer com que o programa leia a memória de vídeo e utilize as informações de fronteira para construir a estrutura topológica do diagrama de Voronoi (e, a partir dela, a triangulação de Delaunay, por exemplo). Evidentemente, devido aos erros combinatórios já mencionados, em alguns casos a estrutura topológica obtida a partir do algoritmo proposto não estará totalmente correta, ou seja, não será idêntica à que seria obtida se o diagrama fosse criado por um algoritmo analítico. Para grande parte das aplicações, no entanto, a solução aproximada é suficiente.

 

Quanto à estratégia de aceleração, ainda há alguns aspectos importantes a explorar:

  • Seria interessante fazer uma análise mais rigorosa da eficiência da estratégia de aceleração, tanto analítica quanto experimental. Entre outras coisas, essa análise permitira determinar com mais precisão o número de células em que deve ser dividida a janela para minimizar o fator de cobertura dos cones. Evidentemente, esse valor dependeria não só de n, mas também da distribuição dos pontos na janela.

  • Implementar a estratégia de aceleração para objetos mais complexos, como segmentos de reta e curvas de maior grau. As extremidades de um segmento de reta podem ser tratadas como pontos comuns do ponto de vista do algoritmo de aceleração, já que a função distância associada a cada um deles é também um cone. Seria interessante criar uma estratégia para diminuir o tamanho das folhas da "tenda" que representa a função distância associada ao interior de um segmento (o número de triângulos em cada folha não pode ser reduzido, ao contrário do caso dos cones; haverá exatamente dois triângulos em cada folha, independentemente de seu comprimento).

 

 

 

 

Bibliografia Básica

K. E. Hoff III, T. Culver, J. Keyser, M. Lin e D. Manosha. "Fast computation of generalized Voronoi diagrams using graphics hardware. Proceedings of ACM SIGGRAPH using graphics hardware". 

Texto a ser Editado. Aguardem!

OBSERVAÇÃO: Este TEXTO pode estar desatualizado, uma vez que ele foi Editado quando nossa Revista Ensino&Informação estava Ativa nos anos 2003 e 2004!

Tínhamos uma SERVIDOR próprio usando WINDOWS 200 SERVER da Microsoft. O endereço era www.ensinoeinformacao.nom este destinado à Pessoa Física e os muito raros ".COM" para empresas - Pessoa jurídica.

Tínhamos um SERVIDOR DE E-MAIL próprio. IP FIXO e REVERSO pela Brasil TELECOM.

Foi uma gratificante Experiência para nós, pois a Internet ainda era meio que insipiente! Nenhuma Empresa apostava em Marketing usando a Internet e assim, nós não conseguíamos Patrocínio!

Voltar para COMPUTAÇÃO: Disciplinas!

Voltar para DIAGRAMA DE VORONOI: Tópicos!

  A partir de 20 Out de 2020

Você é o Visitante de Número

Nosso CANAL

bottom of page