Algoritmo de mapas esquematizar (metro)

Question

Esta es una posibilidad remota, pero pensé que podría intentar antes de comenzar el trabajo sucio.

Tengo un proyecto para construir una aplicación que será, durante las estaciones de entrada definidos (vértices) y líneas (bordes), es decir, un mapa real de un medio de transporte público, esquematizar un mapa dado en un mapa del metro. He hecho algunas investigaciones sobre el problema y es un problema NP-completo equivalente al problema 3-SAT. También tengo algunas ideas teóricas sobre cómo generar un mapa de este tipo, pero no son suficientemente detalladas.

Lo que estoy buscando es cualquier otra solución existente de este problema, una especie de pseudo-código, un código real en (casi) cualquier otro lenguaje de programación, etc., todo lo que reduciría el tiempo que necesito para pasar a trabajar en el algoritmo en sí, lo que a su regreso darme más tiempo para trabajar en otros aspectos de la aplicación.

Si alguien ha visto algo que me puede ayudar, se lo agradecería mucho.

Answer 1

Si Google de "mapa de metro problema de diseño" y "mapa de metro de la línea de cruce" encontrará una gran cantidad de referencias, ya que se ha investigado de forma muy activa en los últimos 10 años.

El problema parece no trivial en absoluto, y la traducción de las características "artísticos" a las limitaciones matemáticas es aparentemente una de las tareas más difíciles.

De todos modos aquí hay tres publicaciones que he encontrado interesante para comenzar con (entre muchos, muchos otros):

Mapa del metro diseño mediante la optimización multicriterio

línea que cruza Minimización de Mapas Metro

El mapa del metro Disposición Problema

HTH!

Answer 2

Investigación que es similar a su tema: http://graphics.stanford.edu/papers/routemaps/

Answer 3

Esto es sólo alguna sugerencia con handwaving -. Tomar con una pizca de sal

Mi noción de un mapa "metro" es uno donde las líneas tienden a una de las ocho direcciones cardinales y las estaciones están espaciados regularmente.

Estoy asumiendo que usted está tratando de convertir un conjunto de coordenadas reales en coordenadas "Metro".

Yo empezaría con la ruta principal (por ejemplo, un bucle de la ciudad), a continuación, añadir gradualmente otras rutas en orden de importancia.

Para cada ruta que desea encontrar la aproximación más cercana que utiliza el menor número de líneas rectas que viajan en las ocho direcciones cardinales. Es posible hacer esto comenzando con el cuadro delimitador para las coordenadas reales, partiendo de que en una rejilla, a continuación, encontrar una ruta "metro" de cuadrícula a cuadrícula, a continuación, refinando sucesivamente esa ruta para reducir el número de curvas sin distorsionar el mapa demasiado y sin introducir cruces con otras rutas, si es posible.

Una vez hecho esto, la escala de cada línea para que las estaciones son consecutivos a la misma distancia de la vista "metro".

Mi conjetura es que usted todavía quiere apoyar ajuste manual del resultado.

Buena suerte!

Answer 4

Se siente como un problema de planificación. Parece que tu restricciones duras son:

• Cada estación debe estar en un punto. A puntos están en una cuadrícula con una distancia de X entre los puntos (me gustaría hacer esta estática en 2 cm)

• Hay no debería ser 2 estaciones en el mismo lugar

• No debe haber espacio suficiente para extraer la etiqueta de la estación. Tenga en cuenta que la etiqueta se puede asignar diferentes direcciones desde el punto al que se asigna la estación.

• No debe haber espacio suficiente para dibujar las líneas de metro.

Parece que tu restricciones blandas son:

• Para cada estación, reducir al mínimo la distancia de ubicación geográfica en realidad hasta el punto asignado a la estación.

A continuación, tirar algo así como Drools Planner en él, aquí es un ejemplo de restricciones duras y suaves para una enfermera rostering .