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

Взаимное расположение точки и многоугольника

В вычислительной геометрии широко известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник с \(N\) вершинами без самопересечений и произвольная точка \(P\), и требуется определить, лежит ли точка внутри многоугольника, причем многоугольник может быть как выпуклым, так и невыпуклым. На рисунке 1 мы можем видеть 3 варианта расположения точки относительно многоугольника: снаружи (точка \(P_\)), внутри (точка \(P_\)) и на границе (точка \(P_\)). Две последние точки ему принадлежат, первая – нет.

Общий случай. Метод трассировки луча.

Идея решения задачи в случае произвольного многоугольника заключается в использовании так называемого «метода трассировки луча». Будем считать количество пересечений со сторонами многоугольника луча, который имеет начало в точке P и параллелен одной из осей координат (для удобства определим, что луч параллелен оси O₁.
Заметим, что если количество пересечений четное, то точка лежит вне многоугольника, если же нечетное – внутри (см. рис. 2). Это основано на достаточно очевидном факте: при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи заданного многоугольника.

Однако, у такого способа есть недостаток: случаи при пересечении луча с вершиной многоугольника или совпадением с его стороной нами не учитываются, а значит их придется разбирать отдельно. Всего может возникнуть 6 разных проблемных ситуаций, представленных на рисунке 3. В случае а) мы должны засчитать пересечение границы лишь раз, в случаях б) и в) количество пересечений не изменяется. В ситуациях же г), д) и е) ребро, которое лежит на луче, можно считать безразличным, то есть его пересечение мы не засчитываем. Поэтому случаи г), д) и е) обрабатываются нами так же, как а), б) и в) соответственно. Таким образом, кроме проверки на пересечение с каждой из сторон многоугольника, нам нужно проверить для каждой вершины и стороны принадлежность к заданному лучу и, если принадлежность выполняется, по одну ли сторону от луча лежат соседние элементу стороны многоугольника.
Приведенный метод позволяет решить задачу за \(O(n)\), где \(n\) – количество углов многоугольника.

Случай выпуклого многоугольника. Бинарный поиск по углу.

Решение данной задачи становится быстрее, если нам изначально дано, что многоугольник выпуклый. Сразу отсортируем вершины в порядке обхода против часовой стрелки, если изначально они были заданы в другой последовательности.
Обозначим за \(C\) точку многоугольника с наименьшей координатой по оси \(O_\) (если таких несколько, то из них берем самую нижнюю, то есть с наименьшей координатой по оси \(O_\)) и заметим, что все остальные точки многоугольника лежат относительно нее в правой полуплоскости. Затем проведем лучи из \(C\) через все оставшиеся вершины многоугольника и воспользуемся бинарным поиском для нахождения сектора, в котором лежит точка \(P\).

Для тех, кто не знает, как строить бинарный поиск в данном случае, поясню. Изначально мы пронумеруем вершины многоугольника от \(0\) до \(N — 1\), начиная в точке \(C\). Далее введем переменные \(L\) и \(R\), которые будут отвечать за верхнюю и нижнюю границы нашего сектора соответственно. То есть изначально \(L = 1\), а \(R = N — 1\) (см. на рисунок 4). Теперь постоянно будем брать между вершинами, номера которых задаются \(L\) и \(R\), среднюю (обозначим ее \(S\), \(S = \)) и смотреть, какому из двух углов – \(\angle\) или \(\angle\) – принадлежит точка \(P\). Если она принадлежит углу \(\angle\), то нижнюю границу мы можем сдвинуть выше в точку \(S\), то есть теперь \(R = S\), иначе же мы сдвигаем верхнюю границу, то есть теперь \(L = S\). Будем сдвигать границы таким образом до тех пор, пока \(L\) и \(R\) не станут соседними, то есть пока их разность не станет равна 1, тем самым мы найдем сектор, которому принадлежит нужная нам точка \(P\) (на рисунке 4 получившиеся \(L\) и \(R\) обозначены как \(L_\) и \(R_\) соответственно).
Теперь, когда мы знаем сектор, в котором лежит точка \(P\), мы можем с легкостью определить, принадлежит ли точка многоугольнику. Для этого мы проверяем, пересекаются ли \(\overrightarrow\) и сторона \(LR\). Если нет, то точка \(P\) лежит внутри многоугольника, если да – то снаружи.
Благодаря использованию бинарного поиска по углу, данный алгоритм работает быстрее, чем тот, что был приведен для общего случая, а именно, за \(O(\log n)\), однако он не подходит для невыпуклых многоугольников.

Расстояние от точки до многоугольника.

