Comment puis-je obtenir un diagramme de Voronoi compte tenu de son ensemble de points et de sa triangulation Delaunay?

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

avec cela fait, je cherche maintenant à créer un diagramme de Voronoi des points pour servir de point de départ pour les frontières de la province. Mes données à ce point (pas de jeu de mots prévu) se compose de la série originale de points et une collection de les triangles Delaunay.

j'ai vu un certain nombre de façons de le faire sur le web, mais la plupart d'entre eux sont liés à la façon dont le Delaunay a été dérivé. J'aimerais trouver quelque chose qui n'a pas besoin d'être intégrée à l'Delaunay, mais peut travailler basé sur les données. Sinon, je cherche quelque chose de compréhensible pour un débutant de géométrie relative, par opposition à une vitesse optimale. Merci!

24
demandé sur S. Huber 2008-09-17 20:53:40

5 réponses

le diagramme de Voronoi n'est que le double graphe de la triangulation de Delaunay.

  • ainsi, les bords du diagramme de Voronoi sont le long des bisecteurs perpendiculaires des bords de la triangulation de Delaunay, donc calculez ces lignes.
  • ensuite, calculer les sommets du diagramme de Voronoi en trouvant les intersections des bords adjacents.
  • enfin, les bords sont alors les sous-ensembles des lignes que vous avez calculées 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.

18
répondu Adam Rosenfield 2012-05-10 13:12:30

si la vitesse optimale n'est pas prise en compte, le code psuedo suivant générera un diagramme de Voronoi à 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 avez une classe ou une structure de "point", si vous leur assignez des couleurs aléatoires, alors vous verrez le motif voronoi familier lorsque vous affichez la sortie.

8
répondu Alexandra Franks 2008-09-17 17:13:42

après avoir essayé d'utiliser ce fil comme source pour des réponses à ma propre question similaire, j'ai trouvé que L'algorithme de Fortune - probablement parce qu'il est le plus populaire et donc le plus documenté - était le plus facile à comprendre.

L'article de Wikipedia sur L'algorithme de Fortune garde de nouveaux liens vers le code source en C, C#, et Javascript. Tous étaient de premier ordre et venaient avec de beaux exemples.

2
répondu Wray Bowling 2012-10-02 14:58:15

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

1
répondu Martin Beckett 2008-09-17 19:55:06

chacun de vos triangles Delaunay contient un point unique du diagramme de Voronoi.

vous pouvez calculer ce point en trouvant l'intersection des trois bisecteurs perpendiculaires pour chaque triangle.

votre diagramme de Voronoi 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 de bord?

0
répondu Arc the daft 2008-09-17 17:14:04