top of page

COMPUTAÇÃO

Disciplina: Diagrama de Voronoi

Veja a seguir os seguintes conteúdos já disponíveis. Para tomar conhecimento da lista completa dos conteúdos vistos nesta disciplina, clique no ícone "PROGRAMA" acima. OBSERVAÇÃO: Alguns dos assuntos estão divididos em partes as quais podem ser acessadas clicando nos links abaixo.

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

Diagrama de Voronoi: Introdução

Na Matemática, um Diagrama de Voronoi é um tipo especial de Decomposição de um dado Espaço, por exemplo, um Espaço Métrico, determinado pela Distância (uma Métrica é uma Generalização do Conceito de Distância) para uma determinada família de objetos (subconjuntos) no Espaço. Estes objetos são normalmente chamados de Sítios ou Geradores (apesar de nomes como “sementes” estarem também em uso). Cada Sítio está associado à Célula de Voronoi correspondente, isto é um conjunto de todos os pontos no dado Espaço o qual a distância para o dado sítio não é maior que sua distância para os outros objetos - o Conceito de Vizinho mais Próximo em Problemas de LOGÍSTICA [ver, por exemplo, Espaços Métricos: Generalização do Conceito de Mediatriz e veja, também, Modelagem Matemática Aplicada à Logística Urbana] nos deparamos com a questão de dividir uma dada região R (deve ser convexa!) segundo, por exemplo, o CRITÉRIO VIZINHO MAIS PRÓXIMO].¹ Foi nomeado de Georgy Voronoi posteriormente, e também chamado de Tesselação de Voronoi, uma Decomposição Voronoi, ou um Mosaico de Dirichlet (após Lejeune Dirichlet). Diagramas de Voronoi podem ser encontrados em diversos campos da Ciência e Tecnologia, até mesmo na Arte, tendo inúmeras aplicações práticas e teóricas. [1] [2]

Diagrama de Voronoi de um Conjunto Aleatório de pontos no plano (todos os pontos estão contidos na imagem).

Caso Base

No caso base e nos casos mais familiares (mostrados na primeira figura), temos um conjunto finito de pontos {p1,...,pn} no Plano Euclidiano. Neste caso cada Sítio pk é meramente um ponto, e corresponde a uma Célula Voronoi (também chamada de Região Voronoi ou Célula Dirichlet) Rk consistindo em todos os pontos que possuem distância para pk menor do que a distância para qualquer outro Sítio. Cada Célula é obtida a partir da interseção de SemiEspaços e, portanto, é um Polígono Convexo. Os segmentos do Diagrama de Voronoi são todos os pontos do plano equidistantes aos dois Sítios Mais Próximos. Os Vértices (Nós) de Voronoi são os Pontos Equidistantes de três ou mais Sítios

Definição Formal

Seja X um Espaço (um conjunto não vazio) terminado com uma função Distância d (Um Espaço Métrico). Seja K um Conjunto de Índices e (Pk) k ∈ K sendo uma Enupla (Coleção Ordenada) de Subconjuntos não vazios (os Sítios) no Espaço X. A Célula Voronoi, ou Região Voronoi, Rk, associada ao Sítio Pk é o Conjunto de todos os pontos em X os quais a distância para Pk não é maior do que a distância para os outros Sítios Pj , onde j é qualquer índice diferente de k. Em outras palavras, se d(x,A)=inf{d(x,a): a ∈ A} (ver: inf = ínfimo) denota a distância entre o ponto x e o subconjunto A, então Rk={x ∈ X: d(x,Pk) ≤ d(x,Pj) para todo j≠k}. O Diagrama de Voronoi é simplesmente a Enupla de Células (Rk) k ∈ K . A princípio, alguns dos Sítios podem se cruzar e até coincidir (uma aplicação é descrita abaixo para os Sítios que representam Lojas), mas normalmente assume-se que são disjuntos. Além disso, Sítios infinitos são permitidos na definição (esta definição tem aplicações na Geometria dos Números e cristalografia), mas, novamente, em muitos casos apenas finitamente alguns Sítios são considerados.

 

No caso particular onde o Espaço é um Espaço Euclidiano de Dimensão Finita - quando a Base dete Espaço Vetorial possui um Número Finito de Elementos (Ver em Álgebra Linear os Espaços Vetorias) , cada Sítio é um ponto, há um número finito de pontos e todos eles são diferentes, então as células Voronoi são Polígonos Convexos que podem ser representados de uma forma Combinatória utilizando seus Vértices, os Lados, Faces 2-Dimensional, etc. Às vezes a estrutura Combinatória Induzida é referida como o Diagrama de Voronoi. No entanto, em geral, as Células de Voronoi podem NÃO serem Convexas ou mesmo NÃO estarem Conectadas (Conjuntos Conexos vistos em Espaços Métricos).

