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 e  02 no Fomato ".PDF") Diagramas de Voronoi são utilizados para Encontrar Rotas Livres. Se cada obstáculo do percurso for representado por um ponto, então as bordas do diagrama serão as rotas mais distantes dos obstáculos (afastando assim, em teoria, o risco de colisões).

  • Em Química Computacional, as Células Voronoi definidas pelas posições dos núcleos em uma molécula são usadas para Calcular Cargas Ctômicas. Isto é feito utilizando o Método de Densidade de Deformação de Voronoi.

  • Na Ciência dos Materiais, Microestruturas Policristalinas em Ligas Metálicas são geralmente representadas utilizando Diagramas de Voronoi.

  • Polígonos de Voronoi têm sido utilizados na Mineração, para Estimas as Reservas de Materiais Valiosos, minerais e outros recursos. Os pontos onde já ocorre a exploração são utilizados como o conjunto de pontos nos Polígonos de Voronoi.

Veja também

Algoritmos

 

Related Subjects

Notas e Referências

  1. Franz Aurenhammer (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991

  2. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages 

  3. Daniel Reem, An algorithm for computing Voronoi diagrams of general generators in general normed spaces, In Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009), 2009, pp. 144--152

  4. Daniel Reem, The geometric stability of Voronoi diagrams with respect to small changes of the sites, Full version: arXiv 1103.4125 (2011), Extended abstract in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254-263

  5. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry. Third edition ed. [S.l.]: Springer-Verlag, 2008. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

  6. Skyum, Sven. (1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters 37(1991)121-125., Contains a simple algorithm to compute the Farthest-Point Voronoi Diagram.

  7. S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams (Arquivo no Formato ".PDF"), Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.

Bibliografia

  • Gustav Lejeune Dirichlet (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die Reine und Angewandte Mathematik, 40:209-227.

  • (1908) "Nouvelles applications des paramètres continus à la théorie des formes quadratiques". Journal für die Reine und Angewandte Mathematik 133: 97-178.DOI:10.1515/crll.1908.133.97.

  • Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages ISBN 0-471-98635-6

  • (1991) "Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys 23: 345-405. DOI:10.1145/116873.116880.

  • (1981) "Computing Dirichlet tessellations". The Computer Journal 24: 162-166. DOI:10.1093/comjnl/24.2.162.

  • (2009) "An algorithm for computing Voronoi diagrams of general generators in general normed spaces". Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009): 144—152. DOI:10.1109/ISVD.2009.23.

  • Daniel Reem (2011). The geometric stability of Voronoi diagrams with respect to small changes of the sites. Full version: arXiv 1103.4125 (2011), Extended abstract: in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254-263.

  • (1981) "Computing the n-dimensional tessellation with application to Voronoi polytopes". The Computer Journal 24: 167-172. DOI:10.1093/comjnl/24.2.167.

  • Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry. 2nd revised edition ed. [S.l.]: Springer-Verlag, 2000. ISBN 3-540-65620-0 Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.

  • Rolf Klein. Abstract voronoi diagrams and their applications. [S.l.]: Springer-Verlag, 1989. 148—157 p. vol. 333. ISBN 3540520554

Ligações Externas

Categorias: 

_________________________________

(1) Em problemas de LOGÍSTICA [ver, por exemplo, 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 (se A1 é um ponto que representa, por exemplo, o local de um acidente e Q1, Q2 e Q3 são as localizações de hospitais, então este acidente deve ser atendido pelo hospital mais próximo). Depois de termos achado as mediatrizes, podemos ver que o hospital mais próximo de A1 é Q1. Isto é, a região R ficou dividida em três sub-regiões R1, R2 e R3, segundo o critério do vizinho mais próximo. Continue a leitura!

(2) Em problemas de LOGÍSTICA [ver, por exemplo, 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 (se A1 é um ponto que representa, por exemplo, o local de um acidente e Q1, Q2 e Q3 são as localizações de hospitais, então este acidente deve ser atendido pelo hospital mais próximo). Depois de termos achado as mediatrizes, podemos ver que o hospital mais próximo de A1 é Q1. Isto é, a região R ficou dividida em três sub-regiões R1, R2 e R3, segundo o critério do vizinho mais próximo.

  

Mostraremos, num segundo momento, a relação estreita entre DIAGRAMA DE VORONOI e o problema de subdividir uma dada região R segundo o Critério do Vizinho mais Próximo -  essas subdivisões neste contexto do DIAGRAMA DE VORONOI (uma Malha não Estruturada) são denominadas de Células: Trataremos isso na Área de SIMULAÇÃO DE SISTEMAS. Falaremos  com mais detalhes sobre trabalhos envolvendo DIAGRAMA DE VORONOI: Um exemplo é o trabalho de Pesquisa no Laboratório de Simulação do Departamento de Engenharia Mecânica da Universidade Federal de Santa Catarina – UFSC. Neste trabalho foi desenvolvido um Algoritmo para fazer as subdivisões da região dada segundo um número dado de pontos dentro desta região (um Toro) utilizando a Métrica Euclidiana – o Algoritmo é iterativamente repetido onde dentro de casa sub-região é inserido o mesmo número de pontos da iteração anterior. O algoritmo tem uma regra de parada quando a malha fica mais refinada ao nível desejado pelo Programador utilizando na época 1993 uma Estão de Trabaho. (o comum na época eram os Pcs da família XT 640kb de memória!)

 

As dificuldades encontradas quando se deseja Implementar (Programar) Computacionalmente no caso particular quando a Métrica envolvida é a Métrica Retangular - isto é de grande valia em Logística Urbana (vide Área MODELAGEM MATEMÁTICA APLICADA À LOGÍSTICA URBANA) não são diferentes das que utilizadas quando a métrica é a Métrica Euclidiana: Basta definir computacionalmente o que é graficamente uma mediatriz tanto utilizando a Métrica Euclidiana bem como a Retangular – é dizer para o computador o que ele tem que intender por mediatriz: é puramente gráfica a explicação, ou seja é uma linha com ângulo de 90o que o Algoritmo tem que desenhar  passando pelo meio do segmento que se pretende obter a mediatriz. Lembrando o que já comentamos em outra seção que resolver Analiticamente o problema do Vizinho mais Próximo usando a  Métrica Retangular é trabalhoso - é quase impossível resolver "a mão" o significativo número de equações quando a região dada R apresenta um número grande de pontos Ai.

Vide Trabalhos e Artigos dos “Professores: Clóvis Maliska e seu filho Clóvis Maliska JR.” do Laboratório de Simulação Numérica em Mecânica dos Fluidos (observação: Aqui, em Mecânica dos Fluidos, a Área da MATEMÁTICA PURA denominada de Variáveis Complexas têm dada significativa contribuição - veremos mais adiante... em Tópicos de Variáveis Complexas) e Transferência de Calor.

 

E para quem tem interesse no assunto de DIAGRAMA DE VORONOI é bom saber que a Área da MATEMÁTICA PURA denominada de Topologia está presente em todos estes estudos em Mecânica dos Fluidos e Transferência de Calor – no Laboratório são criados grupos que se reúnem para o estudo paralelo em TOPOLOGIA! Cada ponto das Células na Malha de Voronoi tem uma informação (valor da função que descreve, por exemplo, a condutibilidade de calor) sobre o fenômeno em estudo – na simulação é possível ver, por exemplo, a superfície de um Toro (Em Geometria Diferencial - Área da MATEMÁTICA PURA, é uma Superfície Parametrizada Regular) mudando de cores (vermelho=bem quente, e assim por diante) conforme a simulação se processa! São resolvidos problemas topológicos (relativos à Topologia) quando se tratam superfícies que não são Convexas – um problema que ocorre nas fronteiras ao se cortar um tipo específico de superfície onde pontos que eram Pontos Interiores acabam se tornando em Pontos de Fronteira! Aí reside a vantagem de se trabalhar com Malhas não estruturadas ao invés de Malhas Estruturadas (Células Enumeráveis).

Voltar para COMPUTAÇÃO: Disciplinas!

  A partir de 20 Out de 2020

Você é o Visitante de Número

Nosso CANAL

bottom of page