Enrutamiento geoespacial

Soy un programador de logística, y me han pedido que descubra si un punto de GPS está "fuera de ruta" cuando la ruta consiste en una serie de puntos geoespaciales (latitud, longitud).Enrutamiento geoespacial

¿Cuál es el mejor algoritmo para determinar si un punto está cerca de la ruta? Usaré C# y SQL Server, pero realmente eso no importa mucho si sé qué algoritmo usar.

he considerado

Encontrar a los dos puntos más cercanos y determinar si el área del triángulo está por encima de un límite específico.
Usando vectores para todos los pares de puntos y luego verificando si alguno de ellos es "similar" al vector definido por el punto de GPS y al punto que determiné que es "siguiente" en la ruta.

No tengo un título en matemáticas, pero probablemente pueda manejar cualquier cosa con los términos correctos y un motor de búsqueda.

Tendré que hacer al menos 4000 cálculos por hora, por lo que probablemente no sea aceptable utilizar una solución de mapeo debido al volumen.

Fuente

2012-01-18 Doug Heeren

lo que has pedido es una pregunta interesante. Esa solución de superficie-área-de-triángulo no funcionaría porque dos puntos muy alejados generarían un triángulo con una gran área de superficie, incluso cuando el punto está solo ligeramente fuera de la ruta. No estoy seguro de tener una mejor solución. Gracias por darme algo en qué pensar. –

¿Qué versión de SQL Server estás usando? ¿Tiene algún atributo sobre la ubicación del autobús que no sea lat/long?¿Qué tal la identificación del autobús, la identificación de la ruta, etc. que puede vincularse con la ruta/ruta correcta en la que debería estar? – RyanDalton

@RyanDalton 2005 desafortunadamente. Según tengo entendido, 2012 tuvo algunas características bastante agradables con respecto a los datos espaciales. No estoy por encima de usar mongo o alguna otra base de datos, pero eso terminará siendo un poco más trabajo para configurar y mantener otra base de datos con información en tiempo real. –

Google para "Along-track distance" y debe encontrar las fórmulas comúnmente utilizadas en la aviación. Alternativamente, el cross-track distance también podría ser lo que desee.

Fuente

2012-01-18 21:57:17

Gracias, esta parece ser la respuesta que estaba buscando. –

¿Puede tomar su ruta existente como una secuencia de segmentos de línea en 2-D, luego tomar su punto de consulta y encontrar el punto más cercano y el segmento de línea más cercano? La distancia hasta ese segmento de punto/línea más cercano sería la distancia que le interese.

Si te apegas a latitudes relativamente bajas (menos de 60 grados) es posible que puedas tratar la latitud y la longitud como si fueran planas, como en una proyección de Mercator.

De lo contrario, podría transformar el sistema de coordenadas en relación con un gran círculo que se ejecute a través de algunos de los puntos de ruta.

A menos que tenga millones de puntos de ruta, no debería tener problemas con el tiempo de CPU.

Fuente

2012-01-18 22:08:43

Esa es una de las fórmulas que he considerado, pero he encontrado casos en los que simplemente no funcionará según la forma de la ruta. La mayoría de ellos no están cerca de una línea recta y algunos de ellos se duplican. Se complica aún más cuando se trata de tiempo, pero guardé eso para otra pregunta. –

¿Qué hay de la siguiente ...

iterar a través de todos los segmentos de línea

lineSegSlope = Calcular pendiente para cada segmento de línea

dibujar una línea de simulación desde el punto en cuestión que se cruza con la línea actual segmento. esto se hace invirtiendo LineSegSlope y multiplicando por -1 para obtener la nueva pendiente, luego sustituye el punto objetivo X, Y y la nueva pendiente en y-y1 = b * (x-x1). Su X entra en x1, su Y entra en Y1, y su nueva Pendiente va a B.

hacer una ecuación para el segmento de línea.

si dibuja las dos líneas una encima de la otra, deben hacer una X donde cada esquina es de 90 grados.

