 |
|
Задача 3. Перевірка належності точки многокутнику
Під належністю точки многокутнику приймається належність точки внутрішній області многокутника або його межі. В тому числі, всі вершини належать многокутнику.
1) Аналогічно до задачі про належність точки трикутнику, можна розв’язати задачу для довільного опуклого многокутника, розбивши його на трикутники.
|
 |
Програмний код:
Program Prog 5;
var xx,yy:array[1..100] of real;
x,y,a1,b1,c1,s1,s_mn, s_tr:real;
i,n:integer;
procedure line(xp,yp,xk,yk:real;var l:real);
begin
l:=sqrt(sqr(xp-xk)+sqr(yp-yk));
end;
procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;
begin
writeln(‘Введіть кількість вершин многокутника’);
readln(n);
writeln(‘Введіть координати вершин многокутника’);
for i:=1 to n do readln(xx[i],yy[i]);
writeln(‘Введіть координати точки’);
readln(x,y);
s_mn:=0;
for i:=1 to n-2 do begin
line(xx[i],yy[i],xx[i+1],yy[i+1],a1);
line(xx[i+1],yy[i+1],xx[i+2],yy[i+2],b1);
line(xx[i+2],yy[i+2],xx[i],yy[i],c1);
pl(a1,b1,c1,s1);
s_mn:=s_mn+s1;
end;
s_tr:=0;
xx[n+1]:=xx[1];
yy[n+1]:=yy[1];
for i:=1 to n do begin
line(xx[i],yy[i],xx[i+1],yy[i+1],a1);
line(xx[i],yy[i],x,y,b1);
line(xx[i+1],yy[i+1],x,y,c1);
pl(a1,b1,c1,s1);
s_mn:=s_mn+s1;
end;
if s_mn=s_tr then writeln(‘належить’) else writeln(‘не належить’);
end.
2) Для визначення положення точки відносно многокутника перевіряється той факт, що точка лежить по одну сторону від всіх ребер полігону. Якщо це не так, то вона зовні. В загальному випадку такий спосіб не працює.
Програмний код:
Program Prog 5;
var x,y:array[1..100] of real;
x0,y0:real;
i,n:integer;
b:Boolean;
begin
writeln(‘Введіть кількість вершин многокутника’);
readln(n);
writeln(‘Введіть координати вершин многокутника’);
for i:=1 to n do readln(x[i],y[i]);
writeln(‘Введіть координати точки’);
readln(x0,y0);
x[n+1]:=x[1];
y[n+1]:=y[1];
b:=true;
for i:=1 to n do begin
if (y0>y[i])=(y0<=y[i+1] then
if x0-x[i]<(y0-y[i])*(x[i+1]-x[i])/(y[i+1]-y[i]) then b:=not(b);
if not(b) then writeln(‘належить’) else writeln(‘не належить’);
end.
3) Припустимо, що нам необхідно визначити належність точки A многокутнику р. Для цього з деякої віддаленої точки проведемо пряму лінію в точку А. На цьому шляху може зустрітися нуль або декілька перетинів сторін межі многокутника: при першому перетині ми входимо всередину многокутника, при другому — виходимо з нього, при третьому перетині знову входимо всередину і так до тих пір, поки не досягнемо точки А. Таким чином кожний непарний перетин означає попадання всередину многокутника р, а кожне парне — вихід з нього. Якщо ми потрапляємо в точку а з непарним числом перетинів сторін многокутника, то точка а лежить усередині полігону, а якщо виходить парне число перетинів, то точка знаходиться зовні многокутника р. Наприклад, промінь ra перетинає межу тільки одного разу, оскільки одиниця число непарне, то точка а знаходиться усередині полігону. Щодо точки b ми прийдемо до висновку, що вона лежить зовні многокутника, оскільки промінь rb перетинає сторони парне число разів (двічі).
Побудова алгоритму на основі цієї ідеї базується на двох особливостях.
По-перше, для вирішення задачі підходить будь-який промінь, що починається в аналізованій точці А. Тому для простоти виберемо правий горизонтальний промінь ra, що починається в точці А і напрямлений вправо паралельно додатній напівосі х.
По-друге, порядок розташування ребер, що перетинаються променем ra байдужий, має значення лише парність (парна або непарна кількість) їх загального числа. Отже, замість моделювання руху уздовж променя ra для алгоритму достатньо визначити всі перетини ребер у будь-якому порядку, визначаючи парність у міру просування. Найпростішим розв’язком буде обхід межі полігону з перемиканням біта парності при кожному виявленні ребра, що перетинається променем ra.
Щодо горизонтального променя ra, направленого управо, розрізнятимемо три типи ребер многокутника: дотичне ребро, що містить точку А; перетинаюче ребро, що не містить точку А; байдуже ребро, яке зовсім не має перетин з променем га. Наприклад, ребро с є перетинаючим ребром, ребро d — дотичним, а ребро е — байдужим.
