google-maps - multiple - google.maps.marker label
Mapa de enrutamiento, al estilo Google Maps? (9)
Eche un vistazo al proyecto del mapa de calles abiertas para ver cómo se aborda este tipo de cosas en un proyecto de software verdaderamente gratuito que utiliza solo datos proporcionados por el usuario y con licencia, y tiene un wiki que contiene elementos que puede resultarle interesantes .
Hace unos años, los chicos involucrados fueron bastante fáciles y respondieron muchas preguntas que tenía, así que no veo ninguna razón por la que todavía no sean un buen grupo.
Siempre me ha intrigado Map Routing, pero nunca encontré ningún buen tutorial introductorio (¡o incluso avanzado!) Sobre él. ¿Alguien tiene punteros, consejos, etc.?
Actualización: principalmente busco indicadores sobre cómo se implementa un sistema de mapas (estructuras de datos, algoritmos, etc.).
En lugar de aprender API para cada proveedor de servicios de mapas (como Gmaps, api de Ymaps) es bueno aprender Mapstraction
"Mapstraction es una biblioteca que proporciona una API común para varias API de mapeo de JavaScript"
Sugeriría que vaya a la URL y aprenda una API general. Hay una buena cantidad de How-Tos también.
Barry Brumitt, uno de los ingenieros de la función de búsqueda de rutas de Google Maps, escribió una publicación sobre el tema que podría ser de su interés:
El camino hacia una mejor búsqueda de ruta 11/06/2007 03:47:00 PM
Todavía tengo que encontrar un buen tutorial sobre enrutamiento, pero hay muchos códigos para leer:
Hay aplicaciones de enrutamiento GPL que usan datos de OpenStreetMap, por ejemplo, Gosmore que funciona en Windows (+ móvil) y Linux. Hay una serie de aplicaciones interesantes que usan los mismos datos, pero gosmore tiene algunos usos interesantes, por ejemplo, la interfaz con sitios web .
El mayor problema con el enrutamiento es la mala información, y nunca se obtienen datos suficientemente buenos. Entonces, si quiere probarlo, mantenga su prueba muy local para que pueda controlar mejor los datos.
A * está mucho más cerca de los algoritmos de mapeo de producción. Requiere bastante menos exploración en comparación con el algoritmo original de Dijikstra.
Desde un punto de vista conceptual, imagine tirar una piedra en un estanque y observar las ondas. Las rutas representarían el estanque y la piedra su posición inicial.
Por supuesto, el algoritmo debería buscar una proporción de n ^ 2 caminos a medida que aumenta la distancia n. Usted tomaría la posición inicial y verificaría todos los caminos disponibles desde ese punto. Luego, recursivamente, pida los puntos al final de esos caminos, etc.
Puede aumentar el rendimiento, al no realizar doble respaldo en una ruta, al no volver a verificar las rutas en un punto si ya se ha cubierto y al renunciar a las rutas que llevan demasiado tiempo.
Una forma alternativa es utilizar el enfoque de feromonas de hormigas, donde las hormigas se arrastran aleatoriamente desde un punto de inicio y dejan un rastro de olor, que acumula más hormigas que cruzan una ruta determinada. Si envía (suficientes) hormigas desde el punto de inicio y el punto final, finalmente la ruta con el aroma más fuerte será la más corta. Esto se debe a que el camino más corto se habrá visitado más veces en un período de tiempo determinado, dado que las hormigas caminan a un ritmo uniforme.
EDITAR @ Spikie
Como explicación adicional de cómo implementar el algoritmo de estanque, se destacan las posibles estructuras de datos necesarias:
Tendrá que guardar el mapa como una red. Esto es simplemente un conjunto de nodes y edges entre ellos. Un conjunto de nodes constituye una route . Un borde une dos nodos (posiblemente ambos el mismo nodo) y tiene un cost asociado, como la distance o el time para atravesar el borde. Un borde puede ser bidireccional o unidireccional. Probablemente lo más simple es tener unidireccionales y duplicar para un viaje de dos vías entre nodos (es decir, un borde de A a B y uno diferente para B a A).
A modo de ejemplo, imagine tres estaciones de ferrocarril dispuestas en un triángulo equilátero apuntando hacia arriba. También hay otras tres estaciones a medio camino entre ellos. Los bordes unen todas las estaciones adyacentes, el diagrama final tendrá un triángulo invertido dentro del triángulo más grande.
Nodos de etiquetas que comienzan desde abajo a la izquierda, yendo de izquierda a derecha y arriba, como A, B, C, D, E, F (F en la parte superior).
Supongamos que los bordes se pueden atravesar en cualquier dirección. Cada borde tiene un costo de 1 km.
Ok, entonces deseamos pasar de la parte inferior izquierda A a la estación superior F. Hay muchas rutas posibles, incluidas las que se duplican, p. Ej., ABCEBDEF.
Tenemos un NextNode rutina, NextNode , que acepta un node y un cost y se llama a sí mismo para cada nodo al que puede viajar.
Claramente, si permitimos que se ejecute esta rutina, eventualmente descubrirá todas las rutas, incluidas las que tienen una longitud potencialmente infinita (por ejemplo, ABABABAB, etc.). Detenimos que esto suceda al verificar contra el cost . Cada vez que visitamos un nodo que no ha sido visitado anteriormente, colocamos tanto el costo como el nodo del que venimos contra ese nodo. Si se ha visitado un nodo antes de verificar el costo existente y si somos más baratos, actualizamos el nodo y continuamos (recursión). Si somos más caros, salteamos el nodo. Si se omiten todos los nodos, salimos de la rutina.
Si golpeamos nuestro nodo objetivo, también salimos de la rutina.
De esta forma se verifican todas las rutas viables, pero crucialmente solo aquellas con el menor costo. Al final del proceso, cada nodo tendrá el costo más bajo para llegar a ese nodo, incluido nuestro nodo objetivo.
Para obtener la ruta, trabajamos hacia atrás desde nuestro nodo objetivo. Como almacenamos el nodo del que venimos junto con el costo, simplemente saltamos hacia atrás para construir la ruta. Para nuestro ejemplo, terminaríamos con algo como:
Nodo A - (Total) Costo 0 - Desde el nodo Ninguno
Nodo B - Costo 1 - Desde el nodo A
Nodo C - Costo 2 - Desde el nodo B
Nodo D - Costo 1 - Desde el nodo A
Nodo E - Costo 2 - Desde el Nodo D / Costo 2 - Desde el Nodo B (esta es una excepción ya que hay un costo igual)
Nodo F - Costo 2 - Desde el nodo D
Entonces, la ruta más corta es ADF.
Desde mi experiencia trabajando en este campo, A * hace el trabajo muy bien. Es (como se mencionó anteriormente) más rápido que el algoritmo de Dijkstra, pero aún es lo suficientemente simple para que un programador ordinariamente competente lo implemente y comprenda.
Construir la red de rutas es la parte más difícil, pero se puede dividir en una serie de pasos simples: obtener todos los caminos; ordenar los puntos en orden; hacer grupos de puntos idénticos en diferentes caminos en intersecciones (nodos); agregue arcos en ambas direcciones donde los nodos se conectan (o en una dirección solo para una carretera de sentido único).
El algoritmo A * está bien documentado en Wikipedia . El lugar clave para optimizar es la selección del mejor nodo de la lista abierta, para lo cual necesita una cola de prioridad de alto rendimiento. Si está usando C ++, puede usar el adaptador de prioridad de STL.
La personalización del algoritmo para enrutar a través de diferentes partes de la red (por ejemplo, peatones, automóviles, transporte público, etc.) a favor de la velocidad, la distancia u otros criterios es bastante fácil. Esto se hace escribiendo filtros para controlar qué segmentos de ruta están disponibles, cuándo construir la red y qué peso se asigna a cada uno.
Se me ocurre otra idea sobre el costo de cada recorrido, pero aumentaría el tiempo y la potencia de procesamiento necesarios para calcular.
Ejemplo: Hay tres maneras en que puedo tomar (donde vivo) para ir del punto A al B, de acuerdo con GoogleMaps. Las unidades de Garmin ofrecen cada una de estas 3 rutas en el cálculo de ruta más Quickest . Después de recorrer cada una de estas rutas muchas veces y promediar (obviamente habrá errores dependiendo de la hora del día, la cantidad de cafeína, etc.), creo que los algoritmos podrían tener en cuenta el número de curvas en el camino para un alto nivel de precisión. , por ejemplo , un camino recto de 1 milla será más rápido que un camino de 1 milla con curvas pronunciadas . No es una sugerencia práctica, pero ciertamente una que utilizo para mejorar el conjunto de resultados de mi viaje diario al trabajo.
¿Por el enrutamiento de mapas, te refieres a encontrar el camino más corto a lo largo de una red de calles?
El algoritmo de ruta más corta de Dijkstra es el más conocido. Wikipedia no tiene una mala introducción: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Hay un applet de Java aquí donde puedes verlo en acción: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html y Google te lleva al código fuente en casi cualquier idioma.
Cualquier implementación real para generar rutas de manejo incluirá bastantes datos en la red de calles que describan los costos asociados con los enlaces y nodos que atraviesan: jerarquía de red vial, velocidad promedio, prioridad de intersección, enlace de señales de tráfico, giros prohibidos, etc.