Принадлежность точки полигону python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

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

b0006/Point-in-polygon

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Принадлежность произвольной точки полигону

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

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

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

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

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

Затем находится площадь самого полигона. Найденные площади сравниваются — если сумма трёх площадей равна площади всего полигона, то значит точка принадлежит полигону.

• ввод координат точки в виде кортежей вида (x, y);
• определить принадлежности точки полигону;

Источник

Point in Polygon in Python

About the algorithm and language used in this code snippet:

Point in Polygon Algorithm

The Point in Polygon (PIP) problem is the problem of determining whether a point is any arbitrary polygon. This might sound trivial for a simple polygon like a square or a triangle, but gets more complex with more complex polygons like the one in the example below. In this post, the even-odd algorithm, also called crossing number algorithm or Jordan’s algorithm (since it can be proven using the Jordan curve theorem), will be introduced.

Description of the Algorithm

The basic principle behind the Even-odd aka. Jordan aka. Cross Number Algorithm is to count the number of times a line from the point in question (in any, arbitrary direction) crosses any edge of the polygon. This line will always be outside of the polygon at it’s “end” in infinity, so if it is inside the polygon at the start (the point in question), it will have to leave the polygon at some point, crossing some edge. It can re-enter the polygon (see the example below), but it always has to leave again, making the total number of crossings uneven if the point is in the polygon. The opposite is also true; if the number of crossings is even, the point is always outside of the polygon. This is the above mentioned Jordan’s curve theorem.

The algorithm checks every edge of the polygon in a loop to determine if the line from the point to infinity crosses it. In the example below, this line is drawn from the point to infinity to the right, but it can be any direction.

1. For each edge in the polygon:
2. If the edge crosses the imaginary line from the point to infinity, increase a counter.
3. At then end, if the counter is uneven, return true. Else, return false.

A simple boolean variable that is inverted every time a crossing is found is also possible.

Example of the Algorithm

Consider the following polygon with 8 edges and two points for which we want to determine whether they are in the polygon:

The steps the algorithm performs on this polygon to determine whether the first (green) point is in the polygon are, starting from the first edge:

1. Green Point crosses edge 8
2. Green Point does not cross edge 1
3. Green Point crosses edge 2
4. Green Point does not cross edge 3
5. Green Point crosses edge 4
6. Green Point crosses edge 5
7. Green Point does not cross edge 6
8. Green Point does not cross edge 7
9. Total number of crossings: 4
10. Even number of edge crossings, therefore the point is not in the polygon

The steps the algorithm performs on this polygon to determine whether the second (red) point is in the polygon are, starting from the first edge:

1. Red Point does not cross edge 8
2. Red Point does not cross edge 1
3. Red Point does not cross edge 2
4. Red Point does not cross edge 3
5. Red Point does not cross edge 4
6. Red Point crosses edge 5
7. Red Point does not cross edge 6
8. Red Point does not cross edge 7
9. Total number of crossings: 1
10. Uneven number of edge crossings, therefore the point is in the polygon

Runtime Complexity of the Algorithm

The runtime complexity of the Jordan Algorithm aka. Crossing Number Algorithm aka. Even-Odd Algorithm to solve the point-in-polygon problem for a single point is linear with respect to the number of edges. This is evident by looking at the code, which contains a single loop over the edges, with no recursion or further function calls or loops.

Formally the runtime is O(|V|), |V|:=number of edges in the polygon.

Space Complexity of the Algorithm

The space complexity is also linear w.r.t. the number of edges, since only fixed-size variables need to be stored in addition to the polygon. Additionally, the algorithm can be implemented on-line, meaning there is no need to look at past edges during the loop, so they can be evicted from memory (or comparable performance improvement measures).

Источник

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

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

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

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

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

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

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

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

• число вершин многоугольника;
• целочисленное значение координаты 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 примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.

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

Источник