Google Maps: dado un punto, ¿cómo encontrar todos los puntos a una determinada distancia de la carretera?

Question

En mi aplicación, el GPS selecciona la ubicación del vehículo. Se supone que debe poner marcadores en todos los puntos donde podría estar el vehículo si conduce durante 1 KM en cualquier dirección (tenga en cuenta que las carreteras pueden doblarse muchas veces dentro de su alcance de 1KM).

¿Alguien me puede recomendar cómo hacerlo? Gracias por adelantado.

Answer 1

Este es un problema muy difícil de resolver con la API de Google Maps. El siguiente es un método que es posible que desee considerar:

1. se puede calcular fácilmente un círculo de delimitación de 1 kilometro alrededor de su punto de GPS, y también es fácil de calcular los puntos que caen sobre la circunferencia de este círculo, para cualquier ángulo. Esta distancia será "como los archivos de gallo" y no la distancia real de la carretera, pero es posible que desee echa un vistazo a la siguiente mensaje de desbordamiento de pila para una aplicación concreta de esta:

   How to calculate the latlng of a point a certain distance away from another?

   pantalla con marcadores a 20 intervalos de grados en un círculo de delimitación con un radio de 1 kilometro:

eliminado enlace ImageShack muertos - ¿Cómo calcular el LatLng de un punto a una cierta distancia de otro?

2. También hay un truco para ajustar estos puntos a la calle más cercana. Puede consultar Mike Williams' Snap point to street examples para una buena implementación de esto.

   El cálculo de la distancia de la carretera desde su punto de GPS a cada punto de carretera roto podría hacerse con el servicio de indicaciones de la API de Google Maps. Tenga en cuenta que esto solo funcionará en países que admiten direcciones en Google Maps, pero lo más importante es que la distancia de la carretera casi siempre será superior a 1 km, porque nuestro círculo delimitador tiene un radio de 1 km "en línea recta". Sin embargo, si puede trabajar con información aproximada, esta ya puede ser una posible solución.

3. También puede considerar comenzar con la solución anterior (círculo delimitador de 1 km, calcular x puntos en la circunferencia y ajustarlos a la carretera más cercana), luego calcule la distancia de cada ruta (desde su punto GPS a cada punto de ruptura), y luego puede repetir esto de forma recursiva para cada ruta, cada vez usando un círculo delimitador más pequeño, hasta que llegue a una distancia de la carretera de cerca de 1 km. Puede disminuir el círculo delimitador en cada recursión, en proporción al margen de error, para que su algoritmo sea más eficiente.

---

UPDATE:

he encontrado una aplicación muy ordenado que parece estar usando un método similar al que se he descrito anteriormente:

• Driving Radius (Multiple destinations)

Nota cómo yo Puedes cambiar el intervalo de grados desde la parte superior. Con un intervalo amplio obtendrás resultados rápidos, pero podrías perder algunas rutas fácilmente.

Captura de pantalla:

eliminado enlace ImageShack muertos - Conducir Radio

Answer 2

algoritmo de fuerza bruta natural es construir una lista de todos los nodos posibles teniendo en cuenta cada posible decisión sobre cada cruce.

Dudo que dentro de 1 km usted obtenga más de 10 encrucijadas en promedio y suponiendo promedio de 3 opciones en una encrucijada terminaría con 3^10 - alrededor de 59,049 nodos finales (tenga en cuenta que debe tener 10 encrucijadas en cada rama del camino para llegar al número completo).

En realidad, el número bajaría y supongo 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 el tiempo potencial, pero el n no parece ser tan alto, por lo que podría ser práctico.

Es posible que haya más mejoras y optimizaciones dependiendo de para qué necesita estos nodos (o qué tipo de escenarios consideraría lo suficientemente parecidos para eliminarlos).

Answer 3

Elaborando un poco sobre el enfoque anterior de Daniel, primero quiere encontrar todo el punto dentro de un radio en 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 inicial. Ahora compruebe que los nodos estén conectados y que no haya ningún nodo flotando que no pueda alcanzar. Ahora crea un "shortest path tree" comenzando desde tu nodo de vehículo.

El árbol le dará las rutas más cortas desde su nodo inicial a todos los otros nodos. Tenga en cuenta que si comienza creando rutas en los nodos más lejanos, cualquier subruta también será la ruta más corta hacia esos nodos en el camino. Asegúrese de etiquetar esos nodos en 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.

Answer 4

1. Lista de todos los nodos posibles teniendo en cuenta cada posible decisión sobre cada cruce (Pero cómo hacerlo automáticamente?
2. algoritmo de Uso Dijkstra`s para encontrar cierra el camino a todos los puntos.
3. datos de visualizar. (que es un poco complicado, porque no puede haber un zonas fuera de cobertura dentro del área accesible.