Как проверить что точка внутри многоугольника

По книге Ласло,
«Вычислительная геометрия и компьютерная графика на С++»

Предположим, что нам необходимо определить принадлежность точки а полигону р. Для этого из некоторой удаленной точки проведем прямую линию в точку а. На этом пути может встретиться нуль или несколько пересечений границы полигона: при первом пересечении мы входим внутрь полигона, при втором — выходим из него, при третьем пересечении снова входим внутрь и так до тех пор, пока не достигнем точки а. Таким образом каждое нечетное пересечение означает попадание внутрь полигона р, а каждое четное — выход из него. Если мы попадаем в точку а с нечетным числом пересечений границы полигона, то точка а лежит внутри полигона, а если получается четное число пересечений, то точка находится вне полигона р. Например, на рис. 1 луч r_a пересекает границу только однажды, поскольку единица число нечетное, то точка а находится внутри полигона. Относительно точки b мы прийдем к заключению, что она лежит вне полигона, поскольку луч r_b пересекает границу четное число раз (дважды).

Построение алгоритма на основе этой идеи базируется на двух особенностях. Во-первых, для решения задачи подходит любой луч, начинающийся в анализируемой точке а (рис. 1). Поэтому для прпстоты выберем правый горизонтальный луч r_a, начинающийся в точке а и направленный вправо параллельно положительной полуоси х.

Во-вторых, порядок расположения ребер, пересекаемых лучом r_a безразличен, имеет значение лишь парность (четное или нечетное количество) их общего числа. Следовательно, вместо моделирования движения вдоль луча r_a для алгоритма достаточно определить все пересечения ребер в любом порядке, определяя четность по мере продвижения. Простейшим решением будет обход границы полигона с переключением бита четности при каждом обнаружении ребра, пересекаемого лучом r_a.

Относительно горизонтального луча r_a, направленного вправо, будем различать три типа ребер полигона: касательное ребро, содержащее точку а; пересекающее ребро, не содержащее точку а; безразличное ребро, которое совсем не имеет пересечения с лучом га. Например, на рис. 2 ребро с является пересекающим ребром, ребро d — касательным, а ребро е — безразличным.

Функция pointlnPolygon решает задачу о принадлежности для точки а и полигона р. В процессе работы алгоритма обходится граница полигона и переключается переменная parity для каждого обнаруженного факта пересечения ребра лучом. Возвращается значение INSIDE типа перечисления, если окончательное значение переменной parity равно 1 (означающее нечетное число), или возвращает OUTSIDE, если это конечное значение равно О (означающее четность). Если обнаруживается касательное ребро, то алгоритм немедленно возвращает значение типа перечисления BOUNDARY (граница). Реализация использует классы из раздела ‘Структуры геометрических данных’.

Обращение к функции edgeTypefa, e) классифицирует положение ребра е относительно горизонтального луча r_a, направленного вправо, возвращая значения TOUCHING, CROSSING или INESSENTIAL (касательное, пересекающее или безразличное) типа перечисления. Определение функции edgeType несколько хитроумное, поскольку функция pointInPolygon должна правильно обрабатывать особые ситуации, возникающие при прохождении луча га точно через вершины.

Рассмотрим рис. 3. В случае (а) бит четности должен быть переключен — луч пересекает границу только однажды, хотя при этом на самом деле пересекает два ребра. В случаях (б) и (в) четность не изменяется. Это может быть достигнуто путем некоторого уточнения схемы классификации ребер:

Обращаясь к рис. 3, мы можем видеть, что в случае (а) переменная parity должна переключиться однажды, в случае (б) parity не изменяется, в случае (в) parity переключается дважды и ситуация остается без изменения. Заметим, что горизонтальное ребро, не включающее точку а, считается безразличным и оно игнорируется функцией pointInPolygon. Поэтому случаи (г), (д) и (е) обрабатываются точно так же, как соответствующие случаи (а), (б) и (в).

Итак, функция edgeType классифицирует ребро е как TOUCHING, CROSSING или INESSENTIAL (пересекающее, касательное или безразличное) относительно точки а:

