Algorithmus für schematisierende (Metro) Karten

Question

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

Ich habe ein Projekt, um eine Anwendung zu erstellen, die für eine definierte Eingabestationen (Vertices) und Linien (Kanten), dh eine echte Karte von einigen öffentlichen Verkehrsmitteln, eine bestimmte Karte in eine U-Bahn-Karte schematisiert . Ich habe etwas über das Problem geforscht und es ist ein NP-vollständiges Problem, das dem 3-SAT-Problem entspricht. Ich habe auch einige theoretische Ideen, wie man solch eine Karte erzeugt, aber sie sind nicht detailliert genug.

Was ich suche ist eine andere existierende Lösung dieses Problems, eine Art Pseudo-Code, ein realer Code in (fast) jeder anderen Programmiersprache usw., alles, was die Zeit reduzieren würde, die ich für die Arbeit brauche auf dem Algorithmus selbst, was mir wiederum mehr Zeit gibt, an anderen Aspekten der Anwendung zu arbeiten.

Wenn jemand jemals etwas gesehen hat, das mir helfen kann, würde ich es sehr schätzen.

Answer 1

Wenn Sie nach "metro map layout problem" und "metro map line crossing" googlen, werden Sie viele Referenzen finden, da es in den letzten 10 Jahren sehr aktiv recherchiert wurde.

Das Problem scheint überhaupt nicht trivial zu sein, und die Übersetzung der "künstlerischen" Merkmale in mathematische Bedingungen scheint eine der schwierigsten Aufgaben zu sein.

hier sind jedenfalls drei Publikationen, die ich mit (unter vielen, vielen anderen) interessant zu beginnen gefunden:

Metro Map Layout Using Multicriteria Optimization

Line Crossing Minimization on Metro Maps

The Metro Map Layout Problem

HTH!

Answer 2

Dies ist nur ein Vorschlag mit Handwaving - nehmen Sie mit einer Prise Salz.

Meine Vorstellung von einer "U-Bahn" -Karte ist eine, wo Linien zu einer der acht Himmelsrichtungen neigen und Stationen regelmäßig voneinander getrennt sind.

Ich nehme an, Sie versuchen, eine Reihe von realen Koordinaten in "U-Bahn" -Koordinaten zu konvertieren.

Ich würde mit Ihrer Hauptroute beginnen (z. B. eine Stadtschleife), dann schrittweise andere Routen in der Reihenfolge ihrer Wichtigkeit hinzufügen.

Für jede Route möchten Sie die nächstgelegene Approximation finden, bei der die geringste Anzahl von Geraden in den acht Himmelsrichtungen verwendet wird. Sie können dies tun, indem Sie mit der Begrenzungsbox für die echten Koordinaten beginnen, diese in ein Gitter aufteilen und dann eine "U-Bahn" -Route vom Gitterquadrat zum Gitterquadrat finden und dann diese Route sukzessive verfeinern, um die Anzahl der Biegungen zu reduzieren, ohne die Karte zu verzerren zu viel und ohne Kreuzungen mit anderen Routen einzuführen, wenn irgend möglich.

Danach skalieren Sie jede Zeile so, dass aufeinanderfolgende Stationen in der "Metro" -Ansicht die gleiche Entfernung haben.

Meine Vermutung ist, dass Sie immer noch manuelle Feinabstimmung des Ergebnisses unterstützen wollen.

Viel Glück!

Answer 3

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

Answer 4

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

• Jede Station auf einem Punkt sein muss. Ein Punkt auf einem Raster mit einem Abstand von X zwischen den Punkten (I würde dies auf 2cm statisch machen)

• Es soll nicht 2 Stationen an der gleichen Stelle seines

• Es sollte genug Platz sein, zu zeichnen das Stationslabel. Beachten Sie, dass dem Label von dem Punkt aus, dem die Station zugewiesen ist, unterschiedliche Richtungen zugewiesen werden können.

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

Sieht aus wie Ihre Soft Constraints sind:

• Für jede Station, die tatsächlich geographische Lage Distanz zu dem mit der Station zugewiesenen Punkt minimieren.

Dann werfen Sie etwas wie Drools Planner darauf, here's an example of hard and soft constraints for nurse rostering.