Mostrar código-fonte de Algoritmos para construção do diagrama de Voronoi

{{Wikificação|data=setembro de 2014}}
== Algoritmo Naive ==

O [https://web.archive.org/web/20130606020627/http://wcipeg.com/wiki/Naive_algorithm algoritmo naive] ou ingênuo para a construção do [[diagrama de Voronoi]] é o método mais simples e fácil de se ser provado, porém ineficiente, a partir disso, foram realizadas muitas pesquisas no campo da geometria computacional para fazer algoritmos eficientes.

=== Definição ===

----

Dado um conjunto de dois ou mais, mas um número finito, de pontos distintos no espaço euclidiano, associamos todos os locais em que o espaço com o membro mais próximo(s) do ponto de ajuste em relação ao distância euclidiana. O resultado é uma camada do plano em um conjunto de regiões associadas com os membros de um conjunto de pontos. Chamamos isso de diagrama de Voronoi ordinário planar gerado pelo conjunto de pontos, e as regiões que constituem o diagrama de Voronoi de  polígonos de Voronoi ordinários.

Seja  <math>P</math> = {<math>p_1, p_2,...,p_n</math>} contido em <math>R^2</math>, onde 2 &le; n &le; &infin; e <math>x_i</math> &ne; <math>x_j</math> para '''i, j''' pertencente a <math>I_n</math> . Chamamos a região <math>V(p_i)</math> = &cap; <math>H (p_i, p_j</math>).

O polígono de Voronoi ordinário associado com <math>p_i</math> e o conjunto <math>V(P</math>) =  {<math>V(p_1</math>), <math>V(p_2</math>), … , <math>V(p_n)</math>} o diagrama de Voronoi ordinário plano gerados por  <math>P</math>.

=== Construção ===

----

Seja  <math>P</math> = {<math>p_1, p_2,..., p_n</math>}  o conjunto de geradores, e <math>V</math> = {<math>v_1, v_2,..., v_n</math>} denota o diagrama de Voronoi para <math>P</math>. A construção do diagrama é o procedimento para a geração <math>V(p)</math>. A partir da definição que vimos do Diagrama de Voronoi ordinario a partir de meios planos é possível criar um método ingénuo para a construação do diagrama.

O polígono de Voronoi para o <math>p_i</math> gerador é a intersecção de todos os planos definidos por meio das meadiatrizes de <math>p_i</math> e dos outros geradores. Assim podemos construir os polígonos de Voronoi um por um que serão no final o Diagrama de Voronoi a partir do seguinte método:

=== Algoritmo ===

----

'''Método Naive:'''

'''VORONOI_DIAGRAM'''<ref>{{Citar periódico
| ultimo = Okabe
| primeiro = A.
| ultimo2 =Hoey
| primeiro2 =D.
| ultimo3 =Boots
| primeiro3 =B.
| ultimo4 = Sugihara
| primeiro4 =K.
| ano = 1992
| titulo = Spatial Tessellations, Concepts and Applications of Voronoi diagrams
| editora = Wiley
| local = England
}}</ref>

*'''ENTRADA:''' ''n'' geradores <math>p_1, p_2,..., p_n</math>.
*'''SAÍDA:''' Diagrama de Voronoi <math>V</math> = {<math>V(p_1), V(p_2)</math>}

::*  Passo 1: Para cada ''i'' sendo ''i'' = 1,2, . . . , ''n'', gerar ''n-1'' planos intermediários  <math>H(p_1, p_2)</math> , 1 &le; j &le;n, j &ne; i , e assim construir sua intersecção em comum <math>V(p_i)</math>.

::*Passo 2: Retorna {<math>V(p_1), V(p_2),</math> … ,<math> V(p_n)</math>} todas as intersecções a partir dos geradores.

=== Avaliação do método naive ===

----

O método naive não pode ser chamado de 'algoritmo' prático, porque é "insuficiente".

Para avaliar um algoritmo, temos que considerar pelo menos se ele é correto e sua eficiência, e se se tratando de computação numérica, nós também temos que considerar robustez contra erros numéricos. O método acima é correto, porque é uma atualização da definição do [[diagrama de Voronoi]]. Assim, consideramos os outros dois aspetos.

==== Eficiência do método naive ====
----
Primeiro vamos avaliar a eficiência. Para construção de um plano intermediário H (p<sub>i</sub>, p<sub>j</sub>) para dois pontos dados p<sub>i</sub> e p<sub>j</sub> requer tempo constante. Assim, para cada p<sub>i</sub> o tempo necessário para a construção de um n-planos  é proporcional a n-1, por exemplo <math> a(n - 1)</math>, onde <math>a</math> é uma constante positiva. Para construir a intersecção dos planos, vamos considerar o seguinte procedimento:

:Primeiro, construir a interseção de dois planos, obtendo um polígono com dois lados.

:Depois construir a interseção deste polígono com o terceiro plano.

Na k-ésima etapa  deste procedimento, temos que encontrar a interseção de um polígono k lados (no pior dos casos) com outro plano, e o tempo desta etapa é pelo menos proporcional ao k, se verificarmos se cada um dos lados de k cruza a linha limite do plano. Esta construção da intersecção dos planos n-1 requer tempo proporcional a <math>1 + 2 + ... + n-2 = (n-2)* (n-1) / 2</math>, dizem <math> b * (n-2) (n-1)</math>  em que <math>b</math> é uma outra constante positiva. Temos que repetir esse processo para todos os geradores, e, consequentemente, o tempo total exigido pelo método ingênuo é:

<center><math>T (n) = n {a (n - 1) + b (n-2) (n-1)} = O (n ^ 3)</math>.</center>

Isto significa que, para um programa de computador com base no procedimento acima, o tempo para o processamento torna-se oito vezes maior do que o tamanho da entrada e torna-se o dobro do tamanho.

Empregando uma técnica pouco mais sofisticada, podemos construir a interseção de n-1 planos em <math>O (n log n)</math><ref>{{Citar livro
| ultimo = Shamos
| primeiro = M. I.
| ultimo2 = Preparata
| primeiro2 = Franco P.
| ano = 1985
| titulo = Computational Geometry An Introduction
| editora = SPRINGER VERLAG NY
}}</ref>. Por isso, a complexidade de tempo do método naive pode ser reduzida para <math> O (n ^ 2 n log)</math>

Existem outros algoritmos para construção do diagrama de Voronoi que requerem pelo menos <math>O (n log n)</math> no pior caso, e pelo menos <math>O(n)</math>, em média. Além disso, existem algoritmos cuja complexidade de tempo atinge estes limites, e alguns deles, na verdade, tem tempo de execução muito curto, mesmo para pequenos valores de n (embora a própria ordem representa o comportamento do algoritmo que n se aproxima do infinito). Em comparação com estes algoritmos, o algoritmo naive não é muito satisfatório do ponto de vista de complexidade de tempo.

==== Robustez do método naive ====
Outro ponto de suma importância de vista para avaliar o algoritmo é a robustez contra erros numéricos. Sob este ponto de vista também o método naive não é satisfatório. Isso pode ser entendido através do seguinte exemplo:
Suponha-se que há apenas quatro geradores P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub> e P<sub>4</sub> e eles estão muito próximos de um círculo em comum. Então as três bissetrizes entre p1 e os outros mais próximos geradores passam para o centro do círculo.
Se o erro numérico ocorre, é difícil decidir as posições relativas dos pontos de interseção dessas [[mediatriz]]es. Por isso, o resultado da intersecção dos três planos associados a P<sub>1</sub> pode ser um polígono de dois lados ou um polígono de três lado, dependendo o número de erros numéricos. Os outros três polígonos de Voronoi têm instabilidade similar. No método naive, cada polígono de Voronoi é calculado de forma independente, de modo que o resultado poderá tornar-se inconsistente topologicamente.
De um ponto de vista teórico, todos os polígonos de Voronoi um mosaico dos planos, mas no cálculo real a saída do método naive, não proporciona necessariamente um mosaico dos planos. Assim, o método naive, se traduzido para um programa de computador de uma maneira simples, não é robusto contra erros numéricos. Sua produção pode ser inconsistente topologicamente. Precisamos de uma análise cuidadosa, a fim de fazer um algoritmo numericamente robusto.
O método naive, apresentado acima, é um dos métodos mais fáceis de compreender, porque é uma tradução direta da definição do diagrama de Voronoi. Este método não é recomendado para propósitos gerais, ele pode ser usado para alguns tipos especiais de simulação onde o objetivo não é construir o próprio diagrama de Voronoi, mas para gerar muitas amostras de polígonos de Voronoi para obter dados estatísticos, tais como a distribuição do número de arestas por polígono.
Portanto a saída do método ingênuo é uma coleção de polígonos de Voronoi, e ele não inclui informações explícitas sobre a estrutura topológica do diagrama. Para extrairmos vários tipos de informação a partir do diagrama de Voronoi, o método ingênuo não é adequado.

=== Bibliografia ===
*{{Citar livro |primeiro=A.

|ultimo=Okabe

|título=Spatial Tessellations, Concepts and Applications of Voronoi diagrams

|editora=Wiley|língua=en|ano=1992

|local=Londres}}

*{{Citar livro

|primeiro=Sacristán.

|ultimo=Vera

|título=Computational Geometry - Algorithms for constructing Voronoi diagrams

|local=Espanha

|url=http://www-ma2.upc.es/~geoc/construccio_voronoi_EN.pdf

|acessodata=2014-09-04

|arquivourl=https://web.archive.org/web/20140904120346/http://www-ma2.upc.es/~geoc/construccio_voronoi_EN.pdf

|arquivodata=2014-09-04

|urlmorta=yes

}}

Algoritmos para a construção de Diagramas de Voronoi

== Algoritmo Incremental ==
 
O algoritmo incremental para a construção de diagramas de Voronoi foi proposto por  Peter Green e Robin Sibson  em 1978<ref>{{citar livro
  | autor      = GREEN, P. J., AND SIBSON, R.
  | título     = Computing Dirichlet tessellation in the plane.
  | língua     = en
  | editora    = The Computer Journal 21
  | data       =  2 de maio de 1978
|ref=harv}}</ref>.
Este algoritmo gasta tempo <math>O(n)</math> para cada inserção de ponto, para uma complexidade total de <math>O(n^2)</math>.<ref name="Joseph">{{Citar livro|nome=Joseph|sobrenome= O'Rourke|título=Computational Geometry in C|editora= Cambridge University Press|ano=1988|páginas=376|isbn=0521649765}}</ref> Apesar de ter complexidade quadrática, é um método simples e popular para a construção de diagramas de Voronoi.<ref name="Joseph"/>

===Descrição===

Este algoritmo começa com um Diagrama de Voronoi <math>V(p_n)</math> para um dado conjunto <math>p_n</math> de pontos <math>n</math>. Novas arestas são construídas à medida que novos pontos são adicionados. A ideia básica é construir um polígono de Voronoi para um novo ponto <math>p_{n+1}</math> que é adicionado ao conjunto de pontos <math>p</math>. As etapas do algoritmo estão descrito a seguir <ref>{{Citar livro|nome=Nabil R., Aryya|sobrenome= Adam, Gangopadhyay|título=Database Issues in Geographic Information Systems|editora= Kluwer Academic Publishers|ano=1997|páginas=156|isbn=0792399242}}</ref>:

[[Imagem:Figura 1..png|thumb|Etapas do algoritmo incremental.]]

A) O primeiro passo é identificar o ponto <math>p_i</math> cujo polígono de Voronoi contém o ponto <math>p_{n+1}</math>. <br />
B) Construa uma mediatriz do segmento <math>p_{n+1}p_i</math> o qual interceta o <math>V(p_n)</math> em <math>q_i</math> e <math>q_{i+1}</math>, respectivamente.<br />
C) Assumindo que <math>q_iq_{i+1}</math> é orientado no sentido anti-horário, adicione uma mediatriz do segmento <math>p_{n+1}p_{i+1}</math> no polígono de Voronoi adjacente ao ponto <math>q_{i+1}</math>.<br />
D) Os passos B e C são repetidos até que o ponto <math>q_i</math> for revisitado.<br />
E)  Neste ponto, o polígono de Voronoi para o ponto <math>p_{n+1}</math> é obtido.<br />
F) O novo Diagrama de Voronoi <math>V(p_{n+1})</math> é obtido pela remoção da subestrutura dentro do polígono de Voronoi para <math>p_{n+1}</math>.

