Вторник, 15.06.2021, 17:52
Приветствую Вас Гость | RSS
Авторизация
Статистика


Rambler's Top100


Яндекс.Метрика
Контакты
356118831
Mr_Ser_Win
Поиск
Архив записей
Календарь
«  Май 2011  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
3031
Реклама

Книжный портал

Блог

Главная » 2011 » Май » 12 » Алгоритм проверки принадлежности точки многоугольнику. Метод трассировки луча
09:34
Алгоритм проверки принадлежности точки многоугольнику. Метод трассировки луча

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


Задача: Многоугольник на плоскости задается координатами своих вершин. Для заданной точки Z(x,y) определить, принадлежит ли она стороне многоугольника или лежит внутри или вне его.

Принадлежность точки стороне проверяется просто: если концевые точки стороны A(x1,y1) и B(x2,y2), то, если точка Z(x,y) принадлежит стороне, то должно выполняться равенство:

(x-x2)*(y1-y2)=(y-y2)*(y1-y2)

Далее, проведем из точки Z прямую, параллельную оси OX и проверим, сколько сторон многоугольника пересекает луч, идущий от точки Z вправо. Если 0, то Z - вне многоугольника, нечетное количество - то внутри, если четное количество - то снаружи.

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

Необходимо обработать случай, когда прямая пересекает одну из вершин многоугольника (например, A).

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

Также рассмотрим случай, когда прямая проходит по стороне (например АВ).

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

Чтобы узнать пересекает ли прямая, проходящая через точку Z параллельно оси OX, сторону АВ, надо обозначить через F(x,y)=b-y (где b - координата точки Z по у). Если эта прямая пересекает отрезок, то либо концы отрезка лежат в различных полуплоскостях, либо хотя бы одна концевая точка отрезка лежит на прямой. Это равносильно выполнению следующего неравенства F(x1,y1)*F(x2,y2)<=0


