Dado:

Coordenada (X, Y), que é a posição de um veículo.Matriz de (X, Y), que são vértices em uma polilinha. Observe que a polilinha consiste apenas em segmentos retos, sem arcos.

O que eu quero:

Para calcular se o veículo está à esquerda ou à direita da polilinha (ou no topo, é claro).

Minha abordagem:

Iterar em todos os segmentos de linha e calcular a distância de cada segmento. Então, para o segmento mais próximo, você faz um simples teste à esquerda (como explicadoAqui por exemplo).

Possíveis problemas:

Quando três pontos formam um ângulo menor que 90 graus (como mostrado no sopro da imagem), surge um cenário mais complicado. Quando o veículo estiver no segmento vermelho, conforme mostrado abaixo, o segmento mais próximo pode ser um dos dois. No entanto, oà esquerda teste produzirácerto se o primeiro segmento for escolhido como o segmento mais próximo eesquerda de outra forma. Podemos ver facilmente (pelo menos, espero) que o resultado correto deve ser que o veículo éesquerda da polilinha.

Minha pergunta:

Como possoelegantemente, mas principalmenteeficientemente cuidar dessa situação específica?

Minha correção até agora:

Calcule para ambos os segmentos um ponto nesse segmento, começando do ponto de vértice.Calcule a distância do veículo para ambos os pontos, usando a distância euclidianaMantenha o segmento para o qual o ponto computado é o mais próximo.

Eu não estou muito feliz com essa correção, porque eu sinto que estou perdendo uma solução muito mais elegante, minha correção parece bastante "hacky". A eficiência é fundamental, porque é usada em um sistema embarcado em tempo real.

A base de código existente está em C ++, portanto, se você quiser escrever em um idioma específico, o C ++ tem minha preferência. Obrigado!

[editar] eu mudeiminha correção, de um ponto perpendicular para um ponto paralelo, como eu acho que é mais fácil seguir o segmento de linha do que calcular o normal externo.