Ilustração

Como uma ilustração simples, considere um grupo de lojas em uma cidade plana. Suponha que queiramos estimar o número de clientes de uma determinada loja. Com todo o resto sendo igual (preço, produtos, qualidade de serviço, etc), é razoável supor que os clientes escolhem sua loja preferida, simplesmente por considerações de distância: eles vão para a loja com localização mais próxima a eles. Neste caso, a célula Rk de Voronoi de uma determinada loja de Pk pode ser utilizado para dar uma estimativa aproximada do número de potenciais clientes indo a esta loja (que é modelada por um ponto em nossa cidade plana).

 

Até agora pensava-se que a distância entre os pontos da cidade eram medidos utilizando-se a distância standard, ou seja, a Distância Euclidiana:                                                                                             . No entanto, se considerarmos o caso em que os clientes só vão para as lojas por um veículo e os caminhos de tráfego são paralelos aos eixos x e y, como na ilha de Manhattan, em seguida, uma função de distância mais realista será a Distância Retangular ou Metropolitana                                                                                  (vista em Modelagem Matemática e Logística Urbana um link pode ser, também, explorado de imediato, em Espaços Métricos a Generalização do Conceito de Mediatriz usando a Métrica Retangular). ² Ver, também, a Dissertação: 

 

 

Um Exemplo de Trabalho na Área de Logística Urbana:

 

Dissertação de Mestrado: 

DIMENSIONAMENTO E LOCALIZAÇÃO DE CENTRO DE DISTRIBUIÇÃO DE CORREIOS NUMA CIDADE DE

MÉDIO PORTE - Arquivo Formato ".PDF" - amanho do Arquivo = 2,60MB.

Outro Link: (UNIVERSIA) Página em HTML

Dissertação

Propriedades

  • O Grafo Dual para um Diagrama de Voronoi (no caso de um Espaço Euclideano com pontos em Sítios) corresponde a Triangulação de Delaunay para o mesmo conjunto de pontos.

  • O Par de Pontos Mais Próximo corresponde a duas Células Adjacentes do Diagrama de Voronoi.

  • Assuma um Cenário onde o Plano Euclideano e um Grupo de diferentes pontos são dados. Então, dois pontos são adjacentes no Fecho Convexo se, e somente se, suas Células Voronoi compartilham um Lado Infinitamente Longo.

  • Se o Espaço é Normalizado (Ver Espaço Vetorial Normado e/ou Espaço Vetorial com Produto Interno) e a distância para cada local é atingido (por exemplo, quando um Sítio é um Conjunto Compacto - em Espaço Vetorial de Dimenção Finita e/ou Isomorfo a R, R² , R³ e tc... Compacto é Equivalente a ser Fechado e Limitado, ou uma Bola Fechada), então cada Célula de Voronoi pode ser representada como uma União de Segmentos de Linha que emana dos Sítios [3] . Como mostrado lá, esta propriedade não é necessariamente válida quando a distância NÃO é atingida.

  • Em condições relativamente gerais (o Espaço é possivelmente um Espaço de Dimensão Infinita Uniformemente Convexo, podendo haver um Número Infinito de Sítios de uma forma geral etc.). As Células Voronoi desfrutam de um Propriedade com certa Estabilidade: uma pequena mudança nas formas dos sítios, por exemplo, uma mudança causada por alguma tradução ou distorção, produz uma pequena mudança na forma das células Voronoi - Um Modelo que se pode dizer ser ROBUSTO: Pequenas Pertubações não afetam a Estrutura Geométrica do Modelo. Esta é a Estabilidade Geométrica dos Diagramas de Voronoi [4] . Como mostrado lá, esta propriedade não se sustenta em geral, mesmo se o espaço é Bidimensional (mas não Uniformemente Convexo, e, em particular, não Euclidianos) e os sítios são pontos.

História

Uso informal de Diagramas de Voronoi têm como primeiro registro em 1644, por Descartes em 1644. Dirichlet utilizou 2-Dimensional e Diagramas 3-Dimensional Voronoi em seu estudo sobre Formas Quadráticas (Ver Funções Quadráticas:de uma Funções de uma Váriável Real) em 1850. O Médico Britânico John Snow utilizou também um Diagrama de Voronoi, em 1854, para ilustrar como a maioria das pessoas que morreram na Epidemia de Cólera Sohovivia mais perto da Bomba de Água de Broad Street do que de qualquer outra bomba.

 

