周 鑫， 赖晓阳， 孟祥群， 王 堃， 唐厚君

(1. 上海交通大学 电气工程系，上海 200240； 2. 上海方菱计算机软件有限公司，上海 200241)

临界多边形这一概念由Adamowicz等[1]提出，广泛应用于CAD、图像图形学等领域.临界多边形最重要的应用为排料问题[2]的相交校验.排料问题可概括为如何在有限的空间内装下最多指定形状的物体[3].排料问题需要测试待排料位置中能否放下指定形状的物体，此时需要判断待排料工件是否与已排料的工件相交，这个过程称为相交校验.临界多边形是排料问题相交校验计算的重要工具.研究临界多边形对工业生产具有重要的学术价值和实用价值.

国内外学者对临界多边形进行了许多研究，提出了多种临界多边形的计算方法[4-5].这些算法包括蚁群算法[6]、元启发算法[7]、移动碰撞法[8]、模拟退火算法[9]、遗传算法[10]、重力临界多边形算法[11]及轨迹线算法[12-13].

以上算法有一个共同的局限：算法仅能对多边形的排样进行求解.实际工业环境中，待排样的物体并非严格的多边形.一种方法是用多边形对其轮廓进行拟合，这样在精度上势必有所损失.一种基于移动碰撞法的临界多边形算法[14]可以计算由包含圆弧和线段的临界多边形，解决了精度损失问题，但其计算速度有待提高.

本文在分析了临界多边形的多种计算方法后，研究了计算速度较快的轨迹线算法，并将其加以拓展，使其能够计算包含圆弧和线段的临界多边形，解决了精度损失问题，同时……