资源描述：
《凸多边形的闵可夫斯基和分解及其最优估计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第1卷第3期中国科技论文在线SCIENCEPAPERONLINE2006年10月191凸多边形的闵可夫斯基和分解及其最优估计张松海，吴奕（清华大学计算机科学与技术系，北京100084）摘要：本文讨论了闵可夫斯基和的逆问题（称为闵可夫斯基和分解），即将一个凸多边形分解为两个更为简单的凸多边形的问题，首先通过三角分解的方法证明了凸多边形闵可夫斯基和分解的存在性，在此基础上研究了在边个数和面积之和的意义下的最优分解。关键词：闵可夫斯基和分解；凸多边形；三角分解中图分类号：TP391文献标识码：A文章编号：1673－7180(2006)03－0191－60
2、引言P=M+N。而本文给出更强的结论，我们将证明任何闵可夫斯基和是计算几何中的基本运算，对于A凸NN(5≥)边形的非平凡二分解不仅一定存在，而且和B两个集合，闵可夫斯基和⊕定义为A⊕B=｛α一定能找到一种所谓的三角分解，即所得到的分解+b｜α∈A，b∈B｝，两个凸多边形的闵可夫斯基和中有一个元素是三角形的分解。本文还将依次探讨的时间复杂度是Omn()+。它广泛应用在机器人学多边形在边个数最小和面积最小的两种最优情况下[1]中的碰撞检测，数据压缩和CAD等各个方面。闵的闵可夫斯基和分解，并给出相关的算法。可夫斯基和在分析几何的容差问题的时候也起到了1
3、闵可夫斯基和分解的存在性及其三角分解重要的作用，由于使用凸多边形表示误差区域，并定义1：对于一个凸多边形P,定义表示S(P)为且基于最坏情况法对误差进行估计，所以误差区域多边形P的边数和。[2][3]定理1：若一个凸多边形P可以表示为若干个的大小主要是利用闵可夫斯基和进行计算，并且许多几何变换的误差域可以直接通过凸多边形的闵n[4]凸多边形的闵可夫斯基和，即PP=∑i，则可夫和来计算求得的，对于Bézier和B样条曲线i=1误差域的计算，最终也可以归结为各控制顶点误差nSP()≤∑SPi()域的线性组合。然而对于该问题的反问题，即已知i=1。几何变
4、换后允许的最大误差域，来估计输入的胖点证明：因为P的每一条边必然都是由子多边形的误差域的问题还没有得到很好的研究。通过把误中若干条与其方向相同的边叠加而成。由于P有S(P)差域凸多边形做闵可夫斯基和分解成子多边形，可条边，那么，所有的Pi中至少也应该有S(P)条边。以帮助解决这个问题，这也是本文的出发点之一。n本文主要研究闵可夫斯基和的逆过程，即对一即SP()≤∑SPi()，证毕。i=1个给定的凸多边形，将其分解为两个更为简单的凸从定理1的证明中我们可以看出当我们把一个多边形，并研究那些使得分解的两个子多边形的总凸N边形P，分解成两个子多边形P１和
5、P２的时候，边数和或者总面积和最小的最优分解，从而为误差必然有SPSP()(12+）≤N，因此如果一个凸多边形能[5]控制提供理论基础。RolfSchneider证明了在二维平够分解成两个多边形，使得这两个子多边形的边数面上，只有三角形和线段是不可分解的，即所有的之和为原多边形的边数，那么该分解一定是边数意平面凸多边形P，都存在多边形M和N,使得义上的最优分解。基金项目：国家自然科学基金(60273012)。作者简介：张松海（1978-），男，博士研究生，主要研究方向为计算机辅助几何设计、计算机图形学。第1卷第3期192凸多边形的闵可夫斯基和分解及
6、其最优估计2006年10月定义2：如果三个m1，m2，m3向量形成如图1(a)量以外必定至少还有一个向量f，且由于该向量不的位置，亦即m1到m2，m2到m3,m3到m1的夹角都在可能在区域1、3和4，那么它必然在区域2，那么0到180度之间，则称m1，m2，m3为可三角化的，cdf,,为满足要求的三个可三角化的向量。证毕。而图1(b)的三个向量就是不可三角化的，因为m3到有了以上的引理，下面我们来证明定理2，把凸m1的角大于180度。多边形的n条边看作n个首尾相连的向量，显然aaaa+++=...0。由引理，必然存在如图3123nm1形式的三个向量
7、aaa123,,可以三角化。m1a1m2m3mm32αβ(a)(b)χaa23图1向量三角化定理2：任意一个凸nn(6≥)边形都可以分解成图3定理2证明图为一个一个三角形和一个凸m边形的闵可夫斯基如果设和，其中mnnn=−−−3,2,1。aaa321rrrrr====,,,min(,r,r)为证明该定理，我们先证明一个引理。321123sinχβαsinsin，引理a：对于任意n≥6个方向各不相同的二维向量，如果它们的和为零，必定可以从中选出三个由正弦定理有向量，使得它们可三角化。rrraaa++=0123证明：我们用反证法进行证明。取这n个向量r
8、rr123中的两个向量ab,，使得这两个向量的夹角α是所有rrr在（0,π）中的夹角最大的向量对，设ab,的位置如并且aa
