Принадлежит ли точка ромбу 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);
• определить принадлежности точки полигону;

Источник

Как определить, принадлежит ли точка ромбу?

Нашел: math.stackexchange.com/a/312733, но не совсем уверен, так ли на самом деле, нужны ли вектора?

Собственно, если у вас дагонали dx, dy, и они параллельны осям, а центр — rx, ry, точка — x, y, то проверка сводится к следующей:
|(x — rx) / dx| + |(y — ry) / dy| Всё.

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

Знак Q определяет, с какой стороны от прямой AB лежит точка T.

Остается проверить это для всех сторон ромба AB, BC, CD, DA, если знак везде одинаков — точка в ромбе.

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

Для того, чтобы это получилось, нужно чтобы ромб был идеально расположен — чтобы его диагонали лежали на осях координат. У вас такой случай?

Диагонали параллельны осям, этого вроде бы, должно быть достаточно.
Кстати, у меня вроде получилось реализовать тем способом, что на math.stackexchange.com

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

Это универсальный способ для любого выпуклого многоугольника, но для ромба можно сделать проверку на порядок быстрее.

Источник

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

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

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

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

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

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

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

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

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

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

Источник

Как определить, принадлежит ли точка ромбу?

Нашел: math.stackexchange.com/a/312733, но не совсем уверен, так ли на самом деле, нужны ли вектора?

Собственно, если у вас дагонали dx, dy, и они параллельны осям, а центр — rx, ry, точка — x, y, то проверка сводится к следующей:
|(x — rx) / dx| + |(y — ry) / dy| Всё.

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

Знак Q определяет, с какой стороны от прямой AB лежит точка T.

Остается проверить это для всех сторон ромба AB, BC, CD, DA, если знак везде одинаков — точка в ромбе.

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

Для того, чтобы это получилось, нужно чтобы ромб был идеально расположен — чтобы его диагонали лежали на осях координат. У вас такой случай?

Диагонали параллельны осям, этого вроде бы, должно быть достаточно.
Кстати, у меня вроде получилось реализовать тем способом, что на math.stackexchange.com

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

Это универсальный способ для любого выпуклого многоугольника, но для ромба можно сделать проверку на порядок быстрее.

Источник