[[Imagem:Figura 2..png|thumb|Exemplo do algoritmo incremental.]]

===Exemplo===
Seja o conjunto de pontos <math>p_1</math>, <math>p_2</math> e <math>p_3</math>. Se um ponto <math>p_4</math> é adicionado ao conjunto, <math> p_2</math> deve ser escolhido como o ponto inicial para a construção do novo diagrama de Voronoi (DV), uma vez que o polígono de Voronoi que contém  <math>p_2</math> contém <math>p_4</math> e é o mais próximo deste último. Uma mediatriz que corta o segmento <math>p_4p_2</math> é adicionada, a qual intercepta o DV nos pontos <math>q_1</math> e <math>q_2</math>. Similarmente, mediatrizes que cortam <math>p_4p_3</math> e <math>p_4p_1</math> são desenhadas as quais interceptam o polígono de Voronoi de <math>p_3</math> em <math>q_2</math> e <math>q_3</math>, e aquele de <math>p_1</math> em <math>q_3</math> e <math>q</math>. O novo DV é obtido removendo a subestrutura interna do novo polígono de Voronoi formado.

== Divisão e conquista ==
O primeiro [[algoritmo]] a utilizar o paradigma computacional da [[divisão e conquista]] para construção de [[Diagrama de Voronoi|Diagramas de Voronoi]], foi proposto por Shamos e Hoey<ref>{{Citar periódico
 | ultimo = Shamos
 | primeiro = M. I.
 | ultimo2   = Hoey
 | primeiro2 = D.
 | data = Outubro 1975
 | titulo = Closest-point problems
 | paginas = 151-162
 | local = Found. Comput. Sci. 16th Annu. IEEE Sympos
 | issn = 0272-5428
 | doi = 10.1109/SFCS.1975.8
 }}</ref> em 1975. Foi também o primeiro algoritmo a computador os diagramas com [[Complexidade computacional|complexidade]] <math>O(nlogn)</math> no pior dos casos.

