C'est un coup long, mais je pensais que je pourrais essayer avant de commencer le saleté.
J'ai un projet pour créer une application qui permettra, pour une station de saisie définie (sommets) et des lignes (bords), c'est-à-dire une réelle carte de certains transports en commun, schématiser une carte donnée dans une carte de métro. J'ai effectué des recherches sur le problème et c'est un problème complet de NP équivalent au problème 3-SAT. J'ai aussi des idées théoriques sur la manière de générer une telle carte, mais elles ne sont pas assez détaillées.
Ce que je recherche est une autre solution existante de ce problème, une sorte de pseudo-code, du code réel dans (presque) tout autre langage de programmation, etc., tout ce qui permettrait de réduire le temps que je dois passer à travailler sur L'algorithme lui-même, qui, en retour, donne-moi plus de temps à travailler sur d'autres aspects de l'application.
Si quelqu'un a déjà vu quelque chose qui peut m'aider, je l'apprécierais beaucoup.
4 Réponses :
Ce n'est que quelques suggestions avec handwaving - prendre avec une pincée de sel.
Ma notion d'une carte "métro" est une case où les lignes tendent à l'une des huit directions et stations cardinales sont régulièrement espacées.
Je suppose que vous essayez de convertir un ensemble de coordonnées réelles en coordonnées "métro".
Je commencerais avec votre route principale (par exemple, une boucle de ville), puis ajoutez progressivement d'autres itinéraires par ordre d'importance.
Pour chaque route, vous souhaitez trouver l'approximation la plus proche qui utilise le moins de lignes droites voyageant dans les huit directions cardinales. Vous pouvez le faire en commençant par la boîte de sélection pour les coordonnées réelles, séparant que dans une grille, puis trouver un itinéraire «métro» de la place de la grille à la place de la grille, puis affinant successivement que la route pour réduire le nombre de courbes sans déformer la carte sans déformer la carte. trop et sans introduire des passages avec d'autres itinéraires si possible.
Ayant fait cela, échelle chaque ligne de sorte que les stations consécutives soient à la même distance de la vue "Metro".
Je suppose que vous voudrez toujours prendre en charge la modification manuelle du résultat.
bonne chance!
Merci pour la réponse, j'avais quelque chose comme ça à l'esprit, y compris la peaufineuse manuelle. J'espérais juste que quelqu'un pourrait avoir un peu de code pour me faire commencer, avant de le faire tout seul.
Si vous Google pour "Métro Map Disaboring Problème" et "Crossing de la ligne de métro" "Vous trouverez de nombreuses références, car elle a été étudiée très activement au cours des 10 dernières années.
Le problème ne semble pas du tout trivial et la traduction des caractéristiques "artistiques" aux contraintes mathématiques est apparemment l'une des tâches les plus difficiles.
Quoi qu'il en soit, voici trois publications que j'ai trouvées intéressantes pour commencer (parmi beaucoup d'autres autres):
Disposition de la carte de métro à l'aide d'optimisation multicritères
Compte tenu du court délai, nous avons fini par mettre en œuvre un algorithme très limité de la nôtre, ce qui était suffisamment bon pour la portée du projet. Si quelqu'un d'autre est intéressé par ce problème, cette publication est un très bon début: www1.informatik.uni-uerzburg.de/pub/wolff/pub/nw-dlhqm-10.p df
Des recherches similaires à votre sujet: http://graphics.stanford.edu/papers/routemaps/
se sent comme un problème de planification. On dirait que vos contraintes difficiles sont:
Chaque station doit être sur un point. Les points sont sur une grille avec une distance de x entre les points (je ferais cette statique sur 2 cm)
Il ne devrait pas y avoir 2 stations sur le même endroit
Il devrait y avoir suffisamment de place pour dessiner l'étiquette de la station. Notez que l'étiquette peut être attribuée à différentes directions du point à laquelle la station est attribuée.
Il devrait y avoir suffisamment de place pour dessiner les lignes de métro.
On dirait que vos contraintes douces sont:
Puis lancez quelque chose comme la planificateur de drooles, Voici un exemple de contraintes difficiles et mous pour l'infirmière Rostering .
"... pour une stations de saisie définie (sommets) et lignes (bords), c'est-à-dire une véritable carte de certains transports en commun, schématiser une carte donnée dans une carte de métro." Dans ce contexte, il n'est pas clair de la différence entre une "carte" et une "carte de métro". Pouvez vous donner un exemple?
Vous devez donner plus de détails sur les différentes contraintes de votre carte de métro, comme la manière dont les noms de la station doivent être affichés, comment les stations où les lignes jointes / Cross doivent-elles être affichées, comment deux lignes suivantes doivent-elles être affichées?
Une carte normale serait une carte dans laquelle les relations entre points de repère et places sont conservées - c'est-à-dire que tout est mis à l'échelle dans des proportions. D'autre part, une carte de métro ne préserve pas ces proportions, mais simplement montre simplement des informations pertinentes de manière visuellement attrayante. En ce moment même, ce n'est pas vraiment important de la manière dont les noms ou les croix seraient affichés, je peux toujours en arriver plus tard. De préférence, des lignes parallèles seraient affichées à côté de l'autre, mais c'est aussi une option, n'importe quelle base que je peux me faire maintenir la main sera bonne.
Quoi qu'il en soit, je pense que vous devriez éditer votre message en essayant de distinguer des contraintes et des préférences réelles. Si toutes vos contraintes ne sont que des préférences, un artiste fera beaucoup mieux qu'un programmeur :)
Essayez d'inclure le [@name] dans vos réponses afin que l'autre partie soit notifiée