Элегантный тест "Левый" для полилинии

Дано:

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

Что я хочу:

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

Мой подход:

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

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

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

Мой вопрос:

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

Мое исправление:

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

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

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

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

Ответ 1

Эта тема так долго неактивна, что я считаю ее мертвой. У меня есть решение.

Однако левый тест даст право, если первый сегмент выбранный как ближайший сегмент и оставленный в противном случае.

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

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

Квадрант находится на ПРАВО первого сегмента
Квадрант находится на LEFT второго сегмента

Оба сегмента не согласны с тем, где находится квадрант, поэтому вы делаете еще два теста на двузначность:

Второй сегмент находится в правой части первого сегмента
Первый сегмент находится на ПРАВО второго сегмента

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

(Я почти уверен, что вы можете сделать только один из двух тестов на двузначность, я поставил оба для ясности)

Для полноты: я считаю, что это решение также учитывает ваши требования эффективности и элегантности, поскольку он использует тот же метод, который вы использовали с самого начала (слева), так что он отвечает всем требованиям заданные условия: он элегантен, эффективен и заботится о проблеме.

Ответ 2

Пусть бесконечность = M, где M достаточно велико. Вы можете считать, что все находится в квадрате [-M, M] x [-M, M], разбивает квадрат на вашу полилинию, и теперь у вас есть два полигона. Тогда проверка того, находится ли автомобиль в заданном полигоне, может быть выполнена очень просто с углами.

Я считаю, что ваша первая точка и ваша последняя точка имеют M в координатах. Возможно, вам нужно добавить некоторые из этих точек, чтобы иметь многоугольник: (-M, -M), (M, -M), (M, M) и (-M, M).

Когда у вас есть полигон слева от полилинии, суммируйте углы OĈP, где O - неподвижная точка, C - автомобиль, а P - точка многоугольника. Если сумма равна 0, то автомобиль находится вне полигона, иначе он внутри.

Ответ 3

Просто быстрая идея: можно ли подключить последнюю и первую вершину вашей полилинии, чтобы она стала полигоном? Затем вы можете выполнить простую проверку внутри/снаружи, чтобы определить, находится ли транспортное средство слева/справа от линии (это зависит от направления многоугольника).

Однако этот метод предполагает, что многоугольник все еще не самопересекается после соединения последней и первой вершин.

Ответ 4

Это стандартная задача из вычислительной геометрии. Поскольку вы хотите проверить, оставлена ли точка (x0, y0) - заданной поверхности (ваша полилиния), вам нужно определить, какой сегмент испытывать по высоте. Один простой способ сделать это - построить дерево нижней точки каждого сегмента и выполнить поиск в нем для предшественника контрольной точки. После того, как у вас есть этот сегмент, вы можете выполнить свой левый тест напрямую: если он оставлен как с конечными точками, так и между ними на соответствующей стороне, вы вернетесь к истине.

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

Расширение в ответ на комментарий OP:

Обратите внимание, что пример угла в вопросе противоречит первому предположению - полилиния не достигает высоты точки поиска.

Одним из способов концептуализации моего метода является сортировка ваших сегментов по вертикали, а затем их повторение путем сравнения вашей координаты точки y с сегментами, пока ваша точка не окажется выше нижней конечной точки и ниже верхней конечной точки. Затем используйте конечные точки сегмента для определения x-перехвата в заданном y. Если точка имеет более низкое x-cooordinate, то она слева, и если она имеет большую координату x, то она вправо.

Есть два способа улучшить это объяснение в реальной реализации, о которой я упомянул:

Используйте сбалансированное дерево поиска, чтобы найти правильный сегмент, а не итерировать через отсортированный список, чтобы довести время от O(n) до O(log n)
Восстановить поиск как найти пересечение полилинии и горизонтальной линии y = y0 через точку поиска. Затем просто сравните значение x пересечения с точкой поиска.