=== Descrição ===
O algoritmo considera um conjunto <math>S</math> de <math>N</math> pontos divididos em dois subconjuntos <math>S_E</math> e <math>S_D</math>, cada um contendo <math>N/2</math> pontos, de tal modo que cada ponto de <math>S_E</math> encontra-se à esquerda de qualquer ponto de <math>S_D</math>.

Assumindo que já possuímos os diagramas de Voronoi <math>V(S_E)</math> e <math>V(S_D)</math>, construídos recursivamente, a etapa de união dos diagramas é realizada traçando-se uma reta poligonal <math>P</math>, também conhecida como cadeia divisória, que divide ambos conjuntos de pontos verticalmente. Essa cadeia possui a propriedade de que cada reta horizontal intersecta <math>P</math> exatamente em um único ponto, uma vez que toda linha poligonal que separa dois conjuntos disjuntos em x é monótona em y<ref>{{Citar periódico
 | ultimo = Shamos
 | primeiro = M. I.
 | ano = 1975
 | titulo = Computational Geometry
 | local = PhD. Thesis, Yale University
 }}</ref>.

A cadeia <math>P</math> faz um percurso sobre o [[lugar geométrico]] equidistante de algum ponto de <math>S_E</math> e algum ponto de <math>S_D</math>. Basicamente, o caminho percorrido acaba formando segmentos de reta pertencentes a uma fronteira comum de uma região de um certo ponto de <math>S_E</math>, com a região um certo ponto de <math>S_D</math>. Visto isso, <math>P</math> forma as novas arestas do diagrama de Voronoi <math>V(S)</math> dado por. <math>V(S_E)\cup V(S_D)</math>.

