Элегантный тест «Слева от» для полилинии

Дано:

• (X,Y) координата, которая является положением транспортного средства.
• Массив (X,Y), являющихся вершинами полилинии. Обратите внимание, что полилиния состоит только из прямых сегментов, без дуг.

Что я хочу:

• Рассчитать, находится ли транспортное средство слева или справа от полилинии (или, конечно, сверху).

Мой подход:

• Перебрать все сегменты линии и вычислить расстояние до каждого сегмента. Затем для ближайшего сегмента вы выполняете простой тест слева (например, как описано здесь ).

Возможные проблемы:

• Когда угол между тремя точками меньше 90 градусов (как показано на рисунке), возникает более сложный сценарий. Когда автомобиль находится в красном сегменте, как показано ниже, ближайший сегмент может быть одним из двух. Однако проверка слева отдаст право, если первый сегмент выбран в качестве ближайшего сегмента, и левов противном случае. Мы можем легко увидеть (по крайней мере, я надеюсь), что правильным результатом должно быть то, что транспортное средство находится слеваломаной.

Мой вопрос:

• Как я могу элегантно, но в основном эффективнопозаботиться об этой конкретной ситуации?

Мое исправление на данный момент:

• Вычислить для обоих сегментов точку на этом сегменте, начиная с точки вершины.
• Вычислите расстояние от автомобиля до обеих точек, используя евклидово расстояние.
• Оставьте отрезок, для которого вычисленная точка является ближайшей.

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

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

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