资源描述：
《简单多边形的最小外接矩形算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第13卷第2期哈尔滨理工大学学报Vol13No22008年4月JOURNALHARBINUNIV.SCI.&TECH.Apr.,2008简单多边形的最小外接矩形算法刘玉珍,刘润涛(哈尔滨理工大学应用科学学院,黑龙江哈尔滨150080)摘要:针对钢板在数控切割过程中存在热变形,导致加工工件变形不可用的问题,采用对工件进行矩形切割,从而使热变形达到最小的方法,给出了一种求解简单多边形的最小外接矩形算2法.并在此基础上分析了其具有的复杂度O(k)(其中k是简单多边形的顶点个数).关键词:凹点;自由矢量;绝对矢量;外接矩
2、形;算法中图分类号:TP3016文献标识码:A文章编号:1007-2683(2008)02-0005-03AnAlgorithmforMinmialCircumscribedRectangleofaSmiplePolygonLIUYuzhen,LIURuntao(SchoolofAppliedScience,HarbinUniversityofScienceandTechnolgoy,Harbin150080,China)Abstract:Itwillbedistortforheatingintheprocessofcutting
3、board,sothepartsofcuttingofffromtheboardcouldntbeusedanymore.Wetakerectanglecuttingfromthematerialwhichcontainedtheneededparts,andmakeitcontaintheminimalheartingdistortbydoingtha.tThispapersolvestheproblemhowtocertainaminimalcircumscribedrectangleofarbitrarypolygon.Meanw
4、hileanalgorithmforitispresented,anditstimecomplexities2aregiven,thatis,O(k)(kisthenumberoftheverticesofthepolygon).Keywords:concavepoin;tfreevector;absolutevector;circumscribedrectangle;algorithm本模块在所给材料上重新布局(摆放),使得基本模1引言块互不重叠,这样可以做到裁剪之后的下角料达到最小,从而使得材料的利用率提高.对这类问题已经实际生活
5、中常会碰到这样一类问题,即从给定有了很多的研究.为解决这类问题,文[1,2]给出了形状的布料上裁剪各种形状的图案(称剪下来的这相应算法.些形状为基本模块).对这类问题,如何剪裁更节省工业生产中有些特殊的工艺,必需考虑其工艺材料是首先要考虑的问题.当然在其它的工艺生产要求.如在一类金属钢板上裁剪一些特定形状的基中也会碰到类似的问题.在实际求解过程中仅考虑本模块.由于钢板在数控切割机的切割过程中,其割材料的利用率有时是远远不够的,还要针对特殊材口附近的温度超过金属的弹性变形极限所需温度,料的加工工艺,生产实际中一刀切等各种特殊的工从而导致钢板
6、塑性变形,一直持续到其冷却至原始艺要求,采用合理的剪裁方法.温度后形成了最终变形,即产生了切割热变形.由于考虑到材料的利用率,一种常规的做法是把基数控切割机由计算机控制,工件的外形尺寸要输入收稿日期:2007-03-06基金项目:国家自然科学基金资助项目(10571037);黑龙江省教育厅资助项目(11511087).作者简介:刘玉珍(1980-),女,哈尔滨理工大学硕士研究生.6哈尔滨理工大学学报第13卷程序中,所在切割位置的坐标定位不会因钢板变形删去简单多边形的所有凹点,直到多边形变成而相应
7、改变.如果直接裁剪所需模块,必然会因切割凸多边形(设凸多边形的边数为n),并把凸多边形热变形产生基本模块的变形,导致切割下来的基本的各顶点按逆时针排列,同时把各边所表示的自由模块不满足实际需要.矢量都移到原点,得到一组有向绝对矢量.显然,该当然,产生热变形的因素有很多种,文[3]介绍组有向绝对矢量的对应边分别是凸多边形的各边.了几种比较常见的因素.如编制程序时起火点的选因为凸多边形的各顶点按逆时针排序,所以得到的择,切割方向,切割顺序,切割引入方式的选择等.以这组有向绝对矢量在坐标系中也按逆时针排列.并上都是切割工艺要考虑的问题.这里只考
8、虑其中一记下按逆时针排列的该组有向绝对矢量的未端点集种,即:改变切割方向来降低加工过程中的热变形,也合Q={p∀1,p∀2,!,p∀n}.就是对基本模块进行最小矩形切割.这种切割方法,为描述方
