文摘
研究三角形包装问题具有重要的理论意义,具有广阔的应用前景在材料加工、网络资源优化,等等。一般来说,三角形的取向应该是有限的,因为三角形包装问题是np难和连续属性。例如,不允许多边形旋转;然后,可以通过优化方法得到近似解。本文研究了三角形包装问题,一种新的方法。角地区等概念,corner-occupying行动,corner-occupying战略,edge-conjoining策略提出了本文。此外,一个edge-conjoining和corner-occupying算法设计,得到一个近似解。证明了该算法是高效的,和时间复杂度分析和模拟实验结果。
1。介绍
解决np难问题始终是对计算机科学和技术瓶颈的任务。然而,近年来,许多研究结果表明,没有一个完整的,准确、快速解决这类问题的算法。人们倾向于专注于寻找一个快速、实用的近似算法;见,例如,(1]。
三角形包装问题是给定一个已知的长度和宽度矩形空集装箱和N确切的大小和形状的三角形;即一个三角形的三面是已知的,问题是N三角形是否可以放在矩形容器。如果我们可以,然后给每个三角形的矩形的位置和姿态。如果没有,给消极的回答这个问题。由于三角形平面上可以不断转换和旋转,有无限数量的位置不利于解决问题。所以位置应该总是有限的。的策略2)只允许一个多边形旋转,但是不能翻译,翻译多边形包装问题为np完全问题。
一个多边形的三角包装问题是一个特例包装问题,但仍然是np难。现在,没有一个快速和完整的解决算法和启发式方法仍然是一个普通的方法;见,例如,(3- - - - - -7)和引用。摘要edge-conjoining和corner-occupying算法是一个快速和近似方法设计基于角region-filling策略。本文对多边形包装有特殊意义的问题,网络资源优化,等等,因为它是一个特例的多边形包装问题;见,例如,(8- - - - - -11]。
节2的基本概念,如角地区。角地区和corner-occupying行动的分类进行了讨论,和部分的物理意义进行了分析3。节4,两个启发式策略和一个近似算法求解三角形包装提出了问题。最后,还讨论了算法的复杂性和一些模拟结果的例子。
2。角地区的形成
定义1。三角形在同一个平面相交的,如果两个三角形的重叠面积大于零。否则这两个三角形non-intersectant。
定义2。两个non-intersectant三角形在同一个平面上,如果两条边之间至少存在一个十字路口,从每个三角形,那么这两个三角形切,如图1。
(一)
(b)
定义3。分别从两个切三角形两条边,如果满足以下条件:(1)存在只有一个交点(O)的两个三角形;(2)一个角形成的两条边是一个积极的角度和不足;(3)的角,没有其他边缘的两个三角形除外;然后这个角据说两个切角地区的三角形。它的大小叫做角的角地区。重叠的部分初始角的边缘的两个三角形是初始角边缘地区;同样的,重叠的部分终端边缘的角的两个三角形是角地区的终端优势;的十字路口据说是角的顶点。如图2,ABC是切线DEF O (A),生化需氧量是一个角度的地区ABC和能延期的;的角度大小区域角用BOD;OB和OD的初始边缘和终端边缘角地区,分别;啊,据说是角的顶点。
判断是否有由两个切三角形一个角地区,它只是取出与常见的从每个三角形顶点和两条边判断是否两个三角形形成一个积极的角度小于和确认没有其他边缘两个三角形的角。计算过程可以实现根据三角形的顶点坐标。
角地区的定义,切三角形的两条边是否可以形成角地区无关的大小和形状的三角形角地区。
3所示。一个角的分类区域和Corner-Occupying行动
根据两个三角形的不同位置,两个切三角形可能形成零,一个或两个角区域,如图3和4(一)- - - - - -4 (c)和5(一个)- - - - - -5 (d),分别。
(一)
(b)
(c)
(一)
(b)
(c)
(d)
这些角区域的材料加工过程中产生的残渣。如果我们利用这些碎片,然后利用材料的比例可以增加实际生产经验的基础上。通过实践充分说明增加材料的比例,然后过滤容器内的位置应该是稳定的。平面图形是否稳定取决于可转让的自由度和可旋转的自由度。三角形,可旋转的自由度是指一个顺时针或逆时针旋转一个三角形的起源在其顶点之一,这里三角形仍在矩形容器旋转后,与其他三角形和三角形不能冲突;即之间没有重叠部分旋转三角形和其它三角形,这意味着你可以自由旋转三角形;同样,可翻译的自由度是指翻译一个三角形的两个相反的方向的直线的一个三角形的一边是三角形的重心坐标作为初始点,当三角形仍在矩形容器后翻译的操纵,并与其他三角形三角形不能冲突周围;即之间没有重叠的部分翻译三角和其他三角形,这意味着你可以自由翻译三角形。
如果一个三角形的重心坐标作为初始点可以自由转换以及任何直线三角形的优势所在,则被认为是即将到来的三角形。显然,这种三角形的位置不稳定,比如三角形1所示图6。
如果一个三角形可以自由翻译只沿一直线或旋转在某个顶点,自由这种立场是pushable swingable,也不稳定,比如三角形如图2和36。
一般来说,一个三角形的位置不能自由翻译只沿一直线或旋转在某个顶点自由是稳定的,如三角形4、5、6和7所示图6。
如果一个三角形的边与另一个三角形的边1是结合2,即重叠部分的长度大于零,三角形1只能翻译的边缘三角形2,则pushable三角形的位置1。把三角形1的边缘三角形2,如果三角形1只是切线第三个三角形,三角形的边1仍然是结合2三角形的边,然后三角形的位置1是稳定的。
一般来说,与三角形4和7的位置相比,三角形的5和6的位置可以很容易地划分空间,这是不利于利用空间。它是合理的假设三角形4和7的位置比三角形5和6。出于这个原因,我们有以下定义。
定义4。Corner-occupying行动:如果一个三角形的一个优势是连体初始或终端边缘角地区,也就是说,重叠部分的长度大于零,另一个三角形的边是连体的终端或最初的边缘区域,然后把三角形的角地区的过程称为Corner-occupying行动。,对面的第三个优势是称为切入角度。
能找到corner-occupying行动:推动边缘与初始或终端结合边缘三角形区域的三角形外矩形容器成矩形容器,如果不能把更多的三角形(当三角形切到终端或初始边缘),三角形的边仍是连体的初始或终端边缘角区域,然后把三角形的位置的过程叫做corner-occupying行动。因此,把一个三角形的问题变成一个角地区由两个切三角形可以转换为三角形的边缘位置关系问题和线段。因此,搜索空间可以在有限数量的点从一个连续的欧几里得空间。
定义5。的联合学位corner-occupying行动:如果一个边缘(长度)一个三角形和一个边缘(长度)的一个角地区联合,让重叠部分的长度,然后corner-occupying行动的联合学位。特别,如果另一个边(长度三角形的),另一个边缘(长度天使的地区联合,重叠部分的长度,然后corner-occupying行动的联合学位)。
定义6。角的两条边地区,如果一个边缘之间的角度结合一个三角形和另一个边缘的切线三角形和角质角的大小,然后corner-occupying行动的一致性程度。
联合学位和整合程度是用来测量灌装三角形之间的邻近度和填充三角形将被放置的位置。联合学位,越大corner-occupying行动的一致性程度,邻近的程度越高。
4所示。一个算法Edge-Conjoining Corner-Occupying
如图7,可以视为一个平面矩形容器图被四个三角形。
(一)
(b)
(c)
(d)
定义7。模式:模式指的是一种有序偶,在那里是四个三角形的集合形成一些三角形的矩形容器放入(集合中的每个元素用三角形的三个顶点坐标),是三角形的矩形容器的集合(集合中的每个元素用三角形的三条边),然后呢是一组角地区形成的三角形。
在第一时刻,只包含四个三角形形成矩形容器,所有三角形的集合是放在矩形容器,然后呢是一组四个角地区由四个三角形此刻,然后模式被称为初始模式,这是用。从最初的模式,将形成的模式th三角形了到矩形容器th模式,这是用。在th模式,如果,那么它被称为终端模式。
在模式在终端模式,让一个三角形执行corner-occupying行动,如果三角形仍在矩形容器,不与其他三角形相交,那么corner-occupying行动被称为合理corner-occupying行动。
Corner-Occupying策略。两个合理corner-occupying行动和,让两者的整合程度和,分别。如果,然后据说有更高的优先级比吗。
Edge-Conjoining策略。两个合理corner-occupying行动和,让双方的联合学位和,分别。如果,然后据说有更高的优先级比吗。
根据corner-occupying edge-conjoining战略和策略,启发式算法求解三角形以下包装问题。
考虑到初始模式,在那里是四个三角形的集合形成矩形容器,所有三角形的集合是放在矩形容器,然后呢是一组四个角地区由四个三角形。角地区和合理安排corner-occupying行动以时间顺序。
步骤1。集,当前的模式是。
步骤2。如果,据报道,所有三角形放在矩形容器,并停止;如果没有合理的corner-occupying行动来执行,然后算法的失败报告,去一步3;如果而在,存在一个合理corner-occupying行动执行,然后去一步3。
步骤3。选择一个合理的corner-occupying行动与最高优先级根据corner-occupying策略执行。如果存在只有一个合理的根据corner-occupying corner-occupying行动策略,然后根据这个corner-occupying填补三角形行动,去一步5;如果不是,选择一个合理的corner-occupying动作与最高优先级执行根据conjoining-occupying策略,去一步4。
步骤4。选择一个合理的corner-occupying行动与最高优先级根据conjoining-occupying策略执行。如果存在只有一个合理的根据conjoining-occupying corner-occupying行动策略,然后根据这个corner-occupying填补三角形行动;如果不是,填补三角形根据第一corner-occupying行动。
第5步。添加三个三角形的垂直坐标执行corner-occupying行动和删除三角形的三条边表演的corner-occupying行动。改变来,来,来组角地区形成的三角形。切换到一个新的模式,去一步2。
5。算法的时间复杂度分析Edge-Conjoining Corner-Occupying
对于最初的模式如果有m三角形和三角形的没有共性,找出合理的corner-occupying行动与最高优先级计算的时间单位(步骤的数量计算)花在执行行动。
首先,计算时间复杂度的m三角形形成的角地区。
鉴于两个三角形,从他们每个人拿出一个边缘,如果需要时间单位来判断两条边是否可以形成一个角度。然后,它将最多时间单位来找出所有的角地区由两个三角形。
还需要时间单位来找出所有的角地区由m三角形。通过角的定义区域,两个三角形可以形成两个角地区最多。因此,有角地区最多。事实上,很少有机会,每个三角形,三角形相切,所有的三角形都是在相同的矩形容器。一般来说,总由m三角形角地区远远不到。这是该算法的高速的根本原因。
其次,计算的时间复杂度corner-occupying行动的三角形的角地区。
如果需要时间单位把一个三角形的角区域以及一个连体的三角形的边与角的边缘地区,和时间单位最多把一个三角形给定角地区22个不同corner-occupying行为最多,那么它将时间单位最多把一个三角形所有的角地区,时间单位最多完成corner-occupying行动的三角形的所有的角地区。
第三,计算判断是否每个corner-occupying操作的时间复杂度是一个合理的corner-occupying行动。
如果需要时间单位来判断是否相交,两个三角形时间单位来判断三角形是否在矩形容器,那么它将时间单位来找出所有合理corner-occupying行动。
最后,计算发现corner-occupying操作的时间复杂度与最高优先级的合理corner-occupying行动。
如果需要时间单位来比较两个corner-occupying行动的优先级,那么它将最多时间单位来找出一个合理的corner-occupying行动最高的优先级。从上面的分析中,所花费的时间倒三角形对应corner-occupying行动的最高优先级最多是
这时,一个三角形一直放在矩形容器,然后切换到一个新的模式。还需要最多时间单位为每个步骤。换句话说,
同样的, 在哪里。从最初的模式,它将达到算法结束步骤。由上面的分析中,该算法的时间复杂度分析
在最初的模式,,是三角形的数量放在矩形容器。所以
也就是说,该算法的时间复杂度。如果没有合理的corner-occupying行动执行,然后停止。因此,总计算时间的数量级并不多。
6。一些说明性的例子
在本节中,我们已经开发出一种程序来验证该算法的有效性,实验数据是包括在表中1。这个项目是由使用Visual c++ 6.0开发的,在计算机上实现的奔腾2.8 GHz处理器,512 MB的RAM。
输入如下:矩形容器的长度和宽度(0.1错误),每个三角形的边长度放入(误差是0.000001)。
输出如下:利用(误差是0.1%),计算时间(误差为0.01秒),把三角形到矩形序列容器,把三角形的顶点坐标,计算误差是0.000001;显示单位是像素。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
这部分工作是支持关键工程技术部门下的中国河南省拨款122102210042,河南省的科技头脑风暴项目中国在格兰特12 b520054和中国863项目资助2011 aa01a201。