二维不规则零件排样：临界多边形法的突破与优化算法

"临界多边形法在二维不规则零件排样中的研究与实现"是一篇深入探讨二维不规则零件优化排样的硕士论文，由白瑞斌撰写，指导教师为魏生民教授，专业领域为航空宇航制造工程。二维零件排样技术在制造、服装、皮革和建筑等行业中具有广泛应用，但其作为典型的完全问题，计算复杂度极高，是自动化领域的研究热点。 本文主要贡献在于解决二维不规则零件排样的关键算法。首先，针对临界多边形法在处理凹多边形时的困难，作者提出了多边形凸化分割策略，通过将凹多边形转化为凸多边形来简化问题，从而克服了长期存在的技术难题。 论文进一步研究了多边形的多种分割方法，包括三角形化、无点分割和有节点分割，以及角平分线和延长线分割法，这些方法为多边形的合并提供了不同的途径。基于平面图的算法，如排列合并、增量合并以及与特定数据结构相关的算法，也被详细探讨。 排样过程中，论文还涉及曲线离散化、多边形合成和面积计算等核心算法，这些都是实现高效排样的基础步骤。为了优化排样序列，作者采用了遗传算法，以提高材料利用率为目标，通过计算几何算法库开发出优化的零件调度策略。 值得一提的是，该论文所提出的临界多边形算法不仅为二维零件排样的研究提供了实用工具，还在计算机辅助装配和机器人路径规划等领域展示了潜在的应用价值。整个研究工作是在特定的计算平台（具体未提及）上完成的，其成果对推进相关行业的自动化和技术进步具有重要意义。