Após a construção de <math>P</math>, a união está praticamente concluída, sendo necessário apenas eliminar parte das arestas de <math>V(S_E)</math> e <math>V(S_D)</math> que cruzam <math>P</math>.

=== Como computar a cadeia divisória ===
{{multiple image
| align = right
| direction = horizontal
| header    = Demonstração da cadeia divisória
| width     = 200

| image1 = Diagrama de Voronoi E D.png
| alt1 =
| caption1 =

| image2 = Fecho Convexo E e D.png
| alt2 =
| caption2 =
}}
{{multiple image
| align = right
| direction = horizontal
| width     = 200

| image1 = Cadeia divisoria 1.png
| alt1 =
| caption1 =

| image2 = Cadeia divisoria 2.png
| alt2 =
| caption2 =
}}

{{multiple image
| align = right
| direction = horizontal
| width     = 200

| image1 = Cadeia divisoria 3.png
| alt1 =
| caption1 =

| image2 = Diagrama de Voronoi.png
| alt2 =
| caption2 =
}}
A essência do algoritmo está na construção da reta poligonal <math>P</math>. Podemos computa-la através dos seguintes passos:
#    Computar o [[Envoltória convexa|fecho convexo]] de <math>S_E</math> e o fecho convexo de <math>S_D</math>.
#    Encontrar o par de pontos, <math>e\in S_E</math> e <math>d\in S_D</math> que define a ponte superior de junção dos fechos convexos de <math>S_E</math> e <math>S_D</math>
#    Criar uma aresta consistindo da mediatriz desses dois pontos, a partir do <math>-\infty </math>, e definir como aresta atual.
#    Sempre que a aresta atual encontrar uma aresta existente, muda-se um dos dois pontos. Se a aresta encontrada pertence à <math>V(S_E)</math>, então atualiza-se o ponto <math>e</math>, caso contrário atualiza-se o ponto <math>d</math>. O ponto é trocado pelo outro ponto equidistante da aresta que foi interceptada.
#    Criar uma nova aresta a partir sobre a mediatriz desses novos pontos que passa a ser a reta atual.
#    Adicionar essa aresta à <math>P</math>
#    Repetir passos 4, 5 e 6 até que a ponte inferior de junção dos fechos convexos seja alcançada.

