Discussion :

[Nyx]

Bonsoir,

Toutes mes tentatives pour générer une carte politique se sont soldées par un échec. Elles sont à peu près toutes issues de bricolage ce qui entraîne plein d'imperfections. Je suis donc à la recherche de quelque chose de plus rigoureux, plus mathématique.

D'abord, je définie ce que j'entend par "carte politique":
- un espace divisé en régions de taille approximativement égale. Donc rien à voir avec une simple heightmap que l'on utilise habituellement pour générer des cartes.
conditions:
(1) les régions ne doivent pas avoir un nombre prédéfini de voisines.
(2) elles doivent être sous la forme de polygons totalement indépendants.
(3) execution en moins de 1 minute.

exemple:


L'exemple est un diagramme de Voronoï mais sa construction est compliquée pour pas grand chose, de plus il est difficile de séparer les régions (indépendances des régions: condition (2) ) d'où l'interêt de générer directement des régions et pas les frontieres mais peut-être je me trompe.

En bricolant, on rencontre souvant les problèmes suivant:
- quelques régions très petites
- des espaces vides
- des regions qui se recoupent.

une idée ?

[FrancisSourd]

Il est possible de partir d'un quadrillage du plan en carré et de faire subir à ces carrés des évenements aléatoires (déplacement d'un sommet selon une direction aléatoire, ajout d'un sommet sur la frontière...) Il faut veiller à ce que chacune des transformations conserve les propriétés désirées.

Cela devrait permettre d'obtenir une cartographie plus irrégulières que les diagrammes de Voronoi (dans lequel toutes les régions sont convexes).

[Kangourou]

salut,

Voronoi a quand meme l'air d'etre le plus adapte pour le probleme. Apres on peut varier un peu.

En choisissant des points avec une distance minimum entre points ('hard-core point'), le decoupage obtenu est plus regulier. on peut aussi partir d'un treillis regulier auquel on ajoute un deplacement locale pour chaque point.

L'implementation est complexe, mais on trouve facilement les algo. le plus efficace (et peut-etre le plus simple a programmer ?) est l'algo de Fortune 'sweep-line', qui permet d'avoir une complexite lineaire.

Une possibilite si on travaille avec des images est d'utiliser une distance, que l'on propage autour de chaque germe. il faut isoler les maxima de la fonction distance obtenue, et on a la carte.

Pour avoir des regions moins convexes, 2 idees :
- rajouter une etape de fusion des regions (pas tres joli)
- rajouter un mouvment aleatoire sur chaque arete, en le contraignant a rester dans une zone donnee pour eviter d'avoir des croisement de frontiere. Rendu assez eraliste.

A+

[Nyx]

Il est possible de partir d'un quadrillage du plan en carré et de faire subir à ces carrés des évenements aléatoires

En faisant un quadrillage, chaque région aura 8 voisines (sauf celles sur les côtés). Donc ça ne respecte pas la condition:
(1) les régions ne doivent pas avoir un nombre prédéfini de voisines.

Voronoi a quand meme l'air d'etre le plus adapte pour le probleme