Обратите внимание, как функция edgeType обнаруживает пересекающие ребра. Если точка а лежит слева от ребра е, то ребро является пересекающим, только если вершина начала ребра v(=e.org) лежит ниже луча r_a, а вершина конца w(=e.dest) расположена на луче или лежит выше его. Тогда ребро не может быть горизонтальным и луч га должен пересекать ребро в некоторой точке, отличающейся от его нижнего конца. Если точка а находится справа от ребра е, то роли конечных точек v и w взаимно меняются.

В худшем случае (когда точка а не принадлежит границе полигона) время выполнения программы pointInPolygon пропорционально размеру полигона.

Источник

Реализации алгоритмов/Задача о принадлежности точки многоугольнику

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

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

Алгоритм определяет точки границ многоугольника как точки, ему принадлежащие.

Содержание

Описание [ править ]

Для того чтобы все результаты вычислений в программе могли быть представлены целочисленными переменными (манипулирование данными целого типа повышает быстродействие программы и является естественным для приложений компьютерной графики), вычисления и сравнения площадей треугольников заменяются вычислениями и сравнениями их удвоенных площадей. Тем самым исключается погрешность округления при программной реализации всего алгоритма, в целом.

Аргументами функции, реализующей проверку принадлежности данной точки данному многоугольнику произвольного вида, являются

Функция возвращает 1, если точка принадлежит многоугольнику, иначе — 0.

Функция имеет следующий вид.

Очень быстрый алгоритм [ править ]

В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении горизонтальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику. В данном алгоритме луч направлен влево.

Замечание: Так как умножение быстрее деления, условие можно записать так:

Однако, стоит заметить, что данный алгоритм не эквивалентен предыдущему, поэтому его использование может привести к неправильным результатам.

Perl [ править ]

Delphi (Object Pascal) [ править ]

JavaScript [ править ]

Python 3 [ править ]

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

Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин [ править ]

Функция Cross определяет, пересекает ли луч j-ое ребро многоугольника:

Фрагмент основной программы:

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

Замечание: В данной реализации алгоритма луч направлен вниз.

Источник

Как определить, находится ли 2D-точка внутри многоугольника?

Я пытаюсь создать быстро 2D точка внутри полигонального алгоритма, для использования в хит-тестировании (например, Polygon.contains(p:Point) ). Были бы признательны за предложения относительно эффективных методов.

30 ответов

для графики я бы предпочел не целые числа. Многие системы используют целые числа для рисования пользовательского интерфейса (пиксели все-таки ints), но macOS, например, использует float для всего. macOS знает только точки, и точка может переводиться в один пиксель, но в зависимости от разрешения монитора она может переводиться на что-то другое. На экранах retina половина пункта (0.5/0.5) пиксел. Тем не менее, я никогда не замечал, что macOS UIs значительно медленнее, чем другие UIs. Ведь 3D API (OpenGL или Direct3D) тоже работает с поплавками и современными графическими библиотеками очень часто используют преимущества ускорения GPU.

теперь вы сказали, что скорость ваша главная забота, хорошо, давайте для скорости. Прежде чем запускать какой-либо сложный алгоритм, сначала выполните простой тест. Создайте ось выровнена ограничивающая коробка вокруг полигона. Это очень легко, быстро и уже может обеспечить вам много вычислений. Как это работает? Повторите все точки многоугольника и найдите минимальные / максимальные значения X и Y.

это первый тест для любой точки. Как вы можете видеть, этот тест ультра быстрый, но он также очень грубый. Для обработки точек внутри прямоугольника, нам нужен более сложный алгоритм. Есть несколько способов, как это может быть рассчитанный. Какой метод работает также зависит от того, может ли многоугольник иметь отверстия или всегда будет сплошным. Вот примеры твердых (один выпуклый, один вогнутый):

и вот один с дыркой:

зеленый имеет отверстие в середине!

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

на алгоритм намотки номера было бы альтернативой, это более точно для точек, находящихся очень близко к полигональной линии, но это также намного медленнее. Ray casting может потерпеть неудачу для точек, слишком близких к a сторона полигона из-за ограниченной точности с плавающей запятой и округления, но на самом деле это едва ли проблема, как будто точка лежит так близко к стороне, часто визуально даже невозможно для зрителя распознать, находится ли она уже внутри или все еще снаружи.

