Dado um conjunto de p1,...,pn de pontos no plano, queremos construir um diagrama de Voronoi varrendo uma uma linha horizontal entre os pontos, mantendo o que foi visto ao longo do caminho.
Para isso, precisamos usar uma estratégia adicional envolvendo parábolas. Parábolas são úteis para este problema de linha de varredura porque para qualquer ponto pi, há uma parábola separando pi da linha de varredura de tal maneira que cada ponto da parábola é eqüidistante tanto de p quanto da linha de varredura. Assim, quando a linha de varredura atinge um novo ponto de pj, sabemos, com base na parábola associada com cada ponto, qual é o ponto médio entre pi e pj.
O algoritmo irá varrer uma linha horizontal de baixo para cima, criando uma parábola para cada ponto, tal que para cada posição da linha de varredura, cada ponto é o foco de sua parábola e a diretriz da parábola é a própria linha de varredura. A parábola se torna mais aberta a medida que a linha de varredura avança para o topo do plano
Figura 1
Em qualquer fase do processo, o algoritmo assemelha-se o que vemos na Figura 2.
Figura 2
Acima da a linha de varredura está um conjunto de sites não visitados, e todos os sites abaixo da linha de varredura já foram visitados pelo algoritmo. Os arcos mais próximos da linha de varredura criar uma "fronteira de onda" (wavefront), bloqueando a vista de outros arcos. Os pontos na "fronteira da onda" onde os arcos se encontram são chamados de pontos de interrupção, e note que cada ponto de interrupção é equidistante de seus correspondentes locais. Cada ponto já ultrapassado pela "fonteira da onda" é conhecido por pertencer a uma região específica de Voronoi.
Considere as seguintes observações:
- Com o avanço da linha de varredura, um novo arco (de alguma parábola) é adicionado para a "fronteira da onda" somente quando a linha de varredura toca algum site. Isto é chamado de evento de site.
- A única maneira que um arco desaparecer a partir da frente de onda é quando dois arcos adjacentes de cruzam em um ponto comum. Chamamos a isto um evento de círculo
Estrutura de Dados
estruturas de dados para armazenar as informações recuperadas durante todo o processo.
A primeira estrutura de dados será uma árvore binária balanceada T usado para armazenar a "fronteira da onda". As folhas da árvore serão os arcos que compõem a "fronteira da onda" e os nós internos de T serão os pontos de interrupção (interseções de arcos).
Precisamos ser capazes de realizar as seguintes operações em T:
- Inserções: quando um novo arco for adicionado na "fronteira da onda"
- Deleções: quando um arco tornar-se invisível para a linha de varredura e não fizer mais parte da "fronteira da onda"
- Busca: Para qualquer linha vertical que quisermos saber qual arco cruza.
A segunda estrutura de dados que queremos usar é uma fila de prioridade Q para armazenar os eventos encontrados. As operações que nós gostaríamos de usar são os seguintes:
- Inserção: para incluir novos eventos quando ocorrerem no processo
- Deleção: depois de processar o evento, ele não mais é necessário e deve ser excluído
- Sucessor: após processar um evento, devemos processar o evento seguinte na fila baseado na posição do ponto na coordenada Y
Complexidade
No pior caso, existem 2n -1 arcos na "fronteira de onda" ao mesmo tempo. Isto ocorre quando cada arco está sobre a "fronteira de onda", mas um é dividido por outro arco da "fronteira de onda"). Então a árvore balanceada contém O(n) elementos. Como cada operação que queremos realizar em T leva não mais que tempo O (log n) e não há mais que n elementos na árvore, cada operação realizada na estrutura de dados do status da "fronteira de onda" é limitada a tempo O (log n).
Notamos que os eventos de círculo só podem ocorrer com três arcos consecutivos. Assim, em uma fila no máximo n sites lá nunca irá ocorrer mais do que n-2 eventos de círculo. Mais uma vez nossa fila tem n elementos, e assim cada uma das operações leva não mais que
tempo O(log n).
Porque há um número constante de eventos de site em Q e cada operação leva uma quantidade constante de tempo, vemos que o algoritmo de varredura de linha para determinar o diagrama de Voronoi em um conjunto de n pontos é executado em tempo de O (n log n).
Pseudo-código
Entrada: um conjunto P = (p1,p2,...pn) pontos no plano
Saida: O Diagrama de Voronoi Vor(P)
1. Inicialize uma fila de prioridade Q com eventos de site ordenados em ordem crescente pela coordenada x; inicialize uma estrutura de árvore balanceada vazia T
2. Enquanto Q não estiver vazia
(a) capture o próximo evento q fora de Q de menor coordenada Y
(b) se q é um evento de site X:
i. Se T estiver vazio, insira q em T e retorne, senão faça os passos ii a iv
ii. Encontre o arco B que cruza a parábola X criada pela "fronteira de onda" e o site x
iii. Insira uma nova parábola em T e divida a parábola (B) que está cortada em duas partes. Reequilibre T se necessário
iv. Atualize Q pela deleção do evento de círculo que já não é alcançavel baseado no corte da "fronteira de onda" (ABC) e pela inserção dos três novos eventos de círculos possíveis criados pelo novo evento de site (A-B1-X, B1-X-B2, X-B2-C)
i. Grave o Vértice de Voronoi
ii. Delete o arco que desapareceu de T
iii. Atualize Q devido a deleção de 3 novos eventos de círculos impossíveis (A-B-x, B-x-D, x-D-E) e insira os dois novos eventos de círculo possíveis A-B-D, B-D-E).
Nenhum comentário:
Postar um comentário