Malheureusement je suis pas sûr que mon niveau me le permette. Par contre j'ai lu que le diagramme de Voronoï est exploité pour des propriétés bien particulieres. Je ne crois pas avoir besoin de m'encombrer de ces propriétés et c'est donc peut-être une occasion de simplifier grandement les algorithmes de construction de ce genre de diagramme ?
Par exemple, une figure semblable à la triangulation Delaunay (http://www.hydrographicsociety.org/Articles/journal/2001/journalgrfx/101-4-006.gif)
semble beaucoup plus facile à générer. Que se passe-t-il si on applique la transformation "Delaunay"-->"Voronoï" à une telle figure (qui n'est pas rigoureusement une triangulation de Delaunay mais qui lui ressemble).

Une possibilite si on travaille avec des images est d'utiliser une distance, que l'on propage autour de chaque germe. il faut isoler les maxima de la fonction distance obtenue, et on a la carte.

Peux-tu developper cette idée ?

[Kangourou]

Pour la propagation par distance :

tu pars d'un tableau avec des valeur tres grandes partout, et 0 la ou tu as tes points.
Ensuite pour chaque pixel, tu affecte la valeur minimum entre la valeur de ce pixel, et la valuer des 4 voisins les plus proches, plus un.
Ex :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
9 9 9 9 9 9
9 0 9 9 9 9
9 9 9 9 9 0
9 9 9 9 9 9
9 9 0 9 9 9

donne ensuite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
9 1 9 9 9 9
1 0 1 9 9 1
9 1 9 9 1 0
9 9 1 9 9 1
9 1 0 1 9 9

puis apres 2 iterations :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
2 1 2 3 3 2
1 0 1 2 2 1
2 1 2 2 1 0
3 2 1 2 2 1
2 1 0 1 2 2

Apres, il faut ariver a recupere la ligne de crete des niveaux, ce qui est pas forcement le plus simple.
Sinon tu peux aussi utiliser les 8 plus proches voisins et eventuellement des pônderations differents selon les directions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1.41 1 1.41
  1    0    1
1.41 1 1.41

voila voila,

A+

[FrancisSourd]

Il est possible de partir d'un quadrillage du plan en carré et de faire subir à ces carrés des évenements aléatoires

En faisant un quadrillage, chaque région aura 8 voisines (sauf celles sur les côtés). Donc ça ne respecte pas la condition:
(1) les régions ne doivent pas avoir un nombre prédéfini de voisines.

C'est vrai au départ mais, en introduisant des événements aléatoires bien sentis, on pourra s'affranchir du problème. Le déplacement des frontières peut suffir mais on peut aussi imaginer la suppression d'une frontière entre deux voisins (réunion des deux régions voisines). Evidemment, cela crée des régions plus grosses que d'autres mais on pourra alors biaiser les événements "déplacement de frontières" de manière à ce que les régions les plus grosses diminuent et les plus petites grossissent.

[Mac LAK]

Une idée, comme ça (je ne sais pas si elle sera exploitable réellement pour ton besoin) :
- Partir d'une région (le "monde"), vide.
- Traitement en boucle :
- Choisir une ligne aléatoirement partageant le monde en deux, en veillant à ce qu'elle ne soit pas trop proche d'une ligne de ce type déjà tracée (mémoriser les coordonnées de chaque ligne ayant été tracée).
- Tracer la ligne : on démarre avec le "pinceau baissé" (la ligne se trace réellement). Lorsqu'elle rencontre une autre ligne, on inverse la position du pinceau (=on le lève, ou on le baisse suivant le cas), mais on continue à tracer la ligne.
- Arrivée au bord opposé : fin de tracé, retour au début de boucle.

Suivant le nombre de lignes et l'algo de choix aléatoire des lignes de partage, ça devrait produire un résultat similaire à celui que tu présentais plus haut, je pense... Un algo de Bresenham pour le tracé de ligne, l'examen de la "couleur" du pixel courant pour déterminer si l'on inverse la couleur du tracé ou non...

[Nyx]

Pour la propagation par distance, j'obtiens ça:
(les valeurs qui tendent vers 0 tendent vers le blanc)

Concretement sur cette image, que représente la ligne de crête des niveaux dont tu parles ?
Je vois pas exactement la finalité de ta méthode. Vais-je obtenir des polygones au final ? (conditions (2): les régions doivent être sous la forme de polygons totalement indépendants. )

Au fait, comment calcule-t-on le diagramme de Voronoï à partir de son dual la triangulation de Delaunay ?

[Kangourou]

salut,

bon, a partir de ton image avec les niveaux de gris, si tu pars d'un point et que tu te dirifges vers un autre point, la valeur des niveaux degris va augmenter (tu t'eloignes du pooint de depart), jusqu'a ec que tu arrievs a mi chemin des 2 points. Ensuite, la valeur va progressivement dimnuer jusqu'a ce que tu arrives au deuxieme point. C'est donc cette transition au milieu qu'il faut detecter.

Un algorithme appele ligne de partage des eaux ('watershed') fait ca tres bien, mais il est au moins aussi difficile a implementer que Voronoi.
Sinon c'est peut-etre possible de faire detecter les limites avec une conditions sur les valeurs de gris dans un voisinage 3x3 : le but est de trouver une zone de transition entre des valeurs descendantes et montantes.

Enfin pour le lien entre vornoi et delaunay :
Le graphe de Vornoi est le dual du graphe de Delaunay, c'est a dire que chaque cellule de vornoi correspond a un sommet de Delaunay, et reciproquement. Le aretes sont en correspondancs 1-1, c'est a dire qu'un lien entre 2 sommets dans le diagramme de voronoi sera un lien entre les centres des 2 cellules dans le diagramme de Delaunay. Cette dualite est meme explitee par certains algos pour callculer les aretes.
Donc si tu as Delaunay et que tu veux Voronoi :
- creer une liste de sommets qui correspondent aux centres des triangles de Delaunay
- pour chaque arete de Delauany, trouer les 2 triangles autour, et creer une arete de Voronoi entre ces 2 sommets de Voronoi qui correspondent a ces triangles.
- eventuellement traitement similaire si tu veux les cellules de voronoi, en partant d'un sommet du Delaunay et en parcourant tous les triangles ou aretes autour.


A+

[echataig]

down

[echataig]

En partant du principe de Kangourou avec les distances, tu peux :

1) étiqueter chaque germe par un identifiant (Les pixels qui ne sont pas des points sont étiquetés par une valeur spéciale signifiant "non étiquetée).
2) A chaque itération, tu note sur chaque point qui augmente d'une valeur son étiquette (c'est à dire l'identifiant du germe dont il est issu).
Après étiquetage, tu compares chaque pixel avec son voisin.
Dès que 2 voisins sont étiquetés par des étiquettes différents, tu les marquent avec une valeur spéciale signifiant "frontière".