После того, как мы узнали, принадлежит ли точка многоугольнику, мы можем без труда определить расстояние до него от нее: если точка лежит принадлежит многоугольнику, то оно будет равняться 0, если же нет, то его значение будет равно наименьшему из расстояний от данной точки до каждой из сторон многоугольника. Например, на рисунке 5 отмечены наименьшие расстояния от точки \(P\) до сторон многоугольника. Наименьшим из них является перпендикуляр к стороне \(AB\), значит, именно его длина является расстоянием от точки \(P\) до данного многоугольника.

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

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

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

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

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

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

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

• указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида

struct Point < int x; int y; >;

• число вершин многоугольника;
• целочисленное значение координаты X заданной точки;
• целочисленное значение координаты Y заданной точки.

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

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

int IsPointInsidePolygon (Point *p, int Number, int x, int y) < int i1, i2, n, N, S, S1, S2, S3, flag; N = Number; for (n=0; n= N) i2 = 0; if (i2 == (n < N-1 ? n + 1 : 0)) break; S = abs (p[i1].x * (p[i2].y - p[n ].y) + p[i2].x * (p[n ].y - p[i1].y) + p[n].x * (p[i1].y - p[i2].y)); S1 = abs (p[i1].x * (p[i2].y - y) + p[i2].x * (y - p[i1].y) + x * (p[i1].y - p[i2].y)); S2 = abs (p[n ].x * (p[i2].y - y) + p[i2].x * (y - p[n ].y) + x * (p[n ].y - p[i2].y)); S3 = abs (p[i1].x * (p[n ].y - y) + p[n ].x * (y - p[i1].y) + x * (p[i1].y - p[n ].y)); if (S == S1 + S2 + S3) < flag = 1; break; >i1 = i1 + 1; if (i1 >= N) i1 = 0; break; > if (flag == 0) break; > return flag; >

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

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

