Главная
 Сайт Андрея Зайчикова
Воскресенье, 5 Августа 2007г. 
Карта сайта Поиск по сайту Написать письмо  
 .:Навигатор 
Новости
Библиотека
Статьи
Олимпиады
FAQ (ЧаВо)
Гостевая книга 
Ссылки
 .:Информация 


Вхождение точки в многоугольник

Андрей Зайчиков (август 2001 г.)
Эта статья рассказывает о том, как проверить, входит ли точка на плоскости в произвольный (не обязательно выпуклый) многоугольник. Если у Вас есть какие-либо вопросы, дополнения или коментарии пишите.

Есть точка B и многоугольник A[кол-во_вершин]. Выпустим луч из B и найдем количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через вершину, то все понятно - точка внутри, если количество пересечений нечетно, и снаружи если четно (в том числе и ноль).

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

Варианты прохождения луча через вершину:

  1. Ребра вершины лежат по одну сторону от луча, тогда четность количества пересечений не меняется.
  2. Ребра воршины лежат по разные стороны от луча, тогда четность количества пересечений меняется.
  3. Сторона многоугольника лежит на луче, тогда четность количества пересечений не меняется.

Получается алгоритм: выпускаем из точки B горизональный луч (т.е. параллельный OX) и все ребра многоугольника, кроме горизонтальных, проверяем на пересечение с этим лучем. В случае, когда луч проходит через вершину, т.е. пересекает сразу два ребра, зачисляем это пересечение только для тех ребер, для которых эта вершина является верхней.

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

bool is_inside(point *a, point b, int n) {
//a - массив вершин многоугольника, их n штук
//b - точка для проверки вхождения
   int count=0;         //количество пересечений
   for(int i=0; i<n; i++)
   {
      int j=(i+1)%n;  //следующая вершина
      if(a[i].y==a[j].y)
         continue;
      if(a[i].y>b.y && a[j].y>b.y)
         continue;
      if(a[i].y<b.y && a[j].y<b.y)
         continue;
      if(max(a[i].y,a[j].y)==b.y)
         count++;
      else {
         if(min(a[i].y,a[j].y)==y)
            continue;
         else {
            float t=(b.y-a[i].y)/(a[j].y-a[i].y);
            if(a[i].x+t*(a[j].x-a[i].x)>=b.x)
            count++;
         }
      }
   }
   return count&1;
}

 
 © Андрей Зайчиков