Tu obtiendras ainsi tes frontières et des formes polygonales pour tes régions.

Par contre, ça ne satisfait pas la contrainte de taille + ou - égales.
Mais peut-être quand plaçant tes germes d'une façon un peu "contrôlée", ça peut marcher.

à+

[Nyx]

Désolé de remonter ce sujet, je n'ai pas encore finis avec mes cartes

Finalement j'ai réalisé un diagramme de Voronoï en utilisant l'algorithme de Tsai pour la triangulation de Delaunay et les informations de Kangourou pour obtenir le diagramme.

Mais compte tenu du résultat (c'est pour un jeu) je préférai une carte politique semi-aléatoire, c'est à dire une carte sur laquelle les frontières et la séparation terre/mer soit réelle mais où la division des pays reste aléatoire.

Ici j'ai simplement fait un tableau composé de 0(=terre) et de 1(=mer). Puis j'ai regardé dans quelle case du tableau se situe le centre de gravité de chaque région.

Le résultat paraît correcte parce que la résolution est exagérée et parce que la carte de l'Afrique n'est pas très connue.

Avec cette méthode, l'Europe est méconnaissable.


Y a t il un moyen d'imposer les coordonnées de certain sommet du diagramme de Voronoï ? Ainsi j'aurais des frontieres réalistes quelque soit la résolution

[maamar]

lu,

si tu dis frontière ==> je me comprend que Contraint
donc je croix il est facile d'utiliser la triangulation de Delaunay avec contraintes apres essai de reconstituer votre diagramme de Voronoï

information :
pour voir interet du diagramme de voronoï visite le lien suivant www.voronoi.com


un conseil :
si tu utilise l'algo de voronoï je croix que vous etes sur la bonne voix

la structure du draigramme de voronoi ( topologie) te permet de faire pas mal de chose (tres partique)

lien pour la triangulation de Delaunay avec Contrainte ( un mémoire ingénieur en pdf a télécharger)
http://membres.lycos.fr/cnts2003/forums/viewforum.php?f=7&sid=396d967dd642d5e276b3d1fd753aee24

[Nyx]

Si j'ai bien compris, tu proposes des solutions pour forcer une triangulation de Delaunay à utiliser certaines arrêtes ?
Moi je dois prédéfinir des arrêtes de mon diagramme de Voronoï et non pas de la triangulation, suffit-il de forcer les arrêtes mediatrices de mes frontières ?

Je vais essayer de modifier les centres de gravités pour qu'ils collent aux points définissant les frontières.

[pascal_damien]

Salut,


Tu peux ajouter des points qui vont suivre la frontière en suivant cette dernière : tous les x kilomètres tu imagines une droite *perpendiculaire* à la frontière et tu ajoutes un point de chaque côté à la même distance de la frontière sur cette droite. Lorsque la carte est très anguleuse, il faut probablement rapprocher les points de la frontières. Lorsque tu ajoutes ces points, il faut peut-être supprimer ceux aléatoires qui sont trop proches.

Une autre méthode pourrait être de découper les polygones générés en suivant la carte (ou une version simplifiée) et en fusionnant des régions trop petites.

PS : Est-ce que tu es sûr de l'algorithme que tu utilises pour déterminer les régions de voronoï ? Il me semble que toutes les région devraient être convexes, mais je peux me tromper.