Como gerar diagramas de Voronoi com o algoritmo de Fortune

 (redpenguin101.github.io)
2 pontos por GN⁺ 2025-02-10 | 1 comentários | Compartilhar no WhatsApp
  • Fortune’s Algorithm consegue criar um diagrama de Voronoi em O(n log n), mas é difícil de implementar; a menos que você precise gerar repetidamente diagramas grandes, uma implementação O(n²) ou uma biblioteca costuma ser mais prática
  • Um diagrama de Voronoi divide o plano em regiões mais próximas com base em vários sites, e as fronteiras são formadas por pontos equidistantes de dois sites
  • O algoritmo mantém uma sweep line que se move da esquerda para a direita e a beachline, frente de arcos parabólicos, processando apenas site events e circle events
  • Um site event insere um novo arco, divide um arco existente e cria uma incomplete edge; um circle event remove o arco do meio, completando um Voronoi Vertex e uma half edge
  • Em implementações práticas, é preciso lidar em conjunto com fila de eventos, beachline, mapa de incomplete edges e DCEL, e a remoção de circle events inválidos e a limpeza das edges restantes aumentam bastante a complexidade

Dificuldade de implementação e escopo de aplicação

  • Fortune’s Algorithm é um algoritmo que gera diagramas de Voronoi em O(n log n)
  • Se o objetivo for uso real, vale mais a pena avaliar primeiro a escala necessária antes de implementar direto
    • Se não for preciso gerar vários diagramas grandes por segundo, uma implementação O(n²) pode ser uma escolha mais simples
    • Uma alternativa mais realista é usar uma biblioteca existente
  • O resultado visual do algoritmo é interessante, mas o processo de implementação tende a ser trabalhoso e frustrante

Conceitos básicos do diagrama de Voronoi

  • O diagrama de Voronoi é uma forma de dividir o plano em várias regiões e é muito usado em geração procedural de mapas
  • Os pontos escolhidos na entrada são chamados de sites ou seeds
  • A cell correspondente a cada site é o conjunto de pontos do plano que estão mais próximos desse site
  • As fronteiras das células são compostas por pontos equidistantes de dois sites
  • O Voronoi Vertex onde os cantos das células se encontram é um ponto equidistante de três sites

sweep line, beachline e event

  • Fortune’s Algorithm usa uma sweep line, uma linha vertical que se move da esquerda para a direita
  • Quando a sweep line encontra um site, forma-se um arco parabólico com esse site como foco, e o arco cresce à medida que a sweep line se afasta
  • O ponto onde dois arcos de sites diferentes se encontram é equidistante dos dois sites, portanto vira uma fronteira entre células
  • Quando duas fronteiras se encontram, surge um vértice do diagrama
  • A frente dos arcos ativos é chamada de beachline
  • Na implementação real, a sweep line não anda pixel a pixel; apenas events em posições calculáveis específicas são processados
    • site event: definido pelas coordenadas conhecidas de um site e, ao ser processado, adiciona um novo arco à beachline
    • circle event: definido por três arcos da beachline e, ao ser processado, remove um arco e gera um Voronoi Vertex e uma half edge

Encontrando fronteiras com parábolas

  • No algoritmo, a parábola não é tratada na forma usual y = ax^2 + bx + c, e sim pela locus definition
  • Uma parábola é definida por um focus point e uma directrix
    • o focus point é o site
    • a directrix é a sweep line
  • A interseção de duas parábolas que usam a mesma sweep line como directrix é equidistante dos dois sites
  • Portanto, ao encontrar a interseção entre duas parábolas, encontramos a equiedge entre dois sites
  • São usados um pseudocódigo para calcular a coordenada x da parábola e um exemplo mostrando como a interseção entre duas parábolas se move ao longo da fronteira quando a posição da sweep line muda

Representação da beachline e processamento de site event

  • Cada arco da beachline pode ser representado apenas pelas coordenadas do site correspondente
    • a sweep line é comum a todos os arcos
    • na implementação, o arco não é tratado como um objeto separado, mas como uma coordenada 2D
  • A beachline pode ser representada como uma simples ordem de pontos
    • exemplo: [arc1, arc2], [arc1, arc2, arc3]
    • arcos do mesmo site podem aparecer várias vezes na beachline
    • exemplo: [arc1, arc3, arc1, arc2]
  • Quando ocorre um site event, procura-se o arco da beachline encontrado ao traçar uma linha para a esquerda a partir do novo site, e o novo arco divide esse arco
  • Se o novo site L dividir j na beachline existente [.., i, j, k, ..], a estrutura vira [.., i, j, L, j, k, ..]
  • Os sites entram na fila em ordem de coordenada x e, a cada processamento, a beachline e os candidatos a evento são atualizados

