4.2. 点与三角形

4.2. 点与三角形

4.2.1. 点与三角形的关系

1. 二维空间

return ({OUSIDE, INSIDE, ON_EDGE})
1.    ${d_0} = \left( {{V_1} - {V_0}} \right) \times \left( {P - {V_0}} \right)$;
2.    ${d_1} = \left( {{V_2} - {V_1}} \right) \times \left( {P - {V_1}} \right)$;
3.    ${d_2} = \left( {{V_0} - {V_2}} \right) \times \left( {P - {V_2}} \right)$;
4.    ${s_0} = {d_0} \cdot {d_1},{s_1} = {d_1} \cdot {d_2}$;
5.    if${s_0} \prec 0$或者${s_1} \prec 0$, then
6.           return OUSIDE；
7.    else${s_0} = 0$或者${s_1} = 0$, then
8.           return ON_EDGE；
9.    else
10.          return INSIDE;
11.   end if

2. 三维空间

return ({NOT_ON_PLANE, OUSIDE, INSIDE, ON_EDGE})
1.    $\vec n = ({V_1} - {V_0}) \times ({V_2} - {V_0}),d = - \vec n \cdot {V_0}$
2.    if$P \cdot \vec n + d \ne 0$, then
3.           return NOT_ON_PLANE;                   //点$P$在平面$\pi$外；
4.    end if
5.    ${d_0} = \vec n \cdot \left[ {\left( {{V_1} - {V_0}} \right) \times \left( {P - {V_0}} \right)} \right]$;
6.    ${d_1} = \vec n \cdot \left[ {\left( {{V_2} - {V_1}} \right) \times \left( {P - {V_1}} \right)} \right]$;
7.    ${d_2} = \vec n \cdot \left[ {\left( {{V_0} - {V_2}} \right) \times \left( {P - {V_2}} \right)} \right]$;
8.    if ${d_0} \prec 0$|| ${d_1} \prec 0$|| ${d_2} \prec 0$, then
9.           return OUSIDE;
10.   else if ${d_0} = = 0$||${d_1} = = 0$|||${d_2} = = 0$|, then
11.          return ON_EDGE；
12.   else
13.          return INSIDE;
14.   end if;

4.2.2. 点与三角形的距离

$f(1 - t,t)$是一个一元二次方程式，因为$a + c - 2b \succ 0$$f(1 - t,t)$是一个开口向上的抛物线，抛物线的极值点，就是最小值点，对抛物线求导数，得

1.    $a = {\vec e_0} \cdot {\vec e_0},b = {\vec e_0} \cdot {\vec e_1},c = {\vec e_1} \cdot {\vec e_1},d = {\vec e_0} \cdot (B - P),e = - {\vec e_1} \cdot (B - P),f = (B - P) \cdot (B - P)$;
2.    $s = be - cd,t = bd - ae,det = ac - b*b$;
3.    if $s + t \le det$, then
4.           if$s \prec 0$, then
5.                  if $t \prec 0$, then
6.                         //区域4
7.                         if$d \prec 0$, then
8.                                $t = 0$;
9.                                if $- d \ge a$, then
10.                                      $s = 1$;
11.                               else
12.                                      $s = - d/a$;
13.                               end if;
14.                        else
15.                               $s = 0$;
16.                               if$- e \le 0$, then
17.                                      $t = 0$;
18.                               else if$- e \ge c$, then
19.                                      $t = 1$;
20.                               else
21.                                      $t = - e/c$;
22.                               end if;
23.                        end if ;
24.                 else
25.                        //区域3
26.                        $s = 0$;
27.                        if$- e \le 0$, then
28.                               $t = 0$;
29.                        else if$- e \ge c$, then
30.                               $t = 1$;
31.                        else
32.                               $t = - e/c$;
33.                        end if;
34.                 end if;
35.          else
36.                 if $t \prec 0$, then
37.                        //区域5
38.                        $t = 0$;
39.                        if$- d \le 0$, then
40.                               $s = 0$;
41.                        else if $- d \ge a$, then
42.                               $s = 1$;
43.                        else
44.                               $s = - d/a$
45.                        end if;
46.                 else
47.                        //区域0
48.                        $t = t/det$,$s = s/det$;
49.                 else if;
50.          end if;
51.   else
52.          if $s \prec 0$, then
53.                 //区域2
54.                 if $(b + d) - (c + e) \prec 0$, then
55.                        $numer = c + e - b - d,denom = a + c - 2b$;
56.                        if $numer \ge {\rm{de}}nom$, then
57.                               $s = 1$;
58.                        else
59.                               $s = numer/denom$;
60.                        end if;
61.                        $t = 1 - s$;
62.                 else
63.                        $t = 1 - s$;
64.                        if $- e \le 0$, then
65.                               $t = 0$;
66.                        else if $- e \ge c$, then
67.                               $t = 1$;
68.                        else
69.                               $t = - e/c$;
70.                        end if;
71.                 end if;
72.          else if $t \prec 0$, then
73.                 //区域6
74.                 if $(b + e) - (a + d) \prec 0$, then
75.                        $numer = c + e - b - d,denom = a + c - 2b$;
76.                        if $numer \le 0$, then
77.                               $s = 0$
78.                        else if $numer \ge {\rm{de}}nom$, then
79.                               $s = 1$;
80.                        else
81.                               $s = numer/denom$;
82.                        end if;
83.                        $t = 1 - s$;
84.                 else
85.                        $t = 0$;
86.                        if $- d \le 0$, then
87.                               $s = 0$;
88.                        else if $- d \ge a$, then
89.                               $s = 1$
90.                        else
91.                               $s = - d/a$
92.                        end if;
93.                 end if;
94.          else
95.                 //区域1
96.                 $numer = c + e - b - d,denom = a + c - 2b$;
97.                 if $numer \le 0$, then
98.                        $s = 0$;
99.                 else if $numer \ge {\rm{de}}nom$, then
100.                      $s = 1$;
101.               else
102.                      $s = numer/denom$;
103.               end if;
104.               $t = 1 - s$;
105.        end if;
106. end if;
107. return $\sqrt {a{s^2} + 2bst + c{t^2} + 2ds + 2et + f}$;