Март
22nd

Урок 33. Точка в многоугольнике

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

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

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

Задача. Даны точка 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[1..n] 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[i].x,a[i].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[1].x;
  nom:=1;
  for i:=2 to n-1 do
       if maxx < a[i].x then begin maxx:=a[i].x;nom:=i;end;
  a[n].x:=a[1].x;   a[n].y:=a[1].y;
  for i:=1 to n-1 do
    if LinesCross(a[i].x,a[i].y,a[i+1].x,a[i+1].y,x,y,a[nom].x+1,a[nom].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
Выходные данные:
Точка внутри многоугольника.

 

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

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

 

Поделиться с друзьями



2 коммент. к “Урок 33. Точка в многоугольнике”

  1. Анатолий | Март 26, 2012 | Ответить

    Достойно у Вас на сайте! Сделано для людей. Творчески и по делу! Считаю, только целеустремленный, настойчивый, трудолюбивый и конечно, одаренный человек, вести сайт в состоянии, достойно! Учусь в Старт Ап проекте. Продвинутый курс. Мне нравится! Как у Вас? Сколько уделяете сайту времени? Дружить предлагаю нашим коллегам по сайтостроению. Каким образом правильнее? Успехов Вам творческих, благополучия достойного. Крепости духа! Слежу за обновлениями! Заходите в гости! Вам, буду рад!

  2. admin | Март 26, 2012 | Ответить

    Анатолий, спасибо Вам за поддержку.
    Я тоже прошла эту школу. Теперь свободное плавание. Изучаю заработок на партнерках, реселлинге.
    Сайт оказался мне знаком. Мы уже встречались! Мне нравятся ваши статьи. Сайт очень живой, светлый. Столько комментариев! Желая Вам дальнейших успехов, счастья и добра. Дружбу принимаю.

Оставить комментарий или два