circle event e circumcircle

  • Nos três arcos [.., i, j, k, ..] da beachline, quando surge uma situação em que duas fronteiras se encontram, o arco do meio j desaparece
  • Nesse momento, existe uma circumcircle que passa pelos três sites, e o centro do círculo é equidistante dos três sites
  • O centro da circumcircle se torna um Voronoi Vertex
  • O circle event é colocado na fila de eventos com base no circle point, a extremidade direita do círculo
  • Se um novo site for encontrado dentro do círculo antes de a sweep line alcançar o circle point, o circle event existente se torna inválido
    • isso acontece porque o novo site divide antes o arco do meio, então a combinação dos três arcos deixa de existir
    • o triple original i, j, k desaparece, e novos triples como i, j, L e L, j, k precisam ser verificados

incomplete edge e half edge

  • Uma incomplete edge é uma linha cujo ponto final de um lado está fixo, mas o outro é definido pela interseção entre dois arcos parabólicos
  • Quando um novo arco é inserido em um site event, são criadas duas incomplete edges
    • o ponto fixo é a coordenada onde o novo arco encontrou a beachline existente
    • se o novo arco j dividir o arco existente i, surge uma edge correspondente à interseção [i, j], [j, i]
  • Quando duas incomplete edges colidem em um circle event, esse ponto de colisão se torna um Voronoi Vertex
  • A incomplete edge existente é completada nesse ponto como uma half edge, e uma nova incomplete edge é criada entre os dois arcos que passaram a ser adjacentes

Apenas círculos no sentido anti-horário viram circle event

  • Quando a beachline contém [i, j, k, j, i], tanto ijk quanto kji podem formar um círculo, mas nem ambos serão circle events válidos
  • O caso em que o arco do meio desaparece é apenas aquele em que as fronteiras realmente convergem
  • No programa, a orientation dos três pontos é determinada por um determinante
    • se o determinante for negativo, a orientação é anti-horária e isso gera um circle event
    • se o determinante for positivo, a orientação é horária e isso não gera um circle event
    • se o determinante for 0, os três pontos são colineares e não há círculo

Fluxo geral do algoritmo

  • Os sites de entrada são ordenados pela coordenada x e colocados na fila como site events
  • Enquanto a fila não estiver vazia, o próximo event é removido e processado
  • Processamento de site event:
    • remove os circle events futuros em que o novo site entra no interior do círculo
    • encontra o arco da beachline que será dividido pelo novo site
    • insere o novo arco e divide o arco existente
    • adiciona duas incomplete edges
    • verifica se os novos triples podem gerar circle events
  • Processamento de circle event:
    • adiciona o centro da circumcircle como Voronoi Vertex
    • remove o arco do meio da beachline
    • remove os futuros circle events que se tornam inválidos por causa do arco removido
    • verifica o triple dos arcos recém-adjacentes para adicionar um circle event
  • Quando a fila esvazia, as incomplete edges restantes são estendidas até a borda do diagrama, e são criados Voronoi Vertex nos pontos onde elas encontram essa borda

Estruturas de dados da implementação em Odin

  • A implementação de exemplo foi escrita em Odin, uma linguagem alternativa ao C
  • O código completo está no repositório RedPenguin101/voronoi
  • Tipos básicos:
    • V2: ponto 2D no formato [2]int
    • PointPair: par de dois V2
    • Event: struct {site: bool, a, b, c: V2}
  • O significado de Event muda conforme o tipo
    • em site event, a é a coordenada do site e b e c não são usados
    • em circle event, a, b e c são os três arcos da beachline que geraram o event
  • A struct Fortune gerencia o seguinte estado
    • beachline: array de V2
    • queue: array de Event
    • incomplete_edges: mapa PointPair -> V2
    • vd: um DCEL que armazena o diagrama de Voronoi

Partes omitidas ou simplificadas na implementação

  • A beachline foi representada como vetor, mas uma binary tree seria mais adequada para melhorar a eficiência
  • A event queue também é, conceitualmente, uma priority queue, mas na implementação de exemplo ela é tratada por inserção ordenada em array
  • A invalidação de circle events é feita percorrendo os eventos futuros, e há um TODO indicando a necessidade de um método mais rápido
  • clean_beachline_edges é o procedimento que remove arcos desnecessários nas duas extremidades da beachline
  • A implementação inclui tratamento de exceções como sites com a mesma coordenada x, casos em que circle point e site coincidem, e colisões de pontos de referência
  • A etapa final de organizar incomplete edges restantes após a fila esvaziar, half edges sem twin e vertexes é tratada apenas com matemática simples

