Алгоритми за тримерни обеми

Тестове за принадлежност на точка вътре в площта на произволен многоъгълник (за включване на точка в многоъгълник)

Тест 1 (алгоритъм 1):

NC := 0; { Брой на пресечните точки на лъча, започващ от точка P и успореден на оста x, с ръбовете на многоъгълника }

for k := 1 to n do

begin

{ Решава се системата от уравнения Pk+t(Pk+1-Pk) = P+ui

за t и u, i е единичен вектор по оста x }

if (u>0) and (0<=t<1) then NC := NC+1;

end;

Inside := ODD(NC);

Тест 2 (алгоритъм 2):

Началото на координатната система се пренася в точка P

NC := 0; { Брой на пресечните точки на оста x с ръбовете на многоъгълника }

x1 := P[n].x; y1 := P[n].y;

UP1 := y1>=0;

for k := 1 to n do

begin

x2 := P[k].x; y2 := P[k].y;

UP2 := y2>=0;

if UP1 <> UP2 then

{ Има вероятност за пресичане на ръба с оста x }

if (x1>0) and (x2>0) then NC := NC + 1

else if ((x1>0) or (x2>0) then begin

x:=x1-y1*(x2-x1)/(y2-y1);

if x>0 then NC := NC + 1;

end;

x1:=x2; y1:=y2;

UP1:=UP2;

end;

Inside := ODD(NC);

Тест за принадлежност на точка в изпъкнал обем (алгоритъм 3)

Тялото се представя като обем, ограден с 4 или повече равнини, всяка зададена с уравнението си n.P=s, където n e вътрешна нормала