Algorithmus zur Schematisierung (U-Bahn) Karten

Question

Dies ist eine lange gedreht, aber ich dachte, ich könnte versuchen, bevor die schmutzige Arbeit beginnen.

Ich habe ein Projekt bekommt eine Anwendung zu erstellen, das wird, für eine definierte Eingabestationen (Knoten) und Linien (Kanten), die eine echte Karte von einigen öffentlichen Verkehrsmittel ist, um eine gegebene Karte in eine U-Bahn-Karte schematisieren. Ich habe einige der Forschung über das Problem gemacht und es ist ein NP-vollständiges Problem entspricht dem 3-SAT Problem. Ich habe auch einige theoretische Ideen, wie man eine solche Karte zu erzeugen, aber sie sind nicht detailliert genug.

Was ich suche ist eine andere bestehende Lösung dieses Problems, eine Art von Pseudo-Code, einige echte Code in (fast) jede andere Programmiersprache usw., alles, was die Zeit, die ich brauche reduzieren würde ausgeben Arbeits der Algorithmus selbst, die sich auf andere Aspekte der Anwendung im Gegenzug geben Sie mir mehr Zeit für die Arbeit.

Wenn jemand hat jemals etwas gesehen, die mir helfen können, ich es schätzen würde sehr viel.

Answer 1

Wenn Sie für „U-Bahn-Karte Layout-Problem“ google und „U-Bahn-Karte Linie crossing“ Sie werden eine Menge von Referenzen finden, da sie sehr aktiv in den letzten 10 Jahren erforscht worden ist.

Das Problem scheint nicht trivial überhaupt, und die Übersetzung der „künstlerischen“ Funktionen mathematische Einschränkungen ist scheinbar eine der schwierigsten Aufgaben.

Wie auch immer hier sind drei Publikationen, die ich interessant fand, mit zu beginnen (unter vielen, vielen anderen):

Metro Map-Layout Mit Multi Optimierung

Linie Crossing Minimierungs auf Metro Karten

Das Metro-Karte Layout-Problem

HTH!

Answer 2

Forschung, die zu Ihrem Thema ähnlich ist: http://graphics.stanford.edu/papers/routemaps/

Answer 3

Dies ist nur einiger Vorschlag mit handwaving -. Nehmen mit einer Prise Salz

Meine Vorstellung einer Karte „U-Bahn“ ist, wo Linien neigen dazu, eine der acht Himmelsrichtungen und Stationen werden regelmäßig angeordnet sind.

Ich gehe davon aus Sie versuchen, eine Reihe von realen Koordinaten in „U-Bahn“ Koordinaten zu konvertieren.

würde ich mit Ihrer Hauptroute beginnt (zum Beispiel eines Stadtkreis), fügen Sie dann schrittweise andere Wege, um von Bedeutung.

Für jede Route, die Sie an die nächste Annäherung finden möchten, die die geringste Anzahl von geraden Linien verwenden in den acht Himmelsrichtungen reisen. Sie könnten dies tun, indem mit dem Begrenzungsrahmen für die realen Koordinaten Start Splitting, dass in ein Gitter, dann einen „U-Bahn“ Weg vom Planquadrat zu Planquadrat findet, dann verfeinert nacheinander diesen Weg die Anzahl der Kurven zu reduzieren, ohne die Karte zu verzerren zu viel und ohne Kreuzungen mit anderen Routen, wenn überhaupt möglich eingeführt werden.

Nachdem das getan, um jede Zeile skalieren, so dass aufeinanderfolgende Stationen im gleichen Abstand auf der „U-Bahn“ Ansicht sind.

Meine Vermutung ist, werden Sie noch manuelle Anpassungen des Ergebnisses unterstützen wollen.

Viel Glück!

Answer 4

Man fühlt sich wie ein Planungsproblem. Sieht aus wie Ihre harte Beschränkungen sind:

• Jede Station muss an einem Punkt sein. A Punkte sind auf einem Raster mit einem Abstand von X zwischen den Punkten (ich würde diese statisch auf 2cm machen)

• Es sollte nicht mehr als 2 Stationen an der gleichen Stelle sein

• Es sollte genug Platz sein, um die Station Etikett zu ziehen. Beachten Sie, dass das Etikett verschiedene Richtungen von dem Punkt zugeordnet werden kann, zu dem die Station zugeordnet ist.

• Es sollte genug Platz sein, um die U-Bahn-Linien zu zeichnen.

Sieht aus wie Ihre Soft Constraints sind:

• Für jede Station, minimiert die tatsächlich geographische Lage Distanz zu dem Punkt, an die Station zugewiesen.

Dann etwas wie geifert Planner auf sie werfen, hier ist ein Beispiel von harten und weichen Einschränkungen für Krankenschwester rostering .