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

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

Задача: Многоугольник на плоскости задается координатами своих вершин. Для заданной точки 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;
}

Ключевые слова: 
луч трассировка
ВложениеРазмер
lch.rar8.09 кб