Je veux dessiner une carte polygonale 2D basée sur les données fournies par une autre source pour faciliter l'analyse des actions sur la carte. Les données ont le format suivant:
1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...Le premier nombre est l'ID d'un nœud, la liste suivante contient les ID de ses voisins. Comme le nombre de voisins d'un nœud diffère, j'ai besoin de dessiner une carte polygonale.
J'ai donc essayé d'utiliser des polygones de Voronoï pour la représentation cartographique. Le problème est: comment déterminer les points pour satisfaire toutes les relations de voisinage? Je suppose que mon premier essai est plus ou moins une erreur dans mon cycle d'essais et d'erreurs. J'ai utilisé l' outil sfdp de graphviz pour obtenir les positions des points du graphique:
L'utilisation des positions des points a donné la représentation cartographique suivante:
Le problème de cette approche est que, par exemple, les nœuds 4 et 1 sont voisins, mais dans le diagramme de Voronoï, ils ne le sont pas à cause de la position des nœuds. Donc pour moi, cette approche a échoué.
Google, j'ai trouvé beaucoup de tutoriels générant des cartes avec des polygones ou des tuiles mais je n'ai pas encore découvert comment je peux créer une carte pour mes données données. Je suppose qu'il existe une approche utilisant (plusieurs) hexagones / triangles / carrés ou un mélange pour atteindre ce dont j'ai besoin mais je ne sais pas ce que je vais chercher.
Y a-t-il un mot clé ou un algorithme qui peut m'aider ici?
Mise à jour / résultat : pour être complet: voici mon résultat après avoir utilisé les suggestions de la réponse acceptée:
Réponses:
Ce que vous voulez, c'est produire un double graphique ; c'est-à-dire un graphique produit en convertissant des faces en sommets et en les connectant en fonction des faces adjacentes dans le graphique d'origine. Exemple:
Le problème, comme vous pouvez le voir, est que si vous souhaitez conserver la même disposition du graphique, vous obtiendrez des bords vraiment sinueux dans le graphique double. En outre, vous vous retrouverez souvent avec un multigraph - un graphique où certains sommets ont plusieurs bords entre eux. Il est cependant garanti d'être planaire, c'est donc quelque chose.
Pour utiliser votre exemple, nous pouvons produire le double graphique dans les étapes suivantes:
Étape 1: pour chaque face du graphique d'origine, créez un sommet
Notez que nous créons un "anneau" extérieur pour représenter le "sommet" le plus à l'extérieur - c'est ainsi que nous pouvons avoir un graphique plus joli à la fin, sans les bords courbés fous.
Étape 2: Pour chaque arête du graphique d'origine, connectez les deux faces-sommets avec une arête
De plus, vous devrez faire quelque chose pour que ces bords ne se chevauchent pas. L'écart entre 3 et 12 est particulièrement problématique. Ces nouveaux bords peuvent avoir besoin d'être pliés pour que cela soit possible. C'est ce que vous obtenez pour avoir un graphique concave.
Étape 3: Jouer le risque
la source
Si la première image, où chaque point est un petit carré avec une certaine couleur, est ce que vous recherchez, vous devez construire la triangulation de Delaunay.
la source