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!
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.
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.
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.
je suis presque sûr que "triangle " http://www.cs.cmu.edu/~quake/triangle.html peut générer le voronoi
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?