Diagrama de Voronoi foi nomeado após o Matemático Russo Georgy Fedoseevich Voronoi (ou Voronoy) definir e estudar o caso n-Dimensional geral, em 1908. Diagramas de Voronoi que são utilizados em Geofísica e Meteorologia para analisar os dados Espacialmente Distribuídos (tais como as Medições de Chuva) - Ver Distribuições Espaciais - são chamados Polígonos de Thiessen graças aos estudos de aplicação do Meteorologista Americano Alfred H. Thiessen. Em Física da Material Condensada, como pavimentações, os diagramas são conhecidos como Células Unitárias de Wigner-Seitz. Diagramas de Voronoi da rede recíproca dos momentos são chamados dezonas de Zonas de Brillouin. Para reticulados gerais em Grupos de Lie, as células são simplesmente chamadas de Domínios Fundamentais. No caso de Espaços Métricos as Células são frequentemente chamadas de Polígonos Métricos Fundamentais.

Exemplos

Este é um pedaço do Diagrama de Voronoi de um Conjunto Aleatório de Pontos em uma Caixa 3D. Em geral, uma Seção Transversal de um Diagrama de Voronoi 3D não é um Diagrama de Voronoi em 2D em si. (todas as células são Poliedros Convexos.)

Diagramas de Voronoi de reticulados regulares de pontos em duas ou três dimensões dão origem a muitos diagramas familiares.

  • O Reticulado 2D nos dá um Diagrama de Favo de Mel Irregular, com Hexágonos iguais e pontos simétricos; no caso de uma Rede Triangular, é regular; no caso de uma Rede Retangular, os Hexágonos são reduzidos à Retângulos em Linhas e Colunas; uma Rede Quadrada nos dá um Diagrama Regular em forma de Mosaico; note que os Retângulos e os Quadrados também podem ser gerados por outras redes (por exemplo, a Rede definida pelos Vetores (1,0) e (1/2,1/2) produz Quadrados). Veja Aqui um Exemplo Visual Dinâmico (passe o Mouse sobre a Figura).

  • Uma Rede Cúbica 3D produz um Favo de Mel Cúbico.

  • Planos Paralelos com Redes Triangulares Regulares Alinhadas, com cada um alinhado com o Centro dos outros, produz um Favo de Mel Prismático Hexagonal (Ver Prisma).

  • Certos corpos centrados reticulados tetragonais produzem um diagrama do espaço com dodecaedro rhombo-hexagonal.

  • Um reticulado cúbico face-centrado produz um diagrama do espaço com dodecaedro r-hombic.

  • Um reticulado cúbico corpo-centrado produz um diagrama do espaço com octaedros truncados.

Para o conjunto de pontos (x, y) com x em um conjunto discreto X e y em um conjunto discreto Y, temos telhas retangulares com os pontos não necessariamente em seus centros.

Diagramas de Voronoi de Ordem Superior

Apesar de uma Célula de Voronoi normal ser definida como o Conjunto de pontos mais próximo de um único ponto em S, a e-nésima Ordem de Células de Voronoi é definida como o Conjunto de pontos com um determinado conjunto de n pontos em S contendo os VIZINHOS MAIS PRÓXIMOS de n. Diagramas de Voronoi de Ordem Superior também subdividem o Espaço. Diagramas de Voronoi de Ordem Superior podem ser gerados de Forma Recursiva. Para gerar o Diagrama de Voronoi da e-nésima Ordem do Conjunto S, comece com o Diagrama da Ordem (n − 1) e substitua cada Célula gerada por X = {x1, x2, ..., xn−1} pelo Diagrama de Voronoi gerado a partir do Conjunto S − X.

 

Diagrama de Voronoi do Ponto Mais Distante

Para um conjunto de n pontos o Diagrama de Voronoi de Ordem (n−1) é chamado de Diagrama de Voronoi de Ponto mais Distante.

Para um dado conjunto de pontos S = {p1, p2, ..., pn} o Diagrama de Voronoi de Ponto mais Distante divide o plano em células onde o mesmo ponto de P é o ponto mais distante. Note que o ponto de P possui uma Célula no Diagrama de Voronoi de Ponto mais Distante se, e somente se, este for um Vértice do Fecho Convexo de P. Portanto, seja H = {h1, h2, ..., hk} o Fecho Convexo (ou Fecho Convexo ) ou (Ver Fecho Convexo: Arquivo no Formato ".PDF") de P. 

