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

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

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

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

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

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

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

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

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

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

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

Источник

Определить, принадлежит ли точка M(X,Y) внутренней области треугольника с вершинами A(0,0), B(a,0) и C(0,b)

как написать на языке Python
Определить, принадлежит ли точка M(X,Y) внутренней области треугольника с вершинами A(0,0), B(a,0) и C(0,b), где a и b – положительные числа.

Если точка М (х, у) принадлежит внутренней области треугольника с вершинами А (а, 0), В (0, b), О (0,0), то на
Если точка М (х, у) принадлежит внутренней области треугольника с вершинами А (а, 0), В (0, b), О.

Определить, принадлежит ли точка внутренней области треугольника
помогите составить программу для этой задачи: определить, пренадлежит ли точка М(x,y) внутренней.

Принадлежит ли точка М внутренней области треугольника
Принадлежит ли точка М(x,y) внутренней области треугольника с вершинами A(0,0), B(a,0) и C(0,b) где.

Это геометрическая задача. Я геометрию уже смутно помню. Но придумал алгоритм и по нему написал сценарий:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# для любой точки внутри треугольника ABC тангенс угла между # отрезком MB и осью X будет меньше b/a (если точка не лежит на # границе треугольника или за пределами треугольника. # отсюда исходные требования: # a > 0 # b > 0 # y/(a-x) < b/aa = float(input('введите положительное число для \"a\": ')) b = float(input('введите положительное число для \"b\": ')) M = input('введите для точки \"M\" координаты X,Y: ').split(',') X = float(M[0]) Y = float(M[1]) tan = b/a if a>0 and b>0 and (Y/X  b/a): print('True') else: print('False')

пример 1:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 3.54,1.42
True

пример2:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 6.33,3.134
False

Добавлено через 14 минут
Сорри, случайно дал первый вариант, который с ошибкой. Вот верный:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# для любой точки внутри треугольника ABC тангенс угла между # отрезком MB и осью X будет меньше b/a (если точка не лежит на # границе треугольника или за пределами треугольника. # отсюда исходные требования: # a > 0 # b > 0 # y/(a-x) < b/aa = float(input('введите положительное число для \"a\": ')) b = float(input('введите положительное число для \"b\": ')) M = input('введите для точки \"M\" координаты X,Y: ').split(',') X = float(M[0]) Y = float(M[1]) tan = b/a if a>0 and b>0 and (Y/(a-X)  b/a): print('True') else: print('False')

пример 1:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 3.54,1.42
True

пример2:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 6.33,3.134
False

Добавлено через 18 минут
Сорри, и второй вариант не правильный, я в нем забыл исключить отрицательные координаты у точки M. Даю еще один вариант, надеюсь он последний:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

# для любой точки внутри треугольника ABC тангенс угла между # отрезком MB и осью X будет меньше b/a (если точка не лежит на # границе треугольника или за пределами треугольника. # отсюда исходные требования: # a > 0 # b > 0 # X > 0 # Y > 0 # y/(a-X) < b/aa = float(input('введите положительное число для \"a\": ')) b = float(input('введите положительное число для \"b\": ')) M = input('введите для точки \"M\" положительные координаты X,Y: ').split(',') X = float(M[0]) Y = float(M[1]) tan = b/a if a>0 and b>0 and X>0 and Y>0 and (Y/(a-X)  b/a): print('True') else: print('False')

Надеюсь, что этот вариант уже все предусматривает.

пример 1:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 3.54,1.42
True

пример2:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» координаты X,Y: 6.33,3.134
False

Добавлено через 4 минуты
пример3:
введите положительное число для «a»: 9.3
введите положительное число для «b»: 4.231
введите для точки «M» положительные координаты X,Y: -6.33,-3.134
False

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

Спасибо за помощь , но у меня почему-то оно так мне запустилась. Может я что-то не правильно ввожу так как в программировании полный ноль))

Может у Вас старая версия Python’а? У меня 3.6.3. Но программа будет работать на версии 3.0 и выше.

Добавлено через 18 минут
Хотя я кажется догадываюсь почему у Вас как бы не запускается.
Вы как запускаете этот сценарий?
Вы его копируете в текстовый редактор?
Даете файлу имя и расширение py ? name.py
Дальше если у Вас стоит на компьютере Python и Вы просто запустите этот файл. То он отработает и Python его мгновенно закроет.
Если Вы скопируете сценарий в редактор питона IDLE то там окно с содержимым закрываться не будет.
Что бы Pyton не закрывал файл (если просто запускать файл, как любую другую программу в windows) и Вы могли посмотреть результат его работы я добавил в конец сценария остановку. В конце на экран выведется надпись «СТОП» и окно питона закроется только когда Вы нажмете Enter. Скопируйте этот сценарий, который я даю ниже:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

# для любой точки внутри треугольника ABC тангенс угла между # отрезком MB и осью X будет меньше b/a (если точка не лежит на # границе треугольника или за пределами треугольника. # отсюда исходные требования: # a > 0 # b > 0 # X > 0 # Y > 0 # y/(a-X) < b/aa = float(input('введите положительное число для \"a\": ')) b = float(input('введите положительное число для \"b\": ')) M = input('введите для точки \"M\" положительные координаты X,Y: ').split(',') X = float(M[0]) Y = float(M[1]) tan = b/a if a>0 and b>0 and X>0 and Y>0 and (Y/(a-X)  b/a): print('True') else: print('False') input('\nСТОП')

Добавлено через 4 минуты
Или у Вас вообще не запустилось? Программа запрашивала ввести числа? Если нет, то что то у Вас другое.
Напишите подробно, куда Вы копируете сценарий и как его запускаете.

Принадлежит ли точка внутренней области треугольника
привет всем, помогите исправить ошибку. program tre1; var a,b,x,y: real; begin writeln.

Определить, принадлежит ли точка внутренней области квадрата
Определить, принадлежит ли точка внутренней области квадрата с правой верхней вершиной в точке с.

Определить, пренадлежит ли точка внутренней области треугольника
определить, пренадлежит ли точка М(x,y) внутренней области треугольника с вершинами А(0,a), B(b,0).

Определить, принадлежит ли точка стороне многоугольника, внутренней или внешней области
Определить, принадлежит ли точка стороне многоугольника, внутренней или внешней области.

Источник

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

Помогите сделать задание пожалуйста)
Определить, попадает ли точка в треугольную область, заданную координатами вершин. Все данные не обязаны быть целыми.
На языке python.
Сейчас имею такую программу:

1 2 3 4 5 6 7 8 9 10 11 12

x = float(input("Введите координату точки по x: ")) y = float(input("Введите координату точки по y: ")) a = float(input("Введите координату вершины 1 по x: ")) b = float(input("Введите координату вершины 1 по y: ")) c = float(input("Введите координату вершины 2 по x: ")) d = float(input("Введите координату вершины 2 по y: ")) e = float(input("Введите координату вершины 3 по x: ")) f = float(input("Введите координату вершины 3 по y: ")) if (x>=a or (-x)a) and (y>=b or (-y)b) and (x>=c or (-x)c) and (y>=d or (-y)d) and (x>=e or (-x)e) and (y>=f or (-y)f): print("Точка входит в область") else: print("Точка не входит в область")

Источник