Armazenando o diagrama de Voronoi com DCEL

  • O diagrama de Voronoi normalmente é armazenado em uma Doubly Connected Edge List (DCEL)
  • DCEL é uma estrutura de dados que facilita representar e manipular um complexo celular formado por vertexes e edges
  • Embora seja centrada em edges, ela também armazena informações de vertexes e faces
  • Uma edge comum não tem direção, mas no DCEL cada edge é armazenada como duas half edges em direções opostas
  • No diagrama de Voronoi, os vertexes armazenados no DCEL não são os sites, e sim os Voronoi Vertexes
  • O destino da edge E é obtido por E.twin.origin, e a face da direita por E.twin.left

Leituras relacionadas

1 comentários

 
GN⁺ 2025-02-10
Comentários do Hacker News

  • Há algum tempo, fiz uma implementação em ClojureScript que mostra uma animação do algoritmo de Fortune em execução: https://voronoi.ajwerner.net/#/app-diagrams
    É um algoritmo realmente bonito.
    Só que, depois desse projeto, passei a gostar um pouco menos do algoritmo de Fortune, porque sua estabilidade numérica com ponto flutuante não é boa.
    Se os pontos estiverem em linha reta, ou quase em linha reta segundo critérios de ponto flutuante, ele pode quebrar.
    Se me lembro bem, o delaunator é melhor nesse aspecto: https://github.com/mapbox/delaunator

    • A animação é a melhor que já vi.
      Na página de referência aparece um link para a implementação “old”; fiquei curioso se há possibilidade de a versão animada atual também ser disponibilizada como open source.

  • Alguns anos atrás, fiz uma visualização 3D desse tipo: https://x.com/KangarooPhysics/status/1253336959755251716

  • Existe uma implementação em JavaScript de Raymond Hill, famoso pelo uBlock Origin: https://github.com/gorhill/Javascript-Voronoi
    Mexi um pouco nela aqui para fazê-la se mover: https://animations.adgent.com/voronoi.html

    • Essa animação lembra o estilo de A Scanner Darkly (2006).
      Fico pensando se daria para pegar um vídeo como entrada e passá-lo por um algoritmo que o exibisse no estilo Voronoi.
      A essa altura talvez nem fosse, estritamente falando, um diagrama de Voronoi, mas acho que ficaria bem legal.

  • O D3.js tem uma implementação nova: https://github.com/d3/d3-delaunay
    Mais abaixo nessa página há uma explicação do algoritmo de varredura usado e uma lista de implementações em linguagens além de JavaScript.
    O antigo d3-voronoi está previsto para ser descontinuado, mas pode ser visto aqui: https://github.com/d3/d3-voronoi

  • Se você não se importa com as arestas e só quer pintar cada ponto com uma cor diferente, pode usar uma variação de flood fill a partir dos pontos-semente.
    Basta colocar um pixel na pilha somente quando a distância daquela cor for menor do que a da cor já pintada naquele pixel.

    • Dá para criar uma cena 3D com cones retos de cores diferentes, com os vértices em cada ponto do plano 2D, e colocar o eixo perpendicular ao plano.
      Ao renderizar com projeção ortográfica 2D a partir de cima dos vértices, o z-buffer preserva o pixel do vértice mais próximo.
      Também deve haver um jeito de fazer isso com shader, mas a demonstração clássica de cones 3D é muito fácil de entender e implementar.

  • É interessante que o D3 tenha migrado do algoritmo de Fortune para https://mapbox.github.io/delaunator/
    O motivo é que, “para criar triangulações de Delaunay ou diagramas de Voronoi, ele é 5 a 10 vezes mais rápido que o d3-voronoi, mais robusto numericamente, tem renderização em Canvas integrada e oferece travessia do grafo de Delaunay e várias melhorias”.

    • Se o D3 considera o delaunator a melhor opção para esse tipo de efeito, então não tenho mais desculpa para não adicioná-lo à minha biblioteca de canvas, exceto a boa e velha tendência a procrastinar.
      O código atual que calcula os tiles é dolorosamente ingênuo.
      Nova discussão: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

  • Este artigo me fez procurar onde Steve anda hoje em dia.
    Eu o conheci décadas atrás.

  • Um texto relacionado que vale a pena ver: https://news.ycombinator.com/item?id=37998923 - Criando diagramas de Voronoi e triangulações de Delaunay em O(n log n) com o algoritmo de Fortune (2020)
    O texto e a discussão anteriores também trazem breves resumos de outros algoritmos.
    Pessoalmente, ainda gosto mais do Jump Flooding Algorithm: https://en.wikipedia.org/wiki/Jump_flooding_algorithm