=== Pseudocódigo ===

<tt><b>VORONOI_DIAGRAM</b><ref>{{Citar periódico
 | ultimo    = Okabe
 | primeiro  = A.
 | ultimo2  = Hoey
 | primeiro2 = D.
 | ultimo3  = Boots
 | primeiro3 = B.
 | ultimo4   = Sugihara
 | primeiro4 = K.
 | ano       = 1992
 | titulo    = Spatial Tessellations, Concepts and Applications of Voronoi diagrams
 | editora   = Wiley
 | local     = England
 }}</ref>

<b>ENTRADA:</b> Uma lista/conjunto S = {s<sub>1</sub>, s<sub>2</sub>,..., s<sub>n</sub>} de pontos em ordem ascendente em relação a coordenada x, onde n > 3

<b>SAÍDA:</b> Diagrama de Voronoi V(S)

#    Seja t a parte inteira de n/2, dividir S em S<sub>E</sub> = {s<sub>1</sub>, s<sub>2</sub>,..., s<sub>t</sub>} e S<sub>D</sub> = {s<sub>t+1</sub>, s<sub>t+2</sub>,..., s<sub>n</sub>}
#    Construir o Diagrama de Voronoi V(S<sub>E</sub>) de S<sub>E</sub> recursivamente
#    Construir o Diagrama de Voronoi V(S<sub>D</sub>) de S<sub>D</sub> recursivamente
#    Combinar V(S<sub>E</sub>) e V(S<sub>D</sub>) em V(S) i.e, V(S)=V(S<sub>E</sub>)&nbsp;&cup;&nbsp;V(S<sub>D</sub>) computando a cadeia divisória e podando as arestas desnecessárias.
#    Devolve V(S)
</tt>