calcular la intersección de las dos líneas

calcular la distancia entre el punto de intersección y el nuevo punto.Si es mayor que algún valor tolerable, el nuevo punto está demasiado lejos.

esto parece un desastre, pero espero que funcione.

Fuente

2012-01-18 22:26:17

El ángulo de los puntos en la ruta versus el punto en cuestión es lo que desaprovecha cuando lo razoné. Si el segmento de línea está lejos del punto, pero el ángulo de los dos puntos de la ruta es tal que la línea está muy cerca del punto cuando se extiende, producirá una respuesta incorrecta. Estoy luchando por entender esto un poco, así que puedo tener una respuesta incorrecta con esto. –

Veo lo que dices, buena captura. Creo que en ese caso, sin embargo, los extremos reales de los segmentos de línea serían los puntos más cercanos. Luego puede calcular la distancia desde el punto objetivo hasta el segmento de línea. Pequeño problema divertido que tienes aquí. –

Un enfoque ingenuo sería insertar el nuevo punto GPS en varios lugares a lo largo de la ruta. Comience insertándolo antes de su primer punto P0, luego entre su primer y segundo punto P0, y P1, y así sucesivamente hasta que intente insertarlo como el último punto. Cada vez que intente insertarlo en una ubicación, calcule la distancia total para el circuito y guarde la distancia total más corta. Esto se puede acelerar precomprimiendo las distancias de las piernas y almacenando esa suma. Compruebe la distancia restando la distancia de la pierna para la pierna en la que está insertando el nuevo punto, y agregando la nueva distancia desde el punto P (n) a su punto de GPS a P (n + 1). Si la distancia total más corta está dentro de su nivel de tolerancia, la puede aceptar.

Probablemente este no sea el "mejor" algoritmo (dependiendo de su definición de mejor) pero es O (n) en el número de puntos en su ruta para la complejidad del tiempo y el espacio. Por lo tanto, a menos que tenga una enorme cantidad de puntos en su ruta, cada cheque debería ser bastante menor que un segundo, por lo que debe cumplir con los requisitos de tiempo.

Además, asegúrese de utilizar haversine distance equations al calcular la distancia entre puntos consecutivos en su ruta.

Fuente

2012-01-18 22:27:20 andand

Lo mejor para mí es rápido y preciso en una gran parte de las circunstancias. El nivel de tolerancia en esta situación deberá crecer cuando la distancia entre los puntos en la ruta sea mayor ¿no? –

voy a tener que hacer por lo menos 4000 cálculos de una hora así que usar una solución mapeo probablemente no es aceptable debido a volumen.

De hecho, este es un ejemplo PERFECTO donde una solución de mapeo sería beneficioso. No es su "mirar un mapa y determinar la distancia" tradicional, sino "dejar que la base de datos determine cuál es la ruta más cercana a su punto de GPS."

Como dice que no se opone a utilizar una base de datos diferente, podría considerar :

SQL Server 2008, que tiene Spatial Database Engine funciones o
PostgreSQL con la extensión de código abierto PostGIS (espacial), que tiene significativamente más funciones de análisis espacial que MS SQL 2008.

Eche un vistazo a la función PostGIS ST_Distance o la función MS SQL Server 2008 STDistance. Este es un buen blog entry que describe los beneficios de SQL2005 frente a SQL2008.

También puede considerar leer (o solicitar una asignación más detallada) publicaciones en gis.stackexchange. Todo ese grupo está dedicado al análisis espacial. Algunas buenas discusiones para que miren sería

Fuente

2012-01-19 22:26:12 RyanDalton

Gracias. Tuve un amigo que me sugirió gis.stackexchange también. La velocidad es mi preocupación con el uso de una solución de mapeo. Tengo que hacer un mínimo de 4000 de estas por hora. Pero tienes razón, es probablemente la solución más precisa. –

Enrutamiento geoespacial

Respuesta

Cuestiones relacionadas