bool pnpoly(int npol, float * xp, float * yp, float x, float y) < bool c = false; for (int i = 0, j = npol - 1; i < npol; j = i++) < if ((((yp[i] ((xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])))) c = !c; > return c; >

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

int pnpoly(int npol, float * xp, float * yp, float x, float y) < int c = 0; for (int i = 0, j = npol - 1; i < npol; j = i++) < if (( (yp[i] < yp[j]) && (yp[i] (xp[j] - xp[i]) * (y - yp[i])) ) || ( (yp[i] > yp[j]) && (yp[j] return c; >

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

Perl [ править ]

my $x = -40; my $y = -60; # Проверяемая точка my @xp = (-73,-33,7,-33); # Массив X-координат полигона my @yp = (-85,-126,-85,-45); # Массив Y-координат полигона &InPoly(\@xp,\@yp,$x,$y); sub InPoly() < my($xp, $yp, $x, $y) = @_; my $npol = @; my $j = $npol - 1; my $c = 0; for(my $i = 0; $i < $npol;$i++) < if ((((@[$i]<=$y) && ($y<@[$j])) || ((@[$j]<=$y) && ($y<@[$i]))) && ($x > (@[$j] - @[$i]) * ($y - @[$i]) / (@[$j] - @[$i]) + @[$i])) < $c = !$c >$j = $i; > return $c; >

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

type tPolygon = array of tPoint; //tPoint - это запись, с двумя полями, x и y . function IsMouseInPoly(x,y: integer; myP: tPolygon): boolean; //x и y - это координаты мыши var //myP - массив с вершинами полигона i,j,npol: integer; inPoly: boolean; begin npol:=length(myP)-1; j:=npol; inPoly:=false; for i:=0 to npol do begin if ((((myP[i].y<=y) and (y(myP[j].x-myP[i].x)*(y-myP[i].y) / (myP[j].y-myP[i].y)+myP[i].x)) then inPoly:=not inPoly; j:=i; end; result:=inPoly; end;

JavaScript [ править ]

var x = -40; var y = -60; var xp = new Array(-73,-33,7,-33); // Массив X-координат полигона var yp = new Array(-85,-126,-85,-45); // Массив Y-координат полигона function inPoly(x,y) < var npol = xp.length; var j = npol - 1; var c = 0; for (var i = 0; i < npol;i++)< if ((((yp[i]<=y) && (y(xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) < c = !c >j = i; > return c; > inPoly(x,y);

Python 3 [ править ]

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

def inPolygon(x, y, xp, yp): c=0 for i in range(len(xp)): if (((yp[i] (xp[i-1] - xp[i]) * (y - yp[i]) / (yp[i-1] - yp[i]) + xp[i])): c = 1 - c return c print( inPolygon(100, 0, (-100, 100, 100, -100), (100, 100, -100, -100)))

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

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

bool Cross(int j) < int first = j; int second = j == n - 1 ? 0 : j + 1; double y = (xh - points[first].x) * (points[second].y - points[first].y) / (points[second].x - points[first].x) + points[first].y; double minimal = min(points[first].x, points[second].x); double maximal = max(points[first].x, points[second].x); return (points[first].x != points[second].x) && (yh >= y) && (xh > minimal) && (xh

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

. int count = 0; for (int i = 0; i < n; i++) < count += Cross(i); >.

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

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

Проверка принадлежности точки выпуклому многоугольнику на Java

Задача: Определить, принадлежит ли точка выпуклому многоугольнику.
Алгоритм: Выберем произвольную точку ( кликом мышки ).
Используя векторное произведение, проверим по очереди в порядке обхода сторон по часовой стрелке, лежит ли точка слева от очередного вектора — стороны многоугольника
( откладываем вектора: от i-й вершины к i-1-й вершине, и от i-й вершины к выбранной точке).
Если векторное произведение неотрицательно, значит точка лежит слева от стороны многоугольника, либо на стороне. Если это выполняется для каждой из сторон, то точка лежит внутри многоугольника.

Код программы:

package sample; import com.sun.xml.internal.bind.v2.schemagen.xmlschema.Annotation; import javafx.geometry.Point2D; import javafx.scene.canvas.GraphicsContext; public class Check { private int n = 6; //количество вершин многоугольника private Point2D Poly[] = new Point2D[] { new Point2D(200, 170), new Point2D(320, 120), new Point2D(440, 170), new Point2D(440, 250), new Point2D(320, 300), new Point2D(200, 250), }; //возвращает true, если точка лежит слева от прямой private boolean vector_mult (Point2D A, Point2D B, double click_X, double click_Y) { if(((B.getX()-A.getX())*(click_Y - A.getY()) - (B.getY()-A.getY())*(click_X - A.getX())) >= 0) return true; else return false; } public void DrPoly (GraphicsContext g_c) { //отрисовка многоугольника for(int i = 0; i  n-1; i++) { g_c.strokeLine(Poly[i].getX(), Poly[i].getY(), Poly[i+1].getX(), Poly[i+1].getY()); } g_c.strokeLine(Poly[n-1].getX(), Poly[n-1].getY(), Poly[0].getX(), Poly[0].getY()); } public boolean check_attachment (double click_X, double click_Y) { //возвращает true, если точка лежит слева от каждой прямой for(int i = 0; i  n-1; i++) { if(!vector_mult(Poly[i], Poly[i+1], click_X, click_Y)) return false; } if (vector_mult(Poly[n-1], Poly[0], click_X, click_Y)) return true; else return false; } }

Прикрепленный файл	Размер
leonidchenko_pointchecker.zip	19.33 кб

Войдите или зарегистрируйтесь, чтобы комментировать

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

Разбор добавил Иван Смирнов

Есть несколько алгоритмов проверки принадлежности точки произвольному многоугольнику. Один из самых простых, на мой взгляд, заключается в следующем.
Найдем сумму ориентированных углов, под которыми из данной точки видны все отрезки, соединяющие две последовательные точки данного многоугольника. Если она будет равна нулю (с точностью до eps), то точка находится строго снаружи. В противном случае точка лежит либо внутри, либо на границе многоугольника.
Как это считать? Здесь нам понадобится одна элементарная операция — нахождение угла между векторами. Пусть у нас есть точка O и две вершины A_i и A_i+1. Угол, под которым из O виден отрезок (A_i, A_i+1), равен углу между векторами (A_i — O) и (A_i+1 — O). Угол между векторами x и y можно посчитать функцией atan2([x, y], (x, y)), где [x, y] и (x, y) — соответственно векторное (косое) и скалярное произведения векторов.
Почему это работает? Вот интуитивное объяснение алгоритма. Пусть мы находимся в данной точке и хотим последовательно осмотреть весь многоугольник, вернувшись в начальную вершину. Если мы находимся снаружи, то, как бы не поворачивали взгляд, в конце он все равно вернется строго в исходное положение, не сделав лишних поворотов на 360 градусов, то есть суммарный угол поворота будет равен нулю. Если же мы находимся строго внутри, то для того, чтобы вернуться в исходную вершину, нам придется сделать полный оборот вокруг своей оси. В случае, когда мы находимся на границе, тоже должен произойти полный поворот вокруг своей оси, однако из-за способа вычисления значения угла в компьютере на практике получается промежуточное значение.

Входные данные

В первой строке вводятся три целых числа – N (3 ≤ N ≤ 100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные

Выведите одну строку: “ YES ”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “ NO ” в противном случае.