# 4.2. 点与三角形

## 4.2. 点与三角形

#### 4.2.1. 点与三角形的关系

1. 二维空间

$\left\{ \begin{array}{l}{d_0} = \left( {{V_1} – {V_0}} \right) \times \left( {P – {V_0}} \right)\\{d_1} = \left( {{V_2} – {V_1}} \right) \times \left( {P – {V_1}} \right)\\{d_2} = \left( {{V_0} – {V_2}} \right) \times \left( {P – {V_2}} \right)\end{array} \right. \tag{4.4}$

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. 三维空间

$f\left( {\overline {{V_i}{V_j}} ,Q,P} \right) = \left[ {({V_j} – {V_i}) \times (Q – {V_i})} \right] \cdot \left[ {({V_j} – {V_i}) \times (P – {V_i})} \right] \tag{4.5}$

$\left\{ \begin{array}{l}{d_0} = f\left( {\overline {{V_0}{V_1}} ,{V_2},P} \right)\\{d_1} = f\left( {\overline {{V_1}{V_2}} ,{V_0},P} \right)\\{d_2} = f\left( {\overline {{V_2}{V_0}} ,{V_1},P} \right)\end{array} \right. \tag{4.6}$

$\left\{ \begin{array}{l}{d_0} = \vec n \cdot \left[ {\left( {{V_1} – {V_0}} \right) \times \left( {P – {V_0}} \right)} \right]\\{d_1} = \vec n \cdot \left[ {\left( {{V_2} – {V_1}} \right) \times \left( {P – {V_1}} \right)} \right]\\{d_2} = \vec n \cdot \left[ {\left( {{V_0} – {V_2}} \right) \times \left( {P – {V_2}} \right)} \right]\end{array} \right. \tag{4.7}$

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. 点与三角形的距离

$T(s,t) = B + s{\vec e_0} + t{\vec e_1} \tag{4.8}$

${\mathop{\rm dist}\nolimits} (P,\Delta ) = \left\| {T(s,t) – P} \right\| \tag{4.9}$

$f(s,t) = {\left\| {T(s,t) – P} \right\|^2} = a{s^2} + 2bst + c{t^2} + 2ds + 2et + f \tag{4.10}$

$\left\{ \begin{array}{l}{f_s}'(s,t) = \frac{{\partial f(s,t)}}{{\partial s}} = 2(as + bt + d) = 0\\{f_t}'(s,t) = \frac{{\partial f(s,t)}}{{\partial t}} = 2(ct + bs + e) = 0\end{array} \right. \tag{4.11}$

$\left\{ \begin{array}{l}{s_c} = \frac{{be – cd}}{{ac – {b^2}}}\\{t_c} = \frac{{bd – ae}}{{ac – {b^2}}}\end{array} \right. \tag{4.12}$

$f(1 – t,t) = (a + c – 2b){t^2} + 2(b + e – d – a)t + (a + f) \tag{4.13}$

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

$f'(1 – t,t) = 2\left[ {(a + c – 2b)t – (a + d – b – e)} \right] = 0 \tag{4.14}$

$t = \frac{{a + d – b – e}}{{a + c – 2b}} \tag{4.16}$

$s = \frac{{c + e – b – d}}{{a + c – 2b}} \tag{4.17}$

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}$$;