Geração de Diagramas de Voronoi com o Algoritmo de Fortune

Gerando diagramas de Voronoi

• O que é um diagrama de Voronoi?

  • Um diagrama de Voronoi é uma forma de dividir o plano em várias regiões, sendo usado principalmente para gerar mapas proceduralmente.
  • Selecionam-se vários pontos no plano, chamados de 'sites', e a região correspondente a cada site inclui todos os pontos mais próximos dele.
  • As fronteiras de cada região são formadas por pontos que estão à mesma distância de dois sites. Pontos à mesma distância de três sites são chamados de 'vértices de Voronoi'.

• Algoritmo de Fortune

  • O algoritmo de Fortune é um método para gerar o diagrama usando uma linha que faz uma 'varredura' do lado esquerdo para o direito do plano.
  • Quando a linha de varredura encontra um site, uma 'bolha' (arco parabólico) é criada ao redor dele, e a bolha cresce à medida que a linha de varredura se afasta.
  • Quando os arcos de dois sites colidem, o ponto dessa colisão se torna a fronteira da célula.
  • A fronteira de todas as bolhas ativas é chamada de 'linha de praia'.

• Glossário de termos

  • Site: ponto bidimensional que determina a forma do diagrama de Voronoi.
  • Linha de varredura: linha vertical que atravessa a região e processa cada evento da fila de eventos.
  • Linha de praia: linha composta por vários arcos, em que arcos são adicionados ou removidos conforme os eventos são processados.
  • Ponto de interseção: ponto onde dois arcos da linha de praia se encontram e que está à mesma distância dos sites relacionados.
  • Fila de eventos: onde os eventos de site e de círculo são armazenados, ordenados em ordem crescente da coordenada x.
  • Evento de site: um dos dois tipos de evento da fila, definido pelas coordenadas do respectivo site.
  • Evento de círculo: o outro tipo de evento da fila, definido por três arcos na circunferência de um círculo.
  • Vértice de Voronoi: ponto à mesma distância de três sites, formando o canto de uma célula.
  • Fronteira de equidistância: linha à mesma distância de dois sites.
  • Fronteira incompleta: linha em que uma extremidade é um ponto fixo e a outra é definida pelo ponto de interseção de dois focos parabólicos.

• Tangentes parabólicas

  • Os conceitos e propriedades da parábola são muito importantes no algoritmo.
  • Uma parábola é definida por um ponto focal e uma reta (diretriz).
  • Ao definir os focos de dois sites e usar a linha de varredura como diretriz, é possível encontrar a linha de fronteira equidistante aos dois sites encontrando o ponto de interseção das duas parábolas.

• Voltando à linha de praia

  • A linha de praia é a 'fronteira' de todos os arcos em um determinado ponto da linha de varredura.
  • Cada arco pode ser representado pelo ponto focal de um site.
  • A linha de praia pode ser representada como uma sequência simples de pontos.

• Um novo arco é criado quando a linha de varredura encontra um novo site

  • A linha de praia é uma sequência de pontos, em que cada ponto representa um site e um arco.
  • Quando a linha de varredura encontra um novo site, um novo arco é criado e inserido na sequência.

• Fronteiras que se cruzam e círculo circunscrito

  • Quando três sites estão sobre a circunferência de um círculo, o centro desse círculo está à mesma distância dos três pontos.
  • O centro do círculo circunscrito se torna um vértice de Voronoi.

• Fronteiras incompletas

  • Uma fronteira incompleta tem uma extremidade fixa em um ponto, e a outra é a interseção entre dois arcos.
  • Quando duas fronteiras incompletas colidem, um vértice de Voronoi é gerado, e as fronteiras incompletas são convertidas em semiarestas.

• Somente círculos no sentido anti-horário geram eventos de círculo

  • Um evento de círculo só é gerado quando três arcos são lidos no sentido anti-horário.

• Resumo

  • Dado um conjunto de sites, coloque todos os pontos dos sites na fila como eventos de 'site' e ordene-os pelo valor de x.
  • Enquanto a fila não estiver vazia, retire o próximo evento da fila e processe-o.
  • Se for um evento de site, adicione um novo arco à linha de praia e crie fronteiras incompletas.
  • Se for um evento de círculo, adicione um vértice de Voronoi e remova o arco da linha de praia.