теперь, когда у нас есть луч с его начальными и конечными координатами, проблема смещается от»является точкой внутри многоугольника «to»как часто луч пересекает сторону многоугольника«. Поэтому мы не можем просто работать с полигональными точками, как раньше, теперь нам нужны фактические стороны. Сторона всегда определяется двумя точками.

вы нужно проверить Луч со всех сторон. Считайте луч вектором, а каждую сторону вектором. Луч должен попасть в каждую сторону ровно один раз или никогда. Он не может попасть в одну и ту же сторону дважды. Две линии в 2D пространстве всегда пересекаются ровно один раз, если они не параллельны, и в этом случае они никогда не пересекаются. Однако, поскольку векторы имеют ограниченную длину, два вектора могут не быть параллельными и никогда не пересекаться, потому что они слишком короткие, чтобы когда-либо встретиться друг с другом другой.

пока все хорошо, но как вы проверяете, пересекаются ли два вектора? Вот некоторый код C (не протестирован), который должен сделать трюк:

входные значения две конечные точки вектор 1 ( v1x1/v1y1 и v1x2/v1y2 ) и вектор 2 ( v2x1/v2y1 и v2x2/v2y2 ). Итак, у вас есть 2 вектора, 4 точки, 8 координат. YES и NO понятны. YES увеличивает перекрестках, NO ничего не делает.

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

последнее, но не менее важное: если вы можете использовать 3D-оборудование для решения проблемы, есть интересная альтернатива. Просто позвольте GPU сделать всю работу за вас. Создайте поверхность рисования, которая находится вне экрана. Заполните его полностью черным цветом. Теперь позвольте OpenGL или Direct3D нарисовать ваш многоугольник(или даже все ваши многоугольники, если вы просто хотите проверить, находится ли точка внутри любого из них, но вам все равно, какой) и заполнить многоугольник (ы) другим цветом, например белым. Проверить если точка находится внутри многоугольника, получите цвет этой точки с поверхности чертежа. Это просто выборка памяти O(1).

конечно, этот метод можно использовать, только если ваша поверхность рисования не должна быть огромной. Если он не может поместиться в память GPU, этот метод медленнее, чем делать это на CPU. Если он должен быть огромным, и ваш GPU поддерживает современные шейдеры, вы все равно можете использовать GPU, реализуя приведенное выше приведение лучей в качестве шейдера GPU, что абсолютно возможно. Для большего количества полигонов или большого количества точек для тестирования это окупится, рассмотрим, что некоторые графические процессоры смогут тестировать от 64 до 256 точек параллельно. Обратите внимание, однако, что передача данных из CPU в GPU и обратно всегда стоит дорого, поэтому для простого тестирования нескольких точек против пары простых полигонов, где либо точки, либо полигоны являются динамическими и будут часто меняться, подход GPU редко окупается.

Источник

Методы определения принадлежности точки многоугольнику

Недавно на хабре была статья, в которой описывалось как можно определить, где находится точка по отношению к многоугольнику: внутри или снаружи. Подобная проблема встречается в геометрическом моделировании и в компьютерной графике достаточно часто. А так как метод, описанный в статье, был несколько не оптимален, а в комментариях был небольшой хаос, возникла мысль написать эту статью. Итак, какие алгоритмы существуют в современной компьютерной графике, чтобы определить, принадлежит ли заданная точка многоугольнику или нет.

Прежде, чем начать, хочу сразу описать проблему. Хотя сама проблема проста: у нас задан набор точек и задан порядок, в котором эти точки соединяются. И задана точка, которую мы тестируем на принадлежность. Подразумевается, что у нас многоугольник замкнутый, и в общем случае ребра многоугольника не пересекаются друг с другом, то есть он избавлен от самопересечений. Ограничений на количество вершин нет, то есть легко может быть задан многоугольник с миллионом вершин. Мы надеемся, что пользователь не задаст нам непонятно что, но и гарантировать это тоже не можем. И еще один нюанс: так как мы работаем с компьютерной графикой, что означает, что мы используем арифметику с плавающей точкой, которая хотя и позволяет оперировать с числами достаточно точно, все равно не избавлена от ошибок.

Ну вроде определились с проблемой, давайте теперь посмотрим, какие методы решения существуют.

Метод 1. Трассировка лучей

