Как-то появилась потребность определять принадлежность точки много угольнику. Естественно, прежде чем браться за разработку своего алгоритма было бы неплохо познакомиться с наработками в решении этой задачи. Что и сделал. полез в интернет. Одно из решений подобной задачи — метод трассировки луча. Купился я на посулы … Потратил рабочий день на него, прежде, чем понял насколько он глючный.
Сначала попробовал вариант под названием «очень быстрый алгоритм». По глупости сразу вставил в рабочий код. Программа глючила. Стал тестировать алгоритм. Простейшая тестовая утилитка показала, что что-то не так:
Утилита отмечает координаты мыши красным если false = точка вне многоугольника и зелёным (true), если «очень быстрый алгоритм» решает, что точка внутри многоугольника. Как видно из скриншота, в некоторых областях алгоритм врёт.
Пробуем проработать каждую точку вокруг многоугольника:
Пробуем простой (не быстрый) алгоритм трассировки луча:
Вроде бы всё прекрасно, но:
опять же часть точек внутри и снаружи многоугольника обрабатывает неверно.
Другая фигура:
Слева вверху область обработана неверно.
Для большинства случаев сойдёт, но мне надо 100% уверенность, в принадлежности точки многоугольнику или не принадлежности. Поэтому делаем лёгкий «плевок» в сторону авторов подобного алгоритма с такими ошибками и быстренько пишем свой алгоритм со 100%-й точностью.
Успехов!
P.S.: Не всё что в сети — золото.
