|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 21 Mar 2002 07:29:41
To : Igor Subbotin
Subject : Re: многоyгольник и точка
--------------------------------------------------------------------------------
До меня дошли слухи, что *19.03.02* *0:42:17* пролетало сообщение
от Igor к *Dennis Adamchuck* про *"многоyгольник и точка"*. И я решил
вмешаться.
[...]
IS> Многоyгольник задается кооpдинатами отpезков (x1,y1,x2,y2)... нy а точка
IS> своими кооpдинатами(x,y).
Вот тебе часть того что может станет факом:
{!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Все функции написаны в расчете на то что выполнено "замыкание"
многоугольника, т.е. p[0]:=p[n]; p[n+1]:=p[1];}
{_Проверка вхождения точки в многоугольник._
Считается количество пересечений луча из этой точки со
сторонами многоугольника.}
function inpoly(p: tpoint; q: tpoly; n: integer): shortint;
var ans: boolean;
function crs(a1,a2: tpoint): integer;
var x: float;
begin
crs:= 0;
if abs(a1.y-a2.y)<eps then
begin
if(abs(p.y-a1.y)<eps)and((p.x-a1.x)*(p.x-a2.x)<0.0)then ans:= false;
exit;
end;
if((a1.y-p.y)*(a2.y-p.y)>0.0)then exit;
x:= a2.x-(a2.y-p.y)/(a2.y-a1.y)*(a2.x-a1.x);
if abs(x-p.x)<eps then ans:= false else
if(x<p.x)then
begin
crs:= 1;
if(abs(a1.y-p.y)<eps)and(a1.y<a2.y)then crs:= 0 else
if(abs(a2.y-p.y)<eps)and(a2.y<a1.y)then crs:= 0;
end;
end;
var i,c: integer;
begin
c:= 0; ans:= true;
for i:= 1 to n do
begin
inc(c,crs(q[i],q[i+1]));
if not ans then break;
end;
if not ans then inpoly:= -1 else inpoly:= c and 1;
end;
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Хороший гопник - мертвый гопник. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: многоyгольник и точка