Diagrama de Voronoi

O Diagrama de Voronoi foi inventado para resolver um problema simples: Como dividir uma cidade em áreas irregulares de forma a que a área coberta por um carteiro vinculado a uma determinada agência de correio seja otimizada?

G. F. Voronoi, em sua tese de doutorado entitulada Sobre uma generalização do algoritmo de quebra de cadeias publicada em Varsóvia, Polônia, em 1896, desenvolveu um método onde, com base em uma triangulação pré-existente de pontos que representam os centros de alguma coisa (no caso da primeira aplicação, agências de correio), se determina qual a área de influência de cada um destes centros em função da posição dos outros centros, delimitando de forma geométrica cada área de influência.

O diagrama de Voronoi é um  método que muito útil para reconhecimento de padrões para delimitar as áreas de categorias ou classes em uma representação geométrica de suas distribuições.

Os “centros” são denominados de centróides. Se existe um conjunto de padrões constituído de um elemento típico para cada categoria que queremos representar (protótipo), pode-se  utilizar o diagrama de Voronoi para determinar a extensão de cada uma das categorias, apenas utilizando cada um dos protótipos como um centróide e gerando um diagrama de Voronoi sobre estes.

Para podermos gerar um diagrama de Voronoi partimos do conjunto de protótipos e geramos primeiramente uma triangulação. Para isto utilizamos o método da Triangulação de Delaunay, que veremos em detalhe adiante. Na figura 1, a triangulação está em vermelho.

Figura 1 - Triangulação de Delaunay

Realizada a triangulação, geramos as linhas que formarão as fronteiras das células do diagrama de Voronoi. Estas fronteiras são geradas por linhas perpendiculares ao ponto médio de cada aresta da triangulação produzida anteriormente. As intersecções destas perpendiculares formam os vértices das células do diagrama de Voronoi. Os segmentos de reta da perpendicular que se estendem para além de sua primeira intersecção com outra perpendicular nos dois sentidos são descartados.

Estruturas Geométricas:

Região de Voronoi 

• Vor(p)
• Coleção de pontos bidimensionais, onde todos os pontos estão mais perto do vértice p do que de qualquer outro vértice no grafo. 
• Diagrama de Voronoi é a união de todas as regiões de Voronoi do grafo
• Triangulação de Delaunay está relacionada com Diagrama de Voronoi
• Dois vértices p e q estão conectados em Del(V) apenas se Vor(p) e Vor(q) compartilham uma mesma borda

Triangulação de Delaunay

• Del(V)
• Assume que nenhum 4 vértices são co-circulares 
• Triangulação é de Delaunay se o circulo circunscrito de cada um de seus triângulos não contém outro vértice em seu interior

Passo-a-passo para criação do Diagrama de Voronoi.

Passo 1: Determinação dos pontos para os triângulos (Triangulação de Delaunay) 

Tome sua distribuição de dados e encontre todos os triângulos definidos por três pontos da distribuição, de tal forma que um círculo passando por estes três pontos não inclua nenhum outro ponto.

 Passo 1

Passo 2: Determinação dos triangulos (Triangulação de Delaunay)

Para cada conjunto de três pontos satisfazendo a condição de Delaunay encontrado, gere um triângulo.

Passo 2

Passo 3: Determinação das células (Diagrama de Voronoi)

P.3.1. Determine o ponto médio de cada uma das arestas do conjunto de triângulos gerado anteriormente. Considere cada aresta apenas uma vez.
P.3.2. Gere uma linha perpendicular a cada uma das arestas.
P.3.3. Determine as duas intersecções mais próximas de cada aresta com duas outras arestas. Um intersecção para cada lado. Ignore os segmentos de reta que seguem para além das intersecções.
P.3.4. Forme as células do diagrama com os polígonos formados por segmentos adjacentes. Ciclos geram células internas, polígonos abertos células externas.

Passo 3