排料问题应用范围非常广泛,如服装行业、皮革行业、机械行业。提高板材利用率必然会降低企业的生产成本,会给企业带来经济效益,所以,排料问题的研究具有重要的经济价值。二维不规则排料问题具有很高的复杂性,属于NP完全问题,所以,排料问题的研究具有重要的理论价值。 自动排料算法都是针对多边形零件来研究的,然而在实际生产中,零件多数是由圆弧和圆组成的,不可以直接进行自动排料计算。为了可以计算,本文提出了自动提取零件数据的算法和求解逼近多边形的方法。 在自动排料计算的过程中,如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。为了减少多边形之间重叠性判断的计算量,在本文中采用了临界多边形算法,并对现有的临界多边形算法提出了改进。 此外,本文设计了自动排料算法中其它一些相关的图形学算法,如凸包算法和合成多边形算法。当计算完临界多边形后,在临界多边形的多个顶点都可以排放零件。为了找到排放零件的最优位置,利用凸包算法来确定。在临界多边形的每个顶点计算利用率,最终确定放置零件的最优位置。临界多边形计算是针对两个多边形的运算,在排料过程中,必须保证板材上只有一个零件多边形才可以与下一个待排零件多边形运算,所以需要将两个多边形合成为一个多边形。 基于上述算法的研究,设计了二维不规则零件自动排料系统,该系统具有友好的界面。系统可以对AutoCAD零件图纸直接处理,通过对板材参数的设定和零件的选择,可以自动生成零件的排料图。 本课题的研究不仅对本领域,而且对其它领域也具有启发意义。