Алгоритм точки в многоугольнике

Алгоритм точки в многоугольнике

Алгоритм точки в многоугольнике

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

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

Благодаря тому, что многоугольник является частным случаем замкнутой односвязной области, алгоритм решения задачи может быть следующим. Вершины многоугольника последовательно нумеруются от 1 до n. Из заданной точки проводятся лучи, проходящие через вершины 2 и 1. Определяется разность направлений этих лучей. Процесс повторяется для пары вершин 3 и 2 и т. д. до пары вершин n и (n-1) и, наконец, 1 и n. Указанные разности суммируются. Если сумма равна нулю, то делается вывод о том, что заданная точка лежит вне заданного многоугольника.

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

Содержание

Алгоритм, требующий простых арифметических операций

Для принадлежности точки выпуклому многоугольнику вершины последовательно нумеруются от 1 до n. Вершина с условным номером 1 соединяется отрезками со всеми другими вершинами. Образуются (n-2) треугольника с вершинами {1, (i-1), i}, где 3 ≤ i ≤ n. Осуществляется проверка принадлежности заданной точки хотя бы одному из этих треугольников.

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

Иначе подобное разбиение многоугольника на треугольники и проверка принадлежности заданной точки треугольникам выполняется для вершин с последующими номерами — до выполнения одного из условий:

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

Что касается проверки принадлежности точки треугольнику, то, благодаря тому, что треугольник является выпуклым многоугольником, соответственно, может использоваться следующий алгоритм проверки принадлежности точки выпуклому многоугольнику. Если при последовательном обходе вершин в одном направлении выясняется, что заданная точка и вершина n + 2 лежат по разные стóроны от стороны, соединяющей текущую вершину n и вершину n + 1, то делается вывод, что точка не принадлежит многоугольнику, и процесс прерывается. Если обход вершин не был прерван, то делается вывод, что точка принадлежит многоугольнику.

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

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

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

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

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

  • указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида
   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; n++)
 {
  flag = 0;
  i1 = n < N-1 ? n + 1 : 0;
  while (flag == 0)
  {
   i2 = i1 + 1;
   if (i2 >= 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;
  }
  if (flag == 0)
    break;
 }
 return flag;
}

Очень быстрый алгоритм

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

 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]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
       (x > (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]<=y) && (y<=yp[j]) &&
       ((yp[j] - yp[i]) * (x - xp[i]) > (xp[j] - xp[i]) * (y - yp[i]))
     ) || (
       (yp[i]>yp[j]) && (yp[j]<=y) && (y<=yp[i]) &&
       ((yp[j] - yp[i]) * (x - xp[i]) < (xp[j] - xp[i]) * (y - yp[i]))
     ))
       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 < $npol;$i++) {
           if ((((@{$yp}[$i]<=$y) && ($y<@{$yp}[$j])) || ((@{$yp}[$j]<=$y) && ($y<@{$yp}[$i]))) &&
              ($x > (@{$xp}[$j] - @{$xp}[$i]) * ($y - @{$yp}[$i]) / (@{$yp}[$j] - @{$yp}[$i]) + @{$xp}[$i])) 
               {
                 $c = !$c
               }
                $j = $i;  
        }
 return $c;
 }

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){
  npol = xp.length;
  j = npol - 1;
  var c = 0;
  for (i = 0; i < npol;i++){
      if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
      (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {
       c = !c
       }
       j = i;
  }
return c;
}
inPoly(x,y);

Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин

Функция 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 <= maximal);
 }

Фрагмент основной программы:

 ...
 int count = 0;
 for (int i = 0; i < n; i++)
 {
   count += Cross(i);
 }
 ...

Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.

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

Литература

  • Джалиашвили З. О., Подольский А. А. Алгоритмы анализа ответов в тестовых заданиях с графическим интерфейсом. Информационный бюллетень ассоциации История и компьютер, N 1, 2005.
  • Ласло М. Вычислительная геометрия и компьютерная графика на C++. М.: БИНОМ, 1997.
  • Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Алгоритм точки в многоугольнике" в других словарях:

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Компьютерная геометрия — Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… …   Википедия

  • Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… …   Википедия

  • Теорема Бойяи — Гервина — утверждает, что любые два равновеликих многоугольника равносоставлены. Более формально: Пусть P и Q суть два многоугольника с одинаковой площадью. Тогда их можно разрезать соответственно на многоугольники и , так что для любого …   Википедия

  • Нейронная сеть Кохонена — Нейронные сети Кохонена  класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена… …   Википедия

  • Векторное квантование — Нейронные сети Кохонена  класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена… …   Википедия

  • Карта данных — Нейронные сети Кохонена  класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»