So erstellen Sie eine Karte aus einem Diagramm

7

Ich möchte eine 2D-Polygonkarte basierend auf Daten zeichnen, die von einer anderen Quelle bereitgestellt wurden, um die Analyse von Aktionen auf der Karte zu vereinfachen. Die Daten haben das folgende Format:

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']
...

Die erste Nummer ist die ID eines Knotens. Die folgende Liste enthält die IDs seiner Nachbarn. Da sich die Anzahl der Nachbarn eines Knotens unterscheidet, muss ich eine Polygonkarte zeichnen.

Also habe ich versucht, Voronoi- Polygone für die Kartendarstellung zu verwenden. Das Problem ist: Wie kann ich die Punkte bestimmen, um alle Nachbarschaftsbeziehungen zu erfüllen? Ich denke, mein erster Versuch ist mehr oder weniger ein Fehler in meinem Versuchs- und Fehlerzyklus. Ich habe das sfdp- Tool von graphviz verwendet , um die Punktpositionen des Graphen zu ermitteln:

Beispieldiagrammdarstellung mit sfdp

Die Verwendung der Positionen der Punkte ergab die folgende Kartendarstellung:

Beispielkarte mit Voronoi-Diagramm

Das Problem dieses Ansatzes besteht darin, dass beispielsweise die Knoten 4 und 1 Nachbarn sind, im Voronoi-Diagramm jedoch nicht aufgrund der Position der Knoten. Für mich ist dieser Ansatz also gescheitert.

Beim Googeln habe ich viele Tutorials gefunden, in denen Karten mit Polygonen oder Kacheln erstellt wurden, aber ich habe noch nicht herausgefunden, wie ich eine Karte für meine angegebenen Daten erstellen kann. Ich denke, es gibt einen Ansatz, bei dem (mehrere) Sechsecke / Dreiecke / Quadrate oder eine Mischung verwendet werden, um das zu erreichen, was ich brauche, aber ich weiß nicht, wonach ich suchen soll.

Gibt es ein Schlüsselwort oder einen Algorithmus, der mir hier helfen kann?

Update / Ergebnis : Der Vollständigkeit halber : Dies ist mein Ergebnis, nachdem ich die Vorschläge der akzeptierten Antwort verwendet habe: Ergebnis

Maggie
quelle
Aus den angegebenen Daten könnten mehrere Karten erstellt werden, insbesondere mit den Punkten 12 und 9, die nur eine Beziehung haben. Ist das ein besonderes Problem?
Lewisjb
@ Pyro: Nein, das ist kein Problem. Es wird nur zur Analyse verwendet.
Maggie
Sie finden einen Algorithmus für dieses doppelte Problem, der als Delaunay-Triangulations- und Voronoi-Diagramme aufgeführt ist.
tinyfiledialogs

Antworten:

12

Was Sie wollen, ist ein duales Diagramm zu erstellen ; Dies ist ein Diagramm, das durch Konvertieren von Flächen in Scheitelpunkte und Verbinden dieser Flächen basierend auf benachbarten Flächen im Originaldiagramm erstellt wird. Beispiel:

Dual Graph

Wie Sie sehen, besteht das Problem darin, dass Sie, wenn Sie das gleiche Layout des Diagramms beibehalten möchten, einige wirklich kurvige Kanten im dualen Diagramm erhalten. Außerdem erhalten Sie häufig ein Multigraph - ein Diagramm, bei dem einige Scheitelpunkte mehrere Kanten zwischen sich haben. Es ist jedoch garantiert planar, also ist das etwas.

Um Ihr Beispiel zu verwenden, können wir das duale Diagramm in den folgenden Schritten erstellen:

Schritt 1: Erstellen Sie für jede Fläche im Originaldiagramm einen Scheitelpunkt

Zentroide und Außenring

Beachten Sie, dass wir einen äußeren "Ring" erstellen, um den äußersten "Scheitelpunkt" darzustellen. Auf diese Weise können wir am Ende ein besser aussehendes Diagramm ohne die verrückten kurvigen Kanten erhalten.

Schritt 2: Verbinden Sie für jede Kante im Originaldiagramm die beiden Flächenscheitelpunkte mit einer Kante

Außerdem müssen Sie etwas gegen diese Kanten unternehmen, die sich nicht überlappen. Die Lücke zwischen 3 und 12 ist besonders problematisch. Diese neuen Kanten müssen möglicherweise biegsam sein, um dies zu ermöglichen. Es ist das, was Sie für ein konkaves Diagramm erhalten.

Kanten

Schritt 3: Spielrisiko

farbige Grafik

Congusbongus
quelle
Danke für den Tipp. Ich habe einen ähnlichen Ansatz vor meinem Voronoi-Ding begonnen, aber ich habe ihn nicht zum Ende gebracht. Ich werde dies tun und dann meine Ergebnisse veröffentlichen.
Maggie
Dies ist auch interessant, wenn es Ihnen hilft, versuchen Sie, Informationen über die Dualität zwischen Voronoi und Delaunay zu erhalten. Dies ist ein guter Anfang, um es zumindest zu verstehen: scicomp.stackexchange.com/questions/771/…
Gustavo Maciel
1
Eine weitere Frage: Welchen Ansatz würden Sie verwenden, wenn Sie nicht die Hilfe von sfdp hätten? Gibt es einen allgemeinen Ansatz zum Erstellen einer geeigneten Diagrammdarstellung, um die erforderlichen Knotenpositionen zu erhalten?
Maggie
@maggie Sie möchten etwas, das planare Diagrammlayouts ausführt . Es ist kein triviales Problem, und ich kann ein bestimmtes Paket nicht empfehlen, aber hier und hier gibt es Optionen .
Congusbongus
1

Wenn Sie nach dem ersten Bild suchen, bei dem jeder Punkt ein kleines Quadrat mit einer bestimmten Farbe ist, müssen Sie die Triangulation des Delaunay erstellen.

Blas Soriano
quelle
1
Dies könnte etwas mehr Inhalt gebrauchen, um die Antwort etwas prägnanter zu gestalten.
Tom 'Blue' Piddock