# 7.4. 最小面积包围矩形

## 7.4. 最小面积包围矩形

$\left\{ \begin{array}{l}{l_0} = {d_{i,k}} \cdot cos{\alpha _k}\\{l_1} = {d_{j,l}} \cdot cos{\alpha _l}\end{array} \right.$

$${A_{CC}} = {l_0}'{l_1}’\left\{ {\begin{array}{*{20}{c}}{{l_0}’ = {d_{i,k}}\cos ({\alpha _k} – \delta )}\\{{l_1}’ = {d_{j,l}}\cos ({\alpha _l} + \delta )}\end{array}} \right.$$

${A_C} = {l_0}”{l_1}”\left\{ {\begin{array}{*{20}{c}}{{l_0}” = {d_{i,k}}\cos ({\alpha _k} + \delta )}\\{{l_1}” = {d_{j,l}}\cos ({\alpha _l} – \delta )}\end{array}} \right.$

$\frac{{{A_{CC}}}}{A} = {\cos ^2}\delta + (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta$

$\frac{{{A_C}}}{A} = {\cos ^2}\delta – (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta$

$\begin{array}{l}{\rm{ }}{\cos ^2}\delta + (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta \le 1\\ \Leftrightarrow – (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta \le {\cos ^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 2({\cos ^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta ) – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 2(1 – si{n^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta ) – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 1 – 2(1 + \tan {\alpha _k}\tan {\alpha _l}){\sin ^2}\delta \end{array}$

1.    $${{i}_{\min }}=0$$;
2.    $$\vec{d}=\left( {{p}_{imin+1}}-{{p}_{i\min }} \right),\vec{d}=\vec{d}/\left\| {\vec{d}} \right\|,\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})$$;
3.    $${{n}_{\max }}=-\infty ,{{d}_{\min }}=+\infty ,{{d}_{\max }}=-\infty$$;
4.    $$area=+\infty$$;
5.    for( i = 0 ; i < n ; ++i )         //求出初始边水平方向上投影最小的点jmin，最大的点jmax
6.           $$\vec{t}={{p}_{i}}-{{p}_{a}}$$;                     //垂直方向上投影最大的点imax
7.           $$s=\vec{d}\cdot \vec{t}$$;
8.           if $$s\prec {{d}_{\min }}$$, then
9.                  $${{d}_{\min }}=s,{{j}_{min}}=i$$;
10.          end if;
11.          if $$s\succ {{d}_{\max }}$$, then
12.                 $${{d}_{\max }}=s,{{j}_{max}}=i$$;
13.          end if;
14.          $$s=\vec{n}\cdot \vec{t}$$;
15.          if $$s\succ {{n}_{\max }}$$, then
16.                 $${{n}_{\max }}=s,{{i}_{max}}=i$$;
17.          end if;
18.   end for;
19.   for ( i=0 ; i<n ; i++ )
20.          计算边与支撑线的夹角$${{\theta }_{{{i}_{\min }}+1}},{{\theta }_{{{i}_{\max }}}},{{\theta }_{{{j}_{\min }}}},{{\theta }_{{{j}_{\max }}}}$$;
21.          最小夹角的索引值为k;
22.          if k==0, then
23.                 return;
24.          end if;
25.          更新$${{i}_{\min }},{{i}_{\max }},{{j}_{\min }},{{j}_{\max }}$$四个索引值;
26.          $$\vec{d}=\left( {{p}_{{{i}_{min}}+1}}-{{p}_{{{i}_{\min }}}} \right),\vec{d}=\vec{d}/\left\| {\vec{d}} \right\|,\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})$$;
27.          $${{l}_{0}}=\vec{d}\cdot \left( {{p}_{{{j}_{\max }}}}-{{p}_{{{j}_{\min }}}} \right),{{l}_{1}}=\vec{n}\cdot \left( {{p}_{{{i}_{\max }}}}-{{p}_{{{i}_{\min }}}} \right)$$;
28.          $$area=\min \{{{l}_{0}}\cdot {{l}_{1}},area\}$$;
29.   end for;

$\left\{ {\begin{array}{*{20}{l}}{{i_{\min }}’ = {i_{\min }} + 1,}&{{i_{\max }}’ = {i_{\max }},}&{{j_{\min }}’ = {j_{\min }},}&{{j_{\max }}’ = {j_{\max }},}&{if,k = {i_{\min }} + 1;}\\{{i_{\min }}’ = {i_{\max }},}&{{i_{\max }}’ = {i_{\min }} + 1,}&{{j_{\min }}’ = {j_{\max }},}&{{j_{\max }}’ = {j_{\min }},}&{if,k = {i_{\max }};}\\{{i_{\min }}’ = {j_{\min }},}&{{i_{\max }}’ = {j_{\max }},}&{{j_{\min }}’ = {i_{\min }} + 1,}&{{j_{\max }}’ = {i_{\max }},}&{if,k = {j_{\min }};}\\{{i_{\min }}’ = {j_{\max }},}&{{i_{\max }}’ = {j_{\min }},}&{{j_{\min }}’ = {i_{\max }},}&{{j_{\max }}’ = {i_{\min }} + 1,}&{if,k = {j_{\max }};}\end{array}} \right.$