Definição: Definimos o Diagrama de Voronoi de Ponto mais distante como a subdivisão do plano em k Células, uma para cada ponto em H, com a propriedade de que um ponto q que está na Célula correspondente a um Sítio hi se, e somente se, dist(q,hi) > dist(q,pj) para cada pj ∈ S com hi ≠ pj, onde dist(p, q) é a Distância Euclidiana                                                                                       entre dois pontos p e q. [5] [6]

Generalizações e Variações

Como implica a definição, as Células de Voronoi podem ser definidas para Métricas de Distâncias Não-Euclidianas (como a Distância de Mahalanobis ou Distância de Manhattan ou Geometria do Táxi ou A Geometria do táxi, considerada por Hermann Minkowski no Século XIX, é uma forma de Geometria em que a Usual Métrica da Geometria Euclidiana é substituída por uma nova Métrica em que a distância entre dois pontos é a Soma das Diferenças absolutas de Suas Coordenadas... - também chamada Metrica Retangular ou Métrica Metropolitana ou Distância Retangular dR                                                                              ). Entretanto, nestes casos, os Limites das Lélulas de Voronoi podem ser mais complexos do que nos casos Euclidianos, uma vez que o Lócus Equidistante de dois Pontos pode não ser um Subespaço de Co-Dimensão 1, mesmo no Caso 2-dimensional.

 

Um Diagrama de Voronoi Ponderado é aquele em que a Função de um par de Pontos para definir uma Célula Voronoi é uma Função Distância Modificada por Atribuição de Pesos aos Pontos Geradores. Diferentemente do caso das Células Voronoi definidas pela Distância Métrica, neste caso, algumas Nélulas Voronoi podem ser Vazias.

 

O Diagrama de Voronoi de n Pontos em um Espaço d-Dimensional requer Espaço de Armazenamento da Ordem de                 . Portanto, Diagramas de Voronoi muitas vezes não são viáveis para d > 2. Uma alternativa é utilizar Aproximação do Diagrama de Voronoi, onde as Células de Voronoi têm uma Fronteira Difusa, podendo ser aproximada. [7]

 

Diagramas de Voronoi também estão relacionados com outras Estruturas Geométricas como o Eixo Medial - Ver Arquino no Formato ".PDF" (que tem encontrado aplicações em Segmentação de Imagens - Ver Arquivo no Formato ".PPT" ou Ver Segmentação de Imagens Arquivo no Formato ".PDF", Reconhecimento Óptico de Caracteres e outras aplicações computacionais) e o Esqueleto Reto.

Aplicações

  • Uma das aplicações primeiras aplicações do Diagrama de Voronoi foi por John Snow para estudar a epidemia de cólera no bairro londrino do Soho em 1854, localizado na Inglaterra. Ele mostrou a correlação entre áreas do mapa de Londres e as áreas com mais mortes devido ao surto, utilizando uma bomba de água particular.

  • Uma estrutura de dados de localização de pontos pode ser construída através do Diagrama de Voronoi, a fim de responder a questões como o Vizinho mais próximo ou o objeto que está mais próximo de um ponto de determinada consulta. Consultas a vizinho mais próximo têm inúmeras aplicações. Por exemplo, encontrar o hospital mais próximo (Ver Modelagem Matemática Aplicada à Logistica Urbana) ou o objeto mais similar em um Banco de Dados. Uma aplicação importante é a quantização vetorial, comumente utilizada em compressão de dados.

  • Com um determinado Diagrama de Voronoi, pode-se também encontrar o Maior Círculo Vazio dentre um conjunto de pontos em um polígono abrangente; por exemplo, para construir um novo supermercado o mais distante possível dos demais supermercados existentes, em uma determinada cidade plana.

  • Diagramas de Voronoi juntamente com Diagramas de Voronoi de Ponto mais Distante são utilizados em Algoritmos eficientes para calcular o Arredondamento de Pontos. [5]

  • Diagrama de Voronoi é útil em Física de Polímeros. Pode ser utilizado na representação do Volume Livre do Polímero.

  • Também é utilizado em Derivações da Capacidade de uma Rede Sem Fio.

  • Em Climatologia, Diagramas de Voronoi são utilizados para calcular a Precipitação de uma Área, com base em uma série de medições pontuais. Neste caso, geralmente referenciados como Polígonos Thiessen.

  • Diagramas de Voronoi são utilizados para estudar os Padrões de Crescimento das Florestas. Também pode ser útil no desenvolvimento de Modelos Preditivos para Incêndios Florestais.

  • Diagramas de Voronoi também são utilizados em Computação Gráfica para Gerar Alguns Tipos de Texturas Orgânicas.

  • Em Robótica Autônoma de Navegação (Ver Arquivos 01