Проверка на принадлежность точки многоугольнику
Формулировка задачи проста. Задан последовательный набор точек (хi,уi), i=1..n. Для заданной точки проверить, принадлежит ли она замкнутому многоугольнику, заданному этими точками, или нет.
Используется метод трассировки луча. Суть его в том, что если из заданной точки провести произвольный луч (не важно в каком направлении), то по числу пересечений этого луча со сторонами многоугольника можно однозначно сказать, лежит ли точка внутри или снаружи. А именно, если число пересечений четно (или 0) - то снаружи, нечетно - внутри. Причем, как оказывается, не важно в каком порядке следуют стороны. Для проверки пересечения луча со сторонами, используем процедуру из рассмотренной ранее задачи
нахождение точки пересечения двух отрезков на плоскости, слегка ее видоизменив. А именно, если раньше нас интересовали только такие решения системы уравнений, когда параметр tb лежит в диапазоне [0.1] (что определяте отрезок), то теперь нас будут устраивать значения [0,бесконечность) (что определяет луч).
Несколько слов о программе. Исходные данные в виде восьми координат считываются из файла poligon.txt. В качестве примера можно использовать, например, такие значения:
1 1 2 1 2 2
3 2 3 1 4 0
4 5 1 5
Только убедитесь, что после последней пятерки в файле не присутствуют ни пробелы, ни концы строк, иначе будет прочитан лишнй ноль.
Точка а задается случайным образом.
Вместо сравнения d с нулем (if (d=0) ...) используется сравнение с малым числом Eps. Сделано это для того, чтобы не делить на очень малые числа. В вещественных представлениях числа 0 зачастую присутствуют что-нибудь вроде 1Е-12, и формального равенства с нулем нет, но фактически это самый что ни на есть 0.
Замечание из форума
const eps = 0.000001;
maxNodes = 50;
type point = object
x,y:real;
procedure setPoint(xp,yp:real);
end;
poligonType = array[1..maxNodes] of point;
procedure point.setPoint(xp,yp:real);
begin
x:=xp;
y:=yp;
end;
var a,ax,c:point;
function readPoligon(var p:poligonType):integer;
var buf:text;
n:integer;
x1,y1:real;
begin
assign(buf, 'poligon.txt');
reset(buf);
n:=0;
while not eof(buf) and (n<=maxNodes) and (IOResult=0) do
begin
inc(n);
read(buf, p[n].x);
if (IOResult = 0) then
read(buf, p[n].y);
end;
if (IOResult <> 0) then dec(n);
if (not eof(buf)) then
writeln(' The maximum number of nodes has been reached. Using maxN=',maxNodes);
readPoligon := n;
end;
const
ONE_INTERSECTION_POINT = 1;
CHUNKS_ARE_PARALLEL = 0;
NO_INTERSCTION = -1;
A1_BORDER_INTERSECTION = 2;
function checkIntersection(a1,a2,b1,b2:Point):shortint;
var d,da,db,ta,tb: real;
begin
d :=(a1.x-a2.x)*(b2.y-b1.y) - (a1.y-a2.y)*(b2.x-b1.x);
da:=(a1.x-b1.x)*(b2.y-b1.y) - (a1.y-b1.y)*(b2.x-b1.x);
db:=(a1.x-a2.x)*(a1.y-b1.y) - (a1.y-a2.y)*(a1.x-b1.x);
if (abs(d)<eps) then
checkIntersection := CHUNKS_ARE_PARALLEL
else
begin
ta:=da/d;
tb:=db/d;
if (abs(ta)<eps) and ((0<=tb) and (tb<=1))
then checkIntersection := A1_BORDER_INTERSECTION
else
if (0<=ta)
and (0<=tb) and (tb<=1)
then
begin
c.setPoint(a1.x+ta*(a2.x-a1.x),a1.y+ta*(a2.y-a1.y));
checkIntersection := ONE_INTERSECTION_POINT
end
else checkIntersection := NO_INTERSCTION;
end;
end;
var i,n:integer;
plg:poligonType;
xr,yr:real;
function pointInsidePoligon(a:Point;plg:poligonType):integer;
var i,k,i1,i2,r:integer;
ax:Point;
begin
ax.setPoint(a.x+5,a.y);
k:=0;
for i:=1 to n do
begin
i1:=i; i2:=i+1; if (i=n) then i2:=1;
r:=checkIntersection(a,ax,plg[i1],plg[i2]);
if (r=2) then
begin
pointInsidePoligon := 2; exit;
end;
if (r=1) then
k:=1-k;
end;
pointInsidePoligon := k;
end;
begin
n:=readPoligon(plg);
xr:=4; yr:=1;
for i:=1 to 20 do
begin
a.setPoint(xr,yr);
write(i:3,'. Point A(',a.x:8:4,',',a.y:8:4,') ');
case pointInsidePoligon(a,plg) of
1: writeln('is inside');
0: writeln('is outside');
2: writeln('on border');
end;
xr:=random(60); xr:=(xr)/10;
yr:=random(50); yr:=(yr)/10;
end;
end.
|