Начну я с того, который считается наиболее популярным в мире графики и игр: трассировка лучей. Вкратце, алгоритм можно описать следующим образом:

Метод простой, но, к сожалению, в общем случае его лучше не применять. Причиной этого является случай, когда мы пересекаем лучом вершину многоугольника или ребро, которое частично совпадает с лучом. Иллюстрирую это на примере.

Допустим, у нас есть многоугольник, и есть точка. В самом начале мы договорились, что направление будет вдоль оси х. Выпускаем из точки луч в положительном направлении оси x и луч благополучно пересек многоугольник в вершине. Тут возникает вопрос, как именно мы проверяем такую ситуацию? Не забываем, что мы работаем с числами с плавающей точкой, и небольшие погрешности возможны. Перейдем в мир аналитической геометрии, чтобы можно было оперировать не просто геометрическими понятиями, а числами.

Посмотрим в другом направлении. Отправили луч в отрицательном направлении. Там тоже не очень хорошо – луч пересекает вершину внутри многоугольника. Тоже может оказаться что угодно. Вместо горизонтального направления взять вертикальное? Никто не гарантирует, что вы опять не пересечете вершину. В конкретно выбранном мной примере наверху точка подобрана таким образом, что пересечение ее с лучом, параллельным оси y и идущий сверху вниз тоже пересекает многоугольник в вершине.

Причем если вы думаете, что пересечение с вершиной – это плохо, смотрите что еще может произойти:

Здесь мы пересекаем луч с отрезком, который с этим лучом совпадает. Как быть в таком случае? А если не совпадает, а почти совпадает? А представьте себе, что в многоугольнике множество почти вырожденных ребер, как с таким пересекать?

Самое печальное во всей этой ситуации то, что нам вот кажется: «мне надо что-то очень простое для моих простых целей, меня такая ситуация не коснется». По закону Мерфи, к сожалению, именно такая ситуация возникает всякий раз когда ее совсем не ждешь. И поэтому я плавно перехожу ко второму методу.

Метод 2. Ближняя точка и ее нормаль

Вообще у этого метода есть страшное название angle weighted pseudo normals и связан он в понятием так называемых полей расстояний со знаком (signed distance fields). Но пугать лишний раз я никого не хочу, так что пусть будет просто ближняя точка и ее нормаль (то есть перпендикулярный вектор).

Алгоритм в данном случае такой:

Рассмотрим пример. Точка A1, ближайшая точка для нее находится на ребре. Если все делаем правильно, нормаль к ребру параллельна вектору от тестируемой точки до ближайшей. В случае точки A1, угол между векторами = 0. Или почти нуль, так как из-за операций с плавающей точкой все возможно. Меньше 90 градусов, тестируемая точка A1 – внутри. Протестируем точку A2. У нее ближайшая точка – вершина, нормаль к которой – усредненная нормаль ребер прилегающих к этой вершине. Считаем скалярное произведение двух векторов, должно быть отрицательным. Мы – снаружи.

Так, вроде бы с сутью метода разобрались. Что там с производительностью и проблемами, связанной с плавающей точкой?

Как и в случае трассировки точек, производительность – O(log n), если использовать деревья для хранения информации о ребрах. С вычислительной точки зрения метод, хотя и имеет подобную сложность, будет несколько помедленнее, чем трассировка. Прежде всего оттого, что расстояние между точкой и ребром чуть более дорогостоящая операция, чем пересечение двух линий. Неприятности, связанные с плавающей точкой, возникают в этом методе, как правило недалеко от ребер многоугольника. Причем чем мы ближе к ребру, тем больше вероятность неправильного определения знака. К счастью, чем мы ближе к ребру, тем меньше расстояние. То есть если мы, например, говорим, что если полученное расстояние меньше заранее заданного минимального (это может быть константа вроде DBL_EPSILON или FLT_EPSILON), то точка принадлежит ребру. А если она принадлежит ребру, то мы уже сами решаем, часть ли многоугольника его ребро или нет (как правило – часть).

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

Но в целом метод неплох, особенно если у нас на входе многоугольник с большим количеством вершин и ребер, а точек на принадлежность надо протестировать много. Если же точек мало, трассировка лучей нестабильна, а хочется чего-то более-менее надежного, то есть и третий способ.

