[Из песочницы] Задача об определении принадлежности точки многоугольнику
Здравствуйте, уважаемые хабравчане!В процессе разработки приложения под Android, которое предполагает взаимодействие пользователя с графическими примитивами (точками, линиями, эллипсами, прямоугольниками и т.д.), возникла довольно неприятная ситуация: пользователь может задать произвольный многоугольник и сделать его неактивным, однако чтобы в будущем была возможность активировать данный многоугольник и продолжить с ним работь (например, переместить в другое место или добавить/удалить вершины) необходимо для неактивного объекта определить, коснулся ли пользователь данного объекта, т.е. потребовалось решить вопрос о принадлежности точки многоугольнику.
Данная задача широко известна в вычислительной геометрии, однако в русскоязычной литературе практически не описана. Чтобы исправить данное недоразумение предлагаю вашему вниманию результаты моего исследования данной темы.
Читать дальше →
