浏览量:269

7.5. 最小周长包围矩形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

7.5. 最小周长包围矩形

问题描述:给定一组点集\(\{ {p_0},{p_1}, \cdots ,{p_{n – 1}}\} \),求一个矩形,满足条件:(1)点集在矩形内部;(2)矩形的周长最小。

很多情况下,多边形的包围矩形的面积减小,对应的周长也会减小,但对于所有的多边形,这个规律是否还成立呢?这里,用一个具体的实例证明:这个规律是不成立的。

2015-3-23 21-41-56

图7.12 多边形和包围矩形,(a)多边形,(b)最小面积包围矩形,(c)最小周长包围矩形

如图7.12所示,图(a)是多边形的最小面积包围矩形,图(c)是最小周长包围矩形,设图(b)和图(c)的面积和周长分别表示为\({{A}_{A}},{{P}_{A}}\)和\({{A}_{P}},{{P}_{P}}\),多边形的边a和b满足约束条件\(\frac{a}{2}\prec b\prec \frac{a}{\sqrt{2}}\),易知\(c=\frac{b}{\sqrt{2}},d=\frac{a}{\sqrt{2}}\),因此可以得到等式

\[\left\{ {\begin{array}{*{20}{l}}{{A_A} = \sqrt 2 ab + 2{b^2}}\\{{P_A} = 2a + 4\sqrt 2 b}\\{{A_P} = \frac{{{a^2}}}{2} + \sqrt 2 ab + {b^2}}\\{{P_P} = 2\sqrt 2 a + 4b}\end{array}} \right.\]

因此,可以得到不等式

\[\left\{ {\begin{array}{*{20}{l}}{{A_P} – {A_A} = \frac{{{a^2}}}{2} – {b^2} \succ 0}\\{{P_A} – {P_P} = 4(\sqrt 2 – 1)(b – \frac{a}{2}) \succ 0}\end{array}} \right.\]

显然,面积最小的包围矩形,不一定周长也最小,两者并无必然的关系。但是,最小周长的矩形与最小面积的矩形有一个相似的性质,即最小周长的矩形至少有一条边与凸多边形重合。

定理7.5.   最小周长的包围矩形的一条边与凸多边形的一条边是重合的。

证明用反证法来证明,给定一个凸多边形\({\rm P}\),若包围矩形的任意一条边与多边形都不重合,它仍可能是最小面积矩形。令矩形与多边形相切的四个顶点分别是\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\),如图1.3所示。令包围矩形的周长是\(D\),则有\(D=2({{l}_{0}}+{{l}_{1}})\)。进一步,令\({{p}_{i}}\)和\({{p}_{k}}\)的距离与\({{p}_{j}}\]和\({{p}_{l}}\)的距离分别用\({{d}_{i,k}},{{d}_{j,l}}\)表示,则有

\[\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.,0 \le {\alpha _k} \prec \frac{\pi }{2}\]

将矩形沿着逆时针方向旋转\(\eta \)角(\(\eta \)是正值,保证\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\)仍是新的矩形的相切点),边长\({{l}_{0}},{{l}_{1}}\)会发生变化,这可以分成两种情况:(1)同时变长或变短;(2)一条边变长,另一条变短。

情况(1),若沿着逆时针方向旋转\(\eta \)角,得到新的边长\({{l}_{0}}’,{{l}_{1}}’\](\({{l}_{0}}’\prec {{l}_{0}},{{l}_{1}}’\prec {{l}_{1}}\))缩短,则面积\(D’=2({{l}_{0}}’+{{l}_{1}}’)\prec 2({{l}_{0}}+{{l}_{1}})=D\),能得到周长更小的矩形;相反,若新边的长度都增加了,则将矩形沿顺时针方向旋转一定的角度,得到的新边一定变短,同样能得到周长更小的矩形。

情况(2),矩形的旋转,导致一条边变长,另一条变短,设矩形沿逆时针方向旋转\(\delta \) (\(\delta \)是正值),\({{l}_{0}}\)变长,\({{l}_{1}}\)变短,有

\[{D_{CC}} = 2({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.\]

则矩形沿顺时针方向旋转\(\delta \) (\(\delta \)是正值),\({{l}_{0}}\)变短,\({{l}_{1}}\)变长,有

\[{D_C} = 2({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.\]

展开\({D_{CC}}\)可以得到

\[{D_{CC}} = 2({l_0} + {l_1})\cos \delta + 2({l_0}\tan {\alpha _k} – {l_1}\tan {\alpha _l})\sin \delta \]

令\(C = 2({l_0}\tan {\alpha _k} – {l_1}\tan {\alpha _l})\),则有

\[{D_{CC}} = D\cos \delta + C\sin \delta \]

同理,可得

\[{D_C} = D\cos \delta – C\sin \delta \]

若\(\frac{{{D_C}}}{D} \prec 1\),则将矩形沿顺时针方向旋转一定角度,得到更小的周长的矩形。相反,若\(\frac{{{D_C}}}{D} \ge 1\),则可以得到

\[\begin{array}{l}\frac{{D\cos \delta – C\sin \delta }}{D} \ge 1\\ \Leftrightarrow \frac{C}{D}\sin \delta \le \cos \delta – 1\\ \Leftrightarrow \frac{{{D_{CC}}}}{D} \le 2\cos \delta – 1 \prec 1\end{array}\]

此时,则将矩形沿逆时针方向旋转一定角度,得到更小的周长的矩形。

综上两种情况,我们可以最小周长的包围矩形的一条边与凸多边形的一条边是重合的。

 

求凸多边形的最小周长包围矩形与最小面积包围矩形的方法类似,不同的是在算法第4、28步,把面积的计算改为周长的计算公式即可,算法伪码不再赘述。

spacer

Leave a reply