Como faço para obter um diagrama de Voronoi dado o seu conjunto de pontos e sua triangulação de Delaunay?

Question

Eu estou trabalhando em um jogo onde eu criar um mapa aleatório das províncias (a la Risco ou Diplomacia). Para criar esse mapa, estou primeira geração de uma série de pontos semi-aleatórios, em seguida, descobrir as triangulações de Delaunay desses pontos.

Com isso feito, agora estou olhando para criar um diagrama de Voronoi dos pontos para servir como um ponto de partida para as fronteiras província. Meus dados neste momento (sem trocadilhos) consiste da série original de pontos e uma coleção dos triângulos Delaunay.

Eu vi um número de maneiras de fazer isso na web, mas a maioria deles são amarrados com a forma como o Delaunay foi derivado. Eu adoraria encontrar algo que não precisa ser integrado ao Delaunay, mas pode trabalhar com base off os dados sozinho. Falhando isso, eu estou procurando algo compreensível para um novato geometria relativa, em oposição a velocidade ideal. Obrigado!

Answer 1

O diagrama de Voronoi é apenas o grafo dual da triangulação de Delaunay.

• Assim, as bordas do diagrama de Voronoi são ao longo das bissectrizes perpendiculares das bordas da triangulação Delaunay, assim calcular essas linhas.
• Em seguida, calcula-se os vértices do diagrama de Voronoi, encontrando as intersecções das orlas adjacentes.
• Finalmente, as bordas são então os subconjuntos das linhas que você calculados que se encontram entre os vértices correspondentes.

Note que o código exato depende da representação interna que você está usando para os dois diagramas.

Answer 2

Se a velocidade ideal não é uma consideração, o seguinte código pseudo irá gerar um diagrama de Voronoi da maneira mais difícil:

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

Supondo que você tenha uma classe 'ponto' ou estrutura, se você atribuir-lhes cores aleatórias, então você vai ver o padrão voronoi familiar quando você exibir a saída.

Answer 3

Depois de tentar usar esta discussão como uma fonte de respostas para a minha própria pergunta semelhante, descobri que o algoritmo de Fortune - provavelmente porque ele é o mais popular e, portanto, mais documentado -. Foi o mais fácil de entender

O artigo da Wikipedia sobre o algoritmo de Fortune mantém ligações frescas para o código-fonte em C, C # e Javascript. Todos eles eram de alto nível e veio com belos exemplos.

Answer 4

Eu tenho certeza de que 'triângulo' http: //www.cs .cmu.edu / ~ terremoto / triangle.html pode gerar o voronoi

Answer 5

Cada um dos seus triângulos Delaunay contém um único ponto do diagrama de Voronoi.

Você pode calcular este ponto por encontrar a intersecção dos três perpendicular bisectors para cada triângulo .

O seu diagrama de Voronoi vai ligar esse conjunto de pontos, cada uma com seu mais próximos três vizinhos. (Cada vizinho compartilha um lado do triângulo Delaunay)

Como você planeja abordar os casos de ponta?