Dado:

Coordenada (X, Y), que es la posición de un vehículo.Array de (X, Y) 's, que son vértices en una polilínea. Tenga en cuenta que la polilínea consiste solo en segmentos rectos, no arcos.

Lo que quiero:

Para calcular si el vehículo está a la izquierda oa la derecha de la polilínea (o en la parte superior, por supuesto).

Mi acercamiento:

Iterar sobre todos los segmentos de línea y calcular la distancia a cada segmento. Luego, para el segmento más cercano, realice una prueba de izquierda simple (como se explicaaquí por ejemplo).

Posibles problemas:

Cuando tres puntos forman un ángulo menor de 90 grados (como se muestra en el golpe de imagen), surge un escenario más complicado. Cuando el vehículo está en el segmento rojo como se muestra a continuación, el segmento más cercano puede ser uno de los dos. sin embargo, elizquierda de la prueba rendiráCorrecto si el primer segmento es elegido como el segmento más cercano, yizquierda de otra manera. Podemos ver fácilmente (al menos, espero) que el resultado correcto debería ser que el vehículo seaizquierda de la polilínea.

Mi pregunta:

Cómo puedoesmeradamente, pero principalmenteeficientemente ¿Atender esta situación específica?

Mi solución hasta ahora:

Calcule para ambos segmentos un punto en ese segmento, comenzando desde el punto del vértice.Calcule la distancia desde el vehículo a ambos puntos, utilizando la distancia euclidianaMantenga el segmento para el cual el punto computado es el más cercano.

No estoy muy contento con esta solución, porque siento que me falta una solución mucho más elegante, mi solución se siente más bien "intrépida". Sin embargo, la eficiencia es clave, ya que se utiliza en un sistema integrado en tiempo real.

La base de código existente está en C ++, por lo que si desea escribir en un idioma específico, C ++ tiene mi preferencia. ¡Gracias!

[editar] Cambiémi arreglo, desde un punto perpendicular a un punto paralelo, ya que creo que es más fácil seguir el segmento de línea que calcular la normal exterior.