Given:

(X,Y) coordinate, which is the position of a vehicle. Array of (X,Y)'s, which are vertices in a polyline. Note that the polyline consists of straight segments only, no arcs.

What I want:

To calculate whether the vehicle is to the left or to the right of the polyline (or on top, ofcourse).

My approach:

Iterate over all line-segments, and compute the distance to each segment. Then for the closest segment you do a simple left-of test (as explained here for instance).

Possible issues:

When three points form an angle smaller than 90 degrees (such as shown in the image blow), a more complicated scenario arises. When the vehicle is in the red segment as shown below, the closest segment can be either one of the two. However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise. We can easily see (at least, I hope), that the correct result should be that the vehicle is left of the polyline.

My question:

How can I elegantly, but mostly efficiently take care of this specific situation?

My fix so far:

Compute for both segments a point on that segment, starting from the vertex point. Compute the distance from the vehicle to both of the points, using Euclidian distance Keep the segment for which the computed point is the closest.

Я не очень доволен этим исправлением, потому что мне кажется, что я упустил гораздо более элегантное решение, а мое исправление выглядит довольно "хакерским". Эффективность является ключевым моментом, поскольку она используется в встроенной системе реального времени.

Существующая кодовая база находится на C ++, поэтому, если вы хотите писать на определенном языке, C ++ имеет мои предпочтения. Спасибо!

[edit] Я изменилсяmy fixот перпендикулярной точки к параллельной точке, так как я думаю, что легче следовать за отрезком, чем вычислять внешнюю нормаль.