В одном из прошлых материалов я рассказывал Вам о шуточной теореме о большой точке (ссылка на неё будет в конце материала, т.к. Дзен блокирует статьи, в которых в описание попадает ссылка).
Точка и сегодня будет героем нашей повести, но говорить будем о такой науке как вычислительная геометрия - отрасли знаний, в которой рассматриваются алгоритмы решения геометрических задач. В университетском курсе начинается предмет с классической задачи:
Дана точка и многоугольник, лежащие в одной плоскости. Определить, где находится точка: внутри или вне многоугольника ?
В задачах могут рассматриваться как простые (без самопересечений) так и сложные многоугольники, причем неважно выпуклые или нет.
Самым простым способом решения задачи является способ трассировки лучом. Для этого в заранее произвольно заданном направлении (например, по оси Y) из каждой точки "запускается луч":
Теперь остается посчитать количество пересечений лучей с ребрами многоугольника. Если их четное количество (или 0) - точка лежит снаружи, в обратном случае - внутри.
На бумаге всё выглядит гладко, но если оперировать абстрактными данными в языках программирования, придется проверять пересечение лучей с каждым ребром. Кроме того, существуют вырожденные ситуации, когда практическое применение алгоритма трассировки лучом ограничено или требует "костылей":
В этом случае число пересечений четное, но точка лежит внутри многоугольника. Конечно, можно считать пересечение вершин за два, но и тут могут возникать сложности, связанные с тем, что в реальности оперируют не идеальными геометрическими объектами, а числами с плавающими точками, где всегда есть хоть минимальные, но погрешности.
Другой подход к решению задачи - "метод ближней точки и нормали" - лишен недостатков первого, но требует некой предварительной подготовки.
Алгоритм следующий:
1. Для всех ребер многоугольника вычисляется вектор нормали, направленный наружу. Если ближняя точка – одна из вершин, то нормалью является усредненный вектор ребер, прилежащих к вершине.
2. Вычисляется вектор от точки, местоположение которой необходимо определить, до ближайшей точки ребра.
3. Определяется угол между ними. Если угол меньше 90 градусов - точка внутри, иначе - снаружи.
Принцип действия достаточно наглядно был показан на рисунке выше. Вроде бы всё хорошо, но напомню, что мы рассмотрели только простые многоугольники. По вполне понятным причинам последний метод очень не любит многоугольники с самопересечениями, ведь неясно, где у него "внутри", а где "снаружи".
В таких ситуациях помогает вычисление т.н. индекса точки относительно многоугольника. Впрочем, это уже совсем другая история, о которой я скоро расскажу. Спасибо за внимание!