Algorithme pour les cartes de schématisant (métro)

Question

Ceci est un long shot, mais je pensais que je pourrais essayer avant de commencer le travail sale.

J'ai un projet de construction d'une application qui sera, pour une station d'entrée définies (sommets) et lignes (arêtes), qui est, une véritable carte de certains transports en commun, schématiser une carte donnée dans une carte de métro. Je l'ai fait quelques recherches sur le problème et il est un problème NP-complet équivalent au problème 3-SAT. J'ai aussi quelques idées sur la façon de théorétiques générer une telle carte, mais ils ne sont pas assez détaillés.

Ce que je suis à la recherche est une autre solution existante de ce problème, une sorte de pseudo-code, un code réel (presque) tout autre langage de programmation, etc., tout ce qui réduirait le temps que je dois passer à travailler sur l'algorithme lui-même, qui en retour me donner plus de temps pour travailler sur d'autres aspects de l'application.

Si quelqu'un a déjà vu quelque chose qui peut me aider, je l'apprécie beaucoup.

Answer 1

Si vous Google pour « métro carte mise en page problème » et « passage de la ligne de métro carte », vous trouverez beaucoup de références, car il a été très recherché activement au cours des 10 dernières années.

Le problème ne semble pas du tout trivial, et traduire les caractéristiques « artistiques » à des contraintes mathématiques est apparemment l'une des tâches les plus difficiles.

Quoi qu'il en soit voici trois publications que je trouve intéressant de commencer par (parmi beaucoup d'autres):

Metro Map mise en page à l'optimisation multicritère

Crossing Line Minimisation sur les cartes de métro

La mise en page Metro Carte Problème

HTH!

Answer 2

La recherche qui est similaire à votre sujet: http://graphics.stanford.edu/papers/routemaps/

Answer 3

Ceci est juste une suggestion avec argument qualitatif -. Prendre avec une pincée de sel

Ma notion de carte « métro » est celui où les lignes ont tendance à l'une des huit directions cardinales et stations sont régulièrement espacées.

Je suppose que vous essayez de convertir un ensemble de coordonnées réelles en coordonnées « de métro ».

Je commencerais par votre route principale (par exemple, une boucle de ville), puis ajouter progressivement d'autres voies par ordre d'importance.

Pour chaque itinéraire que vous voulez trouver le plus proche approximation qui utilise le plus petit nombre de lignes droites qui voyagent dans les huit directions cardinales. Vous pouvez le faire en commençant par la zone de délimitation pour les coordonnées réelles, division qui dans une grille, puis de trouver une route « de métro » de la place de la grille à la place de la grille, puis affiner successivement cette route pour réduire le nombre de virages sans déformer la carte trop et sans introduire de croisements avec d'autres voies si possible.

Après avoir fait cela, l'échelle de chaque ligne afin que les stations sont consécutives à la même distance sur la vue « métro ».

Je suppose que vous voulez toujours soutenir manuel du peaufinage résultat.

Bonne chance!

Answer 4

Ressenti comme un problème de planification. On dirait que vos contraintes dures sont:

• Chaque station doit être sur un point. A points sont sur une grille avec une distance de X entre les points (je fais cette statique sur 2cm)

• Il ne doit pas être 2 stations sur le même endroit

• Il devrait y avoir assez de place pour dessiner l'étiquette de la station. Notez que l'étiquette peut être attribué différentes directions du point auquel la station est assignée.

• Il devrait y avoir assez de place pour dessiner les lignes de métro.

On dirait que vos contraintes souples sont:

• Pour chaque station, minimiser la distance de l'emplacement géographique réellement au point attribué à la station.

Alors jeter quelque chose comme planificateur Drools là-dessus, voici un exemple des contraintes dures et douces pour une infirmière rostering .