Комментарии 52
Там же в комментариях приводят решение этой проблемы: https://habrahabr.ru/post/125356/#comment_4125696
Кстати, оно уже применено автором: "(yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)". Все отрезки считаются открытыми сверху и закрытыми снизу. Поэтому пересечения с концами отрезков отрабатываются правильно — как 0, 1 или 2 пересечения с правильной четностью.
Другими словами что будет, если yp_prev == yp && y == yp?
Если ситуация будет как на картинке (извините за цвета, нарисовал быстро для примера), то ваша функция посчитает, что луч пересекает только зеленые грани, т.е. пересечений четное кол-во?
Нет, не требует. Вы реализовали полностью правильный алгоритм. Грани соседствующие с горизонтальной на луче посчитаются 0, 1 или 2 раза в зависимости от из ориентации. У вас все отрезки закрыты снизу и открыты сверху, обратите внимание на строгие и нестрогие знаки: ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)). Поэтому на картинке сверху будет одно пересечение, а если бы касание горизонтальной грани было сверху — то было бы 2 пересечения.
Сколько пересечений будет, если сложится ситуация как на моей картинке? По-хорошему должно быть 3 пересечения.
Но, судя по тому, что реализация автора проигнорирует горизонтальную грань (результат приведенных вами условий будет false), пересечений будет 2.
Будет 1 пересечение. Горизонтальная грань будет проигнорирована вообще. Верхняя грань зачтется за 1 пересечение по вершине. Нижняя грань (внешняя) не будет учтена за пересечение, потому что она лежит на луче верхней точкой. Условие в алгоритме всегда игнорирует верхнюю точку любого отрезка или горизонтальные отрезки целиком.
Этот метод нормально учитывает и если граница полигона касается горизонтального луча сверху или снизу в вершине или по горизонтальному отрезку. В этом случае будет 0 или 2 пересечения, если касание снизу или сверху соответственно. Что и нужно для корректной четности.
Упустил из виду этот момент, акцентируя внимание на игнорировании горизонтальных линий.
Забавно, что сам автор ввел в дополнительное заблуждение своим ответом.
((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp))
как становится понятно что если один конец грани лежит на луче, а второй выше (визуально, учитывая что точка отсчета координат в левом верхнем углу) — такая грань не будет считаться пересечением.
Это тоже правильный метод. Надо только аккуратно обрабатывать точку на грани или совпадающую с вершиной многоугольника. Его недостаток — скорость. Медленные тригонометрические функции и невозможность сделать целиком в целых числах.
Метод пересечения с лучом можно реализовать без деления вообще в целых числах, если координаты всех вершин целые.
Это начинающие Django + JQuery программисты, интересующиеся векторной графикой в браузере с использованием canvas
Вызывает то чувство, когда вводишь сложный вопрос в Гугл и получаешь 0 результатов.
В статье нет новизны. Обе темы рассматривались неоднократно. Кроме того, опубликованный код — не лучший пример для других. Во-первых, имя view.py намекает, что данный модуль отвечает за представление, а не логику. Во-вторых, алгоритм легко протестировать, но я не вижу тестов. И чтобы их написать, вам придётся разделить логику и код, который принимает запрос и отправляет ответ.
Бывает «even-odd winding rule» и «non-zero winding rule».
В первом случае красная точка считается за пределами полигона (как у автора), во-втором — внутри.
Первый способ определения полигонов является более логичным. Иначе одно и то же множество точек будет описываться бесконечным количеством полигонов.
А почему левая четырехугольная область тут считается внутри многоугольника? Чем она принципиально отличается от правой треугольной, которая помечена как снаружи? По методу луча она тоже будет снаружи.
Насчет отличия таких областей в вики есть удачная метафора:
Если бы P была гвоздём, а C была бы завязанным в кольцо куском нитки, вытягивание какой-то части нитки прочь от гвоздя приведёт либо к вытягиванию всей нитки, либо нитка окажется накрученной несколько раз на гвоздь
Последовательно проверяются все грани полигона на пересечение с лучом, идущим из точки, куда кликнул пользователь. Четное количество пересечений или нет пересечений вовсе — точка за пределами полигона. Количество пересечений нечетное — точка внутри.
Треугольник дает 3 пересечения, прямоугольник — 4. В кого из них точка не входит?
Надо добавить, что луч единственный и направлен влево.
Тем не менее есть контр-пример:
Если считать, как написано в этом комменте, грани полуинтервалами, то левый прямоугольник даст 1 пересечение и точка будет засчитана внутри него. Если же считать грани отрезками, то правый прямоугольник даст 3 пересечения и точка «попадет» в него.
Смотрите код внимательно. Полуинтервалы, открытые сверху. Не с начала или с конца, а сверху всегда. В первом примере с касанием угла левая грань не будет считаться пересечением, потому что касание идет по верхней точке отрезка, которая исключена. Правая грань так же не зачтется, ибо эта точка верхняя и для второй грани. Если бы касание было нижней точки многоугольника то было бы зачтено 2 пересечения. Точно так же и со вторым примером, там еще есть горизонтальная грань, которая игнорируется всегда.
Тестовое задание. Проверка вхождения точки в произвольный полигон