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

Question

Мне интересно, как работает четно-нечетный алгоритм для идентификации точки в сложном многоугольнике.

Что я знаю сейчас, так это то, что он будет выполнять горизонтальный поиск от наиболее левой точки к точке и подсчитывать количество затронутых ребер.

Однако, что произойдет, если коснувшиеся ребра находятся впересечение 2 ребер?как это считается?

Пример полигонов:

Answer 1

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

Слегка изменить направление луча

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

Вам необходимо убедиться, что вы не формируете замкнутые петли, например, по зигзагообразной схеме (чтобы вы чередовали поворот CW и CCW в некотором конусе от первоначального направления).

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

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

btw.Этот алгоритм внутреннего полигона, который вы используете, хорошо известен под именем Тест на попадание

Answer 2

Мне нравится делать то, что работает как для целочисленных, так и для координат с плавающей точкой:

• для негоризонтальных сегментов, каждый сегмент включает самый нижнийточка, но не ее самая верхняя точка.

• не включают горизонтальные сегменты вообще в четно-нечетное число.

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