Comment puis-je obtenir un diagramme de Voronoï étant donné son ensemble de points et sa triangulation de Delaunay?

StackOverflow https://stackoverflow.com/questions/85275

Question

Je travaille sur un jeu où je crée une carte aléatoire des provinces (à la fois Risque ou Diplomatie). Pour créer cette carte, je génère d'abord une série de points semi-aléatoires, puis calcule les triangulations de Delaunay de ces points.

Cela fait, je cherche maintenant à créer un diagramme de Voronoï des points qui servira de point de départ pour les frontières de la province. Mes données à ce stade (sans jeu de mots) sont constituées de la série de points d'origine et d'une collection de triangles de Delaunay.

J'ai vu plusieurs façons de faire cela sur le Web, mais la plupart d'entre elles sont liées à la façon dont le Delaunay a été dérivé. J'aimerais trouver quelque chose qui n'a pas besoin d'être intégré à Delaunay, mais qui peut fonctionner uniquement à partir des données. Sinon, je cherche quelque chose de compréhensible pour un débutant en géométrie relative, par opposition à une vitesse optimale. Merci!

Était-ce utile?

La solution

Le diagramme de Voronoï n’est que le double graphe de la triangulation de Delaunay.

  • Ainsi, les contours du diagramme de Voronoï sont situés le long des bissectrices perpendiculaires des contours de la triangulation de Delaunay. Calculez donc ces lignes.
  • Calculez ensuite les sommets du diagramme de Voronoï en recherchant les intersections des arêtes adjacentes.
  • Enfin, les arêtes sont alors les sous-ensembles des lignes que vous avez calculées qui se situent entre les sommets correspondants.

Notez que le code exact dépend de la représentation interne que vous utilisez pour les deux diagrammes.

Autres conseils

Si la vitesse optimale n'est pas prise en compte, le code psuedo suivant générera un diagramme de Voronoï à la dure: 

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

En supposant que vous ayez une classe ou une structure "ponctuelle", si vous leur affectez des couleurs aléatoires, vous verrez le motif voronoi bien connu lorsque vous affichez la sortie.

Après avoir essayé d’utiliser ce fil comme source de réponses à une question similaire, j’ai découvert que l’algorithme de Fortune & # 8212; probablement parce que c’est le plus populaire & amp; donc le plus documenté & # 8212; était le plus facile à comprendre.

L'article de Wikipedia sur l'algorithme de Fortune conserve de nouveaux liens vers le code source en C, C #. et Javascript. Ils étaient tous excellents et venaient avec de beaux exemples.

Je suis presque sûr que le "triangle" http: //www.cs .cmu.edu / ~ quake / triangle.html peut générer le voronoi

Chacun de vos triangles de Delaunay contient un seul point du diagramme de Voronoï.

Vous pouvez calculer ce point en recherchant l'intersection des trois médiatrices pour chaque triangle. .

Votre diagramme de Voronoï connectera cet ensemble de points, chacun avec ses trois voisins les plus proches. (chaque voisin partage un côté du triangle de Delaunay)

Comment envisagez-vous d'approcher les cas extrêmes?

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top