algorithm - saber - medir distancias google maps android
Google Maps: dado un punto, ¿cómo encontrar todos los puntos a una distancia de carretera determinada? (4)
En mi aplicación, el GPS selecciona la ubicación del vehículo. Entonces se supone que debe colocar marcadores en todos los puntos donde podría estar el vehículo si se conduce por 1 KM en cualquier dirección (tenga en cuenta que las carreteras pueden bifurcarse muchas veces dentro de su alcance de 1 km).
¿Puede alguien sugerirme cómo hacer esto? Gracias por adelantado.
- Enumere todos los nodos posibles teniendo en cuenta cada decisión posible en cada encrucijada (¿Pero cómo hacerlo automáticamente?
- Utilice el algoritmo de Dijkstra para encontrar la ruta de cierre a todos los puntos.
- Visualizar datos. (Eso es un poco complicado, porque puede haber áreas inalcanzables dentro del área accesible).
Al elaborar un poco el enfoque de Daniel anterior, primero debe buscar todos los puntos dentro de un radio de línea recta desde su origen. Ese es tu conjunto inicial de nodos. Ahora incluya TODOS los bordes incidentes a esos nodos y otros nodos en su conjunto de inicio. Ahora verifique que los nodos estén conectados y que no haya nodos flotando alrededor que no pueda alcanzar. Ahora cree un " árbol de ruta más corto " a partir de su nodo de vehículo.
El árbol le dará las rutas más cortas desde su nodo inicial a todos los demás nodos. Tenga en cuenta que si comienza creando rutas en los nodos más alejados, cualquier ruta secundaria también será la ruta más corta a esos nodos en el camino. Asegúrese de etiquetar esos nodos en las subrutas a medida que continúa para que no tenga que calcularlos. En el peor de los casos, debe desarrollar una ruta más corta para todos los nodos, pero en la práctica esto debería tomar mucho menos tiempo.
El algoritmo de fuerza bruta natural es construir una lista de todos los nodos posibles teniendo en cuenta cada decisión posible en cada encrucijada.
Dudo que dentro de 1 km obtendría más de 10 cruces en promedio y, asumiendo un promedio de 3 opciones en un cruce, terminaría con 3 ^ 10 - alrededor de 59,049 nodos finales (tenga en cuenta que debe tener 10 cruces en cada rama del camino para llegar al numero completo).
En realidad, el número bajaría y asumiría que llegar al mismo nodo por una ruta diferente no sería raro, especialmente en las ciudades.
Este enfoque le daría una respuesta exacta (siempre que tenga un buen mapa de calles como entrada). Es tiempo potencial, pero la n no parece ser tan alta, por lo que podría ser práctico.
Podrían ser posibles mejoras y optimizaciones adicionales dependiendo de para qué necesita estos nodos (o qué tipo de escenarios consideraría lo suficientemente similares como para eliminarlos).
Este es un problema muy difícil de resolver con la API de Google Maps. El siguiente es un método que tal vez quiera considerar:
Puede calcular fácilmente un círculo delimitador de 1 km alrededor de su punto GPS, y también es fácil calcular los puntos que caen en la circunferencia de este círculo, para cualquier ángulo. Esta distancia será "como los archivos de cuervo" y no la distancia real de la carretera, pero es posible que desee revisar la siguiente publicación de Desbordamiento de pila para una implementación concreta de esto:
¿Cómo calcular la latencia de un punto a cierta distancia de otro?
Captura de pantalla con marcadores a intervalos de 20 grados en un círculo delimitador con un radio de 1 km:
enlace de ImageShack eliminado: ¿Cómo calcular el tiempo de espera de un punto a cierta distancia de otro?
También hay un truco para ajustar estos puntos a la calle más cercana. Puede ver ejemplos de puntos de la calle de Mike Williams para una buena implementación de esto.
El cálculo de la distancia de la carretera desde su punto GPS a cada punto de la carretera se puede hacer con el servicio de direcciones de la API de Google Maps. Tenga en cuenta que esto solo funcionará en países que admitan direcciones en Google Maps, pero lo que es más importante, la distancia de la carretera será casi siempre mayor a 1 km, porque nuestro círculo de delimitación tiene un radio de 1 km "a vuelo de pájaro". Sin embargo, si puede trabajar con información aproximada, esta puede ser una solución posible.
También puede considerar comenzar con la solución anterior (circunvolución de 1 km, calcular x puntos en la circunferencia y ajustarlos a la carretera más cercana), luego calcular la distancia de ruta de cada ruta (desde su punto GPS hasta cada punto ajustado), y luego puede repetir esto recursivamente para cada ruta, cada vez utilizando un círculo de delimitación más pequeño, hasta que alcance una distancia de la carretera cercana a 1 km. Puede disminuir el círculo delimitador en cada recursión, en proporción al margen de error, para hacer que su algoritmo sea más eficiente.
ACTUALIZAR:
Encontré una implementación muy clara que parece estar usando un método similar al descrito anteriormente:
Observe cómo puede cambiar el intervalo de grados desde la parte superior. Con un amplio intervalo obtendrá resultados rápidos, pero podría perder fácilmente algunas rutas.
Captura de pantalla:
eliminado enlace de ImageShack muerto - Radio de conducción