Метод 3. Индекс точки относительно многоугольника

Этот метод известен довольно давно, но в основном остается теоретическим, по большей части потому, что он не так эффективен, как предыдущие два. Вот его суть «на пальцах». Возьмем единичную окружность с центром в тестируемой точке. Потом каждую вершину многоугольника спроецируем на эту окружность лучами, которые проходят через вершину и тестируемую точку. Как-то примерно так:

На рисунке точки P1, P2 и так далее – вершины многоугольника, а точки P1’, P2’ и так далее – их проекции на окружность. Теперь когда мы рассматриваем ребро многоугольника, по проекциям можно определить, происходит ли вращение против часовой стрелки или по часовой стрелке при переходе от одной вершины к другой. Вращение против часовой стрелки будем считать положительным поворотом, а вращение по часовой стрелке – отрицательным. Угол, который соответствует каждому ребру – это угол между сегментами окружности через проекции вершин этого ребра. Так как поворот у нас может быть положительный или отрицательный, то и угол может быть положительный или отрицательный.

Алгоритм в этом случае следующий:

Рассмотрим пример. Есть многоугольник, порядок которого установлен против часовой стрелки. Есть точка А, которую мы тестируем. Для тестирования сначала вычисляем угол между векторами AP1 и AP2. Векторное произведение этих же векторов смотрит на нас, значит прибавляем к сумме. Переходим дальше и считаем угол между AP2 и AP3. Векторное произведение смотрит на нас, полученный угол вычитаем. И так далее.

Для конкретно этого рисунка я все посчитал и вот что получилось:

(AP1, AP2)=74.13, (AP2, AP3)=51.58, (AP3, AP4)=89.99, (AP4, AP5)=126.47, (AP5, AP1)=120.99.
sum=74.13-51.58+89.99+126.47+120.99=360. 360/360=1 Точка – внутри.

(BP1, BP2)=44.78, (BP2, BP3)=89.11, (BP3, BP4)=130.93, (BP4, BP5)=52.97, (BP5, BP1)=33.63.
sum=-44.78+89.11-130.93+52.97+33.63=0. Точка – снаружи.

И традиционно опишем плюсы и минусы данного подхода. Начнем с минусов. Метод прост математически, но не так-то эффективен с точки зрения производительности. Во-первых, его алгоритмическая сложность O(n) и, как ни крути, а все ребра многоугольника придется перебрать. Во-вторых, для вычисления угла придётся воспользоваться операцией арккосинуса и двумя операциями взятия корня (формула скалярного произведения и связь его с углом тем в помощь, кто не понимает, почему). Эти операции очень недешевы с точки зрения скорости, и, к тому же, погрешности связанные с ними могут быть существенны. И в третьих, алгоритм напрямую не определяет точку, лежащую на ребре. Либо – снаружи, либо – внутри. Третьего не дано. Впрочем, последний недостаток легко определяется: если хотя бы один из углов равен (или почти равен) 180 градусам, это автоматически означает ребро.

Недостатки метода в чем-то компенсируются его достоинствами. Во-первых, это самый стабильный метод. Если многоугольник на вход подан корректный, то результат получается корректный для всех точек, за исключением разве что точек на ребрах, но о них смотри выше. Более того, метод позволяет частично бороться с некорректными входными данными. Многоугольник самопересекается? Не беда, метод скорее всего определит большинство точек правильно. Многоугольник не замкнут или вообще не многоугольник а малоосмысленный набор сегментов? Метод определит точки верно в большом количестве случаев. В общем, всем метод хорош, но медленный и требует вычислений арккосинусов.

Чем бы хотелось закончить этот обзор? А тем, что методов для решения проблемы определения принадлежности точки многоугольнику существует не один и даже не два. Они служат для разных целей и некоторые более подходят в случаях, когда важна скорость, другие – когда важно качество. Ну и не забываем о том, что у нас непредсказуемые входные данные и мы работаем с компьютером, у которого арифметика с плавающей точкой подвержена погрешностям. Если нужна скорость и качество совершенно неважно – трассировка лучей в помощь. В большинстве реальных приложений скорее всего поможет метод ближней точки и нормали. Если же на первом месте – точность определения при непонятных входных данных, метод индекса точки должен помочь.

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

Источник