gboolean on_click(GtkWidget *widget, GdkEventButton *event, gpointer data)//функция обработки щелчка мыши
{
 gc = widget->style->fg_gc[GTK_WIDGET_STATE(widget)];
 int i,j;
 int x,y;//переменные, в которые записываются координаты текущей точки
 int count,ct;
 int h,l,r;//вспомогательные переменные
 
 clrbelong.pixel = 0; //цвет, обозначающий, что точка 
 clrbelong.red = 225*257; //принадлежит одной из сторон
 clrbelong.green = 150*257; //многоугольника
 clrbelong.blue = 0*257; 
 
 clroutside.pixel = 0; //цвет, обозначающий, что точка не 
 clroutside.red = 225*257; //принадлежит ни одной из сторон
 clroutside.green = 0*257; //многоугольника
 clroutside.blue = 0*257;
 
 clrinside.pixel = 0; //цвет, обозначающий, что точка в
 clrinside.red = 0*257; //многоугольнике
 clrinside.green = 139*257; 
 clrinside.blue = 0*257; 
 
 if(x_mouse > 0 && x_mouse < widget->allocation.width && y_mouse > 0 && y_mouse < widget->allocation.height)
 {
 c.X = x_mouse; 
 c.Y = y_mouse;
 p[k]=c;//записываем в массив координаты новую точку с экрана
 k++;
 } 
 x=p[k-1].X;//записываем ее координаты в переменные х и у
 y=p[k-1].Y;
 //проверка принадлежности точки одной из сторон мн-ка
 count=1;
 for(i=1;i<=num;i++)//проверяем, лежит ли данная точка на какой-нибудь из сторон прямоугольника
 {
 if(i==num)
 j=1;
 else
 j=i+1;
 if(((x-a[j].X)*(a[i].Y-a[j].Y))==((y-a[j].Y)*(a[i].X-a[j].X)))
 {//проверка, лежит ли данная точка на отрезке или только на его продолжении
 if(((a[i].X<a[j].X)&&(a[i].X<=x)&&(x<=a[j].X))||((a[i].X>a[j].X)&&(a[j].X<=x)&&(x<=a[i].X)))
 {
 gdk_gc_set_rgb_fg_color(gc,&clrbelong);
 gdk_draw_arc(widget->window,gc,TRUE, x-4, y-4, 8, 8, 0, 360*64);
 count = 0;
 break;
 }
 }
 }
 
 //если данная точка не лежит ни на одной строне многоугольника, то выполняем следующее 
 if(count)
{ 
 //проводим прямую || ox 
 gdk_gc_set_rgb_fg_color(gc,&clr);
 gdk_draw_line(widget->window, gc, x, y, WIDTH, y);
 
 ct=0;//счетчик, в который записывается кол-во пересечений многоугольника лучом
 for(i=1;i<=num;i++)//перебираем каждую сторону мн-ка
 {
 if(i==num)
 j=1;
 else
 j=i+1;
 
 //проверяем, пересекает ли прямая отрезок (сторону)
 if(((y-a[i].Y)*(y-a[j].Y))<0)
 { //"<" означает, что мы не берем случай, когда прямая проходит через концы отрезка
 //
 //проверка с какой стороны точка
 if(x<((y-a[i].Y)*(a[j].X-a[i].X)/(a[j].Y-a[i].Y)+a[i].X))
 {
 ct++;//если справа - увеличиваем счетчик на единицу
 }
 }
 //если данная сторона лежит на луче
 else if((a[i].Y==a[j].Y)&&(y==a[i].Y))
 {
 if(i==1)
 l=num;
 else
 l=i-1;
 if(i==num-1)
 r=1;
 else
 r=j+1;
 //если \_ или _/ , то добавляем к счетчику единицу
 // \ / 
 // _
 //если \_/ или / \ , то добавляем к счетчику двойку
 if(((y-a[l].Y)*(y-a[r].Y))<0)
 {
 ct++;
 }
 else if(((y-a[l].Y)*(y-a[r].Y))>0)
 {
 ct+=2;
 }
 }
 //если же прямая проходит через конец отрезка, тогда 
 //проверяем, как расположены стороны относительно данной точки
 else if(y==a[i].Y)
 {
 if(i==1)
 h=num;
 else
 h=i-1;
 
 //если стороны расположены:
 // \ или /
 // / \ ,то прибавляем к счетчику единицу
 
 //если стороны расположены:
 // \/ или /\ ,
 //то прибавляем к счетчику двойку
 
 if(((y-a[h].Y)*(y-a[j].Y))<0)
 {
 ct++;
 }
 else if(((y-a[h].Y)*(y-a[j].Y))>0)
 {
 ct+=2;
 }
 }
 }
 if(ct%2==0)//если четное кол-во пересечений луча с мн-ком, то точка снаружи
 {
 gdk_gc_set_rgb_fg_color(gc,&clroutside);
 gdk_draw_arc(widget->window,gc,TRUE, x-4, y-4, 8, 8, 0, 360*64);
 }
 else//если нечетное - то внутри
 {
 gdk_gc_set_rgb_fg_color(gc,&clrinside);
 gdk_draw_arc(widget->window,gc,TRUE, x-4, y-4, 8, 8, 0, 360*64);
 }
} 
 return TRUE;
}
Материал  позаимствован с сайта 

Просмотров: 2716 | Добавил: Mr_Ser_Win | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Получить бонус WMR

Вы можете получить WMR-бонус в размере 0,01-0,10 WMR на свой кошелек 1 раз в сутки

Кошелек
Код Защитный код

Обмен Webmoney



Получить больше бонусов
Помощь сайту

Облако тегов
Реклама
Качественный хостинг
Бесплатная раскрутка сайтов и блогов - YouRaise.Ru
Начать Заработок на Блоге
Хранилище фотографий фото хостинг Храни фото здесь!
Драки: дом2 драки
обмен играми Все для геймера!
А ты играл в XBOX 360? продажа развивающие игры в твоем городе
AlfaInternet.Su - Регистрация сайта в каталогах поисковиках

Регистрация сайта в Каталогах
Ваше имя:
Ваш email:
Регистрация при поддержке AlfaInternet.Su
PR-CY.ru