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

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

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

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

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

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

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

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

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 .x * (p.y - p.y) +
 p.x * (p.y - p.y) +
 p.x * (p.y - p.y));
 S1 = abs (p.x * (p.y - y) +
 p.x * (y - p.y) +
 x * (p.y - p.y));
 S2 = abs (p.x * (p.y - y) +
 p.x * (y - p.y) +
 x * (p.y - p.y));
 S3 = abs (p.x * (p.y - y) +
 p.x * (y - p.y) +
 x * (p.y - p.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 )) || ((yp - yp ) != 0) && (x > ((xp - xp ) * (y - yp ) / (yp - yp ) + xp ))))
 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 ) && (yp ) &&
 ((yp - yp ) * (x - xp ) > (xp - xp ) * (y - yp ))
 ) || (
 (yp > yp) && (yp - yp ) * (x - xp ) - xp ) * (y - yp ))
 ))
 c = !c;
 }
 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 = @{$xp};
 	 my $j = $npol - 1;
 	 my $c = 0;
 	 for(my $i = 0; $i )) || ((@{$yp}))) &&
 ($x > (@{$xp} - @{$xp}) * ($y - @{$yp}) / (@{$yp} - @{$yp}) + @{$xp})) 
 {
 $c = !$c
 }
 $j = $i; 
 }
 return $c;
 }

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 .y.y)) or ((myP.y(myP.x-myP .x)*(y-myP .y) / (myP.y-myP .y)+myP .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 )) || ((yp (xp - xp ) * (y - yp ) / (yp - yp ) + xp )) {
 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 ) or (yp (xp - xp ) * (y - yp ) / (yp - yp ) + xp )): 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.x) * (points.y - points.y) / (points.x - points.x) + points.y;
 double minimal = min(points.x, points.x);
 double maximal = max(points.x, points.x);
 return (points.x != points.x) && (yh >= y) && (xh > minimal) && (xh 
Фрагмент основной программы:
…
 int count = 0;
 for (int i = 0; i 
Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.
Замечание: В данной реализации алгоритма луч направлен вниз.

Задача о принадлежности точки многоугольнику. Уро. Точка в многоугольнике

Урок из серии « Геометрические алгоритмы «

Здравствуйте, дорогой читатель! Продолжим знакомиться с геометрическими алгоритмами.

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

Задача. Даны точка P и простой N -угольник. Определить, принадлежит ли точка многоугольнику .

Пусть многоугольник на плоскости задается координатами своих N вершин в порядке обхода их по контуру по или против часовой стрелки (контур самопересечений не имеет). Для заданной точки P (x,y) определить, принадлежит ли она многоугольнику .

Идея решения этой задачи состоит в том, что нужно подсчитать количество пересечений луча, который имеет начало в данной точке P (x,y) и параллельного любой из осей координат. Для удобства возьмем ось абсцисс.

Из данного луча выделим отрезок с началом в точке P(x,y) и с концом в точке с максимальным значением абсциссы всех точек плюс 1 (эта точка заведомо находится вне многоугольника).

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

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

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

program geom5;
Const n=9; {Количество точек+1}
 _Eps: Real=1e-4; {точность вычислений}
type b=record
 x,y:real;
 end;
 myArray= array of b;
var
 input:text;
 x,y:real;
 i:integer;
 a:myArray;

procedure zapmas;
begin
 assign(input,'input.pas');
 reset(input);
 for i:=1 to n-1 do
 read(input, a .x,a .y);
 readln(input, x,y);
 close(input);
end;

function RealLess(Const a, b: Real): Boolean; {строго меньше}
begin
 RealLess := b-a> _Eps
end; {RealLess}

function VektorMulti(ax,ay,bx,by:real): real;
{Векторное произведение векторов}
…
end;
Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean;
{Пересекаются ли отрезки?}
…
end;

function InsidePoint(a:myArray):Boolean;
{Проверка принадлежности точки многоугольнику}

var i,k,nom: integer;
 maxx:real;
begin
 k:=0;
 maxx:=a.x;
 nom:=1;
 for i:=2 to n-1 do
 if maxx .x:=a.x; a.y:=a.y;
 for i:=1 to n-1 do
 if LinesCross(a .x,a .y,a.x,a.y,x,y,a.x+1,a.y)
 then k:=k+1;
 if k mod 2 0
 then InsidePoint:= true
 else InsidePoint:= false;
end;

begin {main}
 zapMas;
 if InsidePoint(a)
 then writeln('Точка внутри многоугольника.')
 else writeln('Точка вне многоугольнка.)
end.

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

Предварительно находим для точек максимальное значение абсциссы x_max. Берем отрезок с началом в заданной точке P (x,y) и концом в точке с координамами ( x_max +1, y). Далее подсчитываем количество пересечений этого отрезка со сторонами нашего многоугольника и делаем вывод о принадлежности точки многоугольнику.

Входные данные:
0.4 2 1.2 0.9 3 2.1 3.3 0.4 4 2.7 3.2 3.6 2 2.8 0.9 3
1.6 1.8
Выходные данные:
Точка внутри многоугольника.

 

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

 

На этом я с Вами прощаюсь. До встречи на следующем уроке.

Как понять, что точка лежит внутри фигуры. Точка внутри треугольника

Координаты треугольника

Координаты точки

Вы ввели следующие координаты многоугольника

Определение, принадлежит ли произвольная точка какому либо треугольнику (находится ли она внутри треугольника, на самом деле очень важная задача. Для нас она важна в контексте разбиения многоугольника на треугольники. Решение этой промежуточной задачи, позволит нам определять координаты центра тяжести многоугольника. Итак, существует достаточно много вариантов определения принадлежности точки треугольнику. Могу порекомендовать ссылку. Написано достаточно подробно и рассмотрены практически все варианты. Мы в своей реализации будем придерживаться следующего алгоритма Пусть у нас есть треугольник Высчитаем значение трех нижеуказанных выражений где x0,y0 - координаты произвольной точки Если все три значения одинакового знака, то точка внутри треугольника, если значение равно нулю, значит точка лежит на стороне треугольника В ином случае (если значения различные по знаку) , точка вне треугольника. Теперь проверим наше предположение Точка лежит внутри треугольника так как результат трех вычислений одинаков по знаку ( все они отрицательные) В этом случае точка F лежит вне треугольника, так как знаки результирующих вычислений различны. Хотелось бы заметить, что в случае точки Е наш бот, скажет что точка также находится внутри треугольника, хотя и находится на стороне треугольника( или как вариант в одной из вершин) . Это как уже было сказано связано с использованием этого бота, для расчета центра тяжести многоугольников. Как определить лежит ли точка внутри треугольника или снаружи. Калькулятор поможет определить находится ли заданная точка внутри заданного треугольника. Точка и треугольник задаются декартовыми координатами на плоскости. Детально описан алгоритм вычисления. Этот калькулятор определит где находится заданная точка внутри 2-мерного треугольника или вовне. Калькулятор использует простой алгоритм, основанный на свойствах векторного произведения. Описание этого алгоритма можно найти сразу за калькулятором. Точка в треугольнике Векторное произведение ( z - координата ) Точка внутри треугольника. Описание алгоритма. Векторное произведение векторов a и b, заданного декартовыми координатами в пространстве для 3-х мерного правого ортонормального базиса можно выразить так: . Векторное произведение обладает свойством антикоммутативности: Это важное свойство мы будем использовать для решения нашей задачи. Попарное векторное произведение векторов-сторон треугольника и вектора из вершины в точку Для того чтобы определить лежит ли точка P внутри треугольника ABC мы вычислим 3 векторных произведения: ABxAP, BCxBP and CAxCP. Так как наш треугольник и точка в 2-мерном пространстве на плоскости, третья координата z для трехмерного пространства равна нулю. Согласно формуле мы можем не вычислять координаты x и y для векторного произведения, если координата z векторов-множителей равна нулю - координаты x и y результата в этом случае всегда равны нулю (результирующий псевдо-вектор перпендикулярен плоскости треугольника). Знак результата произведения для оставшейся координаты (z) зависит от относительного положения умножаемых векторов. Если первый вектор (в нашем случае это сторона треугольника) находится правее второго вектора (вектор из вершины в точку P), то координата z результата будет положительна, если первый вектор будет левее второго - отрицательна, и в противном случае, если оба вектора идут в одном и том же направлении, результат будет равен нулю. Получив результаты по трем векторным произведениям, нам остается их проанализировать, чтобы понять лежит ли точка внутри треугольника: Если мы имеем и положительные и отрицательные результаты, точка лежит вне треугольника, если результаты только положительные или только отрицательные, точка - внутри. Таблица далее иллюстрирует все возможные варианты результатов векторного произведения: Ззамечательные точки треугольника - свойства, применение и примеры решения Замечательные точки треугольника не просто так описываются таким прилагательным. Для многих учеников, а начинают знакомиться с этим понятием в 8 классе, эта тема кажется наиболее интересной и простой в курсе геометрии, поэтому многочисленные теоремы и свойства запоминаются достаточно просто. Итак, какие же четыре точки называются замечательными? Перечислим их: точку пересечения медиан треугольника; точку пересечения биссектрис треугольника; точку пересечения высот треугольника; точку пересечения серединных перпендикуляров сторон треугольника. Все точки обладают своими особенностями и свойствами, про всех есть свои теоремы и следствия из них. Кроме того, существует свойство, которое справедливо сразу для четырёх этих точек. Вне зависимости от того, медиана ли это, биссектриса или высота, все они пересекаются в одной точке.

Принадлежность точки треугольнику. Алгоритм точка внутри треугольника

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

Калькулятор поможет определить находится ли заданная точка внутри заданного треугольника. Точка и треугольник задаются декартовыми координатами на плоскости. Детально описан алгоритм вычисления.

Этот калькулятор определит где находится заданная точка внутри 2-мерного треугольника или вовне. Калькулятор использует простой алгоритм, основанный на свойствах векторного произведения. Описание этого алгоритма можно найти сразу за калькулятором.

Точка в треугольнике

Векторное произведение ( z - координата )

Точка внутри треугольника. Описание алгоритма.

Векторное произведение векторов a и b, заданного декартовыми координатами в пространстве для 3-х мерного правого ортонормального базиса можно выразить так:.Векторное произведение обладает свойством антикоммутативности:

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

Попарное векторное произведение векторов-сторон треугольника и вектора из вершины в точку

Для того чтобы определить лежит ли точка P внутри треугольника ABC мы вычислим 3 векторных произведения: ABxAP, BCxBP and CAxCP. Так как наш треугольник и точка в 2-мерном пространстве на плоскости, третья координата z для трехмерного пространства равна нулю. Согласно формуле мы можем не вычислять координаты x и y для векторного произведения, если координата z векторов-множителей равна нулю - координаты x и y результата в этом случае всегда равны нулю (результирующий псевдо-вектор перпендикулярен плоскости треугольника). Знак результата произведения для оставшейся координаты (z) зависит от относительного положения умножаемых векторов. Если первый вектор (в нашем случае это сторона треугольника) находится правее второго вектора (вектор из вершины в точку P), то координата z результата будет положительна, если первый вектор будет левее второго - отрицательна, и в противном случае, если оба вектора идут в одном и том же направлении, результат будет равен нулю.Получив результаты по трем векторным произведениям, нам остается их проанализировать, чтобы понять лежит ли точка внутри треугольника:Если мы имеем и положительные и отрицательные результаты, точка лежит вне треугольника, если результаты только положительные или только отрицательные, точка - внутри.Таблица далее иллюстрирует все возможные варианты результатов векторного произведения:

Точка внутри треугольника

Координаты треугольника

Координаты точки

Вы ввели следующие координаты многоугольника

Определение, принадлежит ли произвольная точка какому либо треугольнику (находится ли она внутри треугольника, на самом деле очень важная задача. Для нас она важна в контексте разбиения многоугольника на треугольники. Решение этой промежуточной задачи, позволит нам определять координаты центра тяжести многоугольника. Итак, существует достаточно много вариантов определения принадлежности точки треугольнику. Могу порекомендовать ссылку. Написано достаточно подробно и рассмотрены практически все варианты. Мы в своей реализации будем придерживаться следующего алгоритма Пусть у нас есть треугольник Высчитаем значение трех нижеуказанных выражений где x0,y0 - координаты произвольной точки Если все три значения одинакового знака, то точка внутри треугольника, если значение равно нулю, значит точка лежит на стороне треугольника В ином случае (если значения различные по знаку) , точка вне треугольника. Теперь проверим наше предположение Точка лежит внутри треугольника так как результат трех вычислений одинаков по знаку ( все они отрицательные) В этом случае точка F лежит вне треугольника, так как знаки результирующих вычислений различны. Хотелось бы заметить, что в случае точки Е наш бот, скажет что точка также находится внутри треугольника, хотя и находится на стороне треугольника( или как вариант в одной из вершин) . Это как уже было сказано связано с использованием этого бота, для расчета центра тяжести многоугольников. Определение принадлежности точки треугольнику Дано: у нас есть треугольник, нам известны только координаты его вершин. У нас есть точка, нам известны её координаты. Что нужно узнать: нужно установить принадлежность точки треугольнику. В данной статье разбирается несколько разных методов определения принадлежности точки треугольнику. Метод сравнения площадей В данном методе сначала находятся площади 3-х треугольников, которые образует данная точка с каждой стороной треугольника. В нашем случае(рис. 1) это треугольники ABP, BCP, CAP и их площади s1, s2, s3 соответственно. Затем находится площадь самого треугольника ABC. Найденный площади сравниваются — если сумма 3-х площадей равна площади всего треугольника, то значит точка принадлежит треугольнику. При сравнении, как правило, задаётся погрешность.

Принадлежность точки многоугольнику с++. Расположение точки относительно многоугольника

Метки нет( Все метки )

Доброго времени суток!
Очень нужна помощь в написании программы на С++!
Задача такая:
Множество точек определяет многоугольник. Для данной точки определить где она расположена относительно этого многоугольника: внутри, снаружи, на границе.
(предполагается, что в файле записано несколько пар чисел, которые можно рассматривать как координаты точек на плоскости или как координаты концов отрезков.)
Поблема заключается в том, что я никогда ранее не сталкивлся со структурами и не представляю как это можно написать.
Общее решение задачи:
Для решения этой задачи проведем прямую из точки а в некоторую бесконечно удаленную от многоугольника точку. На всем своем протяжении эта прямая может n раз пересечь границу нашего многоугольника. Если прямая не пересекает ни одного ребра заданного многоугольника, то n=0. Если следовать по прямой из бесконечно удаленной точки к точке a, то первое пересечение приведет нас внутрь многоугольника, при втором пересечением мы выйдем за границу этого многоугольника, при третьем — снова окажемся внутри и т.д. Из этих наблюдений можно заключить, что каждое нечетное пересечение означает попадание внутрь нашего многоугольника, а каждое четное — выход из него. Таким образом, если при движении по прямой только что описанным образом, мы попадаем в точку a с нечетным числом пересечений границы многоугольника, то точка a находится внутри него, если же число пересечений четно, то точка лежит вне многоугольника.
Добавлено через 8 часов 51 минуту Очень нужно до вторника, помогите пожалуйста, напишите хотя бы как задать координаты на плоскости и как с ними делать простейшие арифметические операции!