==Algoritmo de Fortune==

Para a construção de diagramas de Vornoi, o Algoritmo de varredura (Sweep Algorithm) foi proposto em 1986 por Steven Fortune através do artigo "A Sweepline Algorithm for Voronoi Diagrams" (Tradução livre: Um algoritmo de linha de varredura para os diagramas de Voronoi). Esse algoritmo é normalmente chamado de Algoritmo de Fortune, em referência a seu autor, tem complexidade <math>O(n log n)</math> e é, portanto, considerado um algoritmo ótimo para a construção dos diagramas.

===Descrição===

Inicialmente temos um conjunto <math>S</math> de <math>n</math> pontos dispostos no plano <math>xy</math> Em seguida, criamos um conjunto de cones idênticos, de forma que, para cada ponto do conjunto haja um cone que cresce em direção ao eixo <math>z</math>. <!--figura1-->

Dito isso, podemos dizer que a intersecção entre dois cones é uma hipérbole, cuja projeção no plano <math>xy</math> é uma reta correspondente a uma das arestas do Diagrama de Voronoi.

A ideia do algoritmo de Fortune é deslocar um plano, com a mesma inclinação que a dos cones, sobre o plano <math>xy</math>. Este plano é chamado de "Plano de Varredura" e sua intersecção com o plano <math>xy</math>, gera a linha que é chamada de ''Sweepline'', ou “Linha de varredura”.<!--figura2-->

A projeção no plano <math>xy</math> a esquerda da Linha de Varredura, gerará o diagrama de Voronoi.
Dado um ponto <math>P</math> qualquer, podemos dizer que o conjunto de pontos mais próximos de <math>P</math> do que da linha de varredura é uma parábola. A fronteira da união das parábolas formadas antes da linha de varredura é chamada de ''beach line'', ou “linha de praia”.<!--figura3-->

Vale observar que o ponto de encontro entre duas parábolas na linha de praia sempre está sobre uma aresta do diagrama.

===Estratégia do Algoritmo===

[[Image:Fortunes-algorithm-slowed.gif|frame|right|Animação: Algoritmo de Fortune]]

A estratégia do algoritmo é deslocar a linha de varredura de cima para baixo (note que no plano, a ordem esquerda-direita e cima-baixo, não altera em nada a lógica do algoritmo), armazenando a estrutura acima da linha enquanto a mesma se desloca. É fácil notar que a estrutura acima da linha de praia não se modifica. Sobre a linha de praia, ela só sofre alterações significativas em duas situações as quais são chamadas de ''Site Events'', ou “evento-ponto”, e ''Circle Events'', ou “evento-círculo”.

Um ponto-evento ocorre quando a linha de varredura passa por um ponto qualquer. Depois que isso acontece, um novo arco é adicionado à linha de praia. Esse novo arco pode quebrar um arco já existente em dois.

Quando um arco na linha de praia é reduzido até tornar-se um ponto (quando ocorre o encontro entre três [[parábola]]s), podemos traçar um círculo centrado nesse ponto que passa por todos os pontos geradores das parábolas e que também é tangente a linha de varredura. Por isso dizemos que aconteceu um evento-círculo, que é o único modo de um arco sair da linha de praia.

Resumindo, um novo arco surge na linha de praia quando um evento-ponto ocorre e sai com um evento-círculo.

;Bibliografia
*{{Citar livro 
|autor = [[Mark de Berg]], [[Marc van Kreveld]], [[Mark Overmars]], e [[Otfried Schwarzkopf]] 
|ano = 2008 
|título= Computational Geometry
|editora=[[Springer-Verlag]]|língua=en
|isbn=3-540-65620-0
}}

==Ver também==
*[[Diagrama de Voronoi]]

{{Referências}}

[[Categoria:Algoritmos]]
[[Categoria:Geometria computacional]]