Простой тест точки-полигона с постоянным поведением для ребер

Question

При поиске тестов точка-полигон я нашел описанный Дином Пови здесь . Мне нравится этот подход, поскольку его легко понять (raycast вдоль оси x), но я столкнулся с небольшим несоответствием с этим методом. При написании модульных тестов для моей реализации я заметил, что при выборе квадрата в качестве «Тест-многоугольника» точки на левом и нижнем краях квадрата распознаются как часть многоугольника, а точки на правой и верхней стороне многоугольника. распознаются как вне многоугольника. Вот небольшой рисунок, показывающий, что я имею в виду (+ не распознаются как внутри, удвоенные линии и х):

+--------+
‖        |
‖        |
x========+

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

Answer 1

Чтобы проверить, лежит ли точка P на ребре QR, рассмотрим преобразование, которое отображает Q в начало координат и R в точку (0, 1).

Используя комплексные числа, запишите это преобразование как Z = (z - Q) / (R - Q) и преобразуйте P с помощью (P - Q) / (R - Q). Это число должно быть чисто вещественным, а его действительная часть должна быть в [0, 1].

Вы можете использовать этот тест для обнаружения точек на контуре. Также возможно допустить допуск, позволяя мнимой части быть небольшим числом. В этом случае целесообразно нормализовать знаменатель R - Q, чтобы мнимая часть стала евклидовым расстоянием до отрезка.