有限包络圆族的快速生成方法及其在二维布局优化中的应用  

Efficient Construction Algorithms of Finite Circles and Their Applications to 2D Layout Optimization

作　　者：张桥[1] 张卫红[1] 

机构地区：[1]西北工业大学现代设计集成制造技术教育部重点实验室,西安710072

出　　处：《计算机辅助设计与图形学学报》2009年第5期617-625,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(10676028);西安-应用材料创新基金(XA-AM-200705)

摘　　要：为了有效地实施有限包络圆族方法(FCM),大幅度减少包络圆数目,达到一圆多用、圆尽其用的目的,提出3种FCM自动化建模方法:二分法、三步划分法和带间隙的改进三步划分法.二分法利用组件各边长度和设置的容差大小得到该边的候选包络圆,若该圆不满足组件所有边的容差要求,则将该边不断地对分,直至所得到的包络圆满足各边的容差要求;三步划分法和带间隙的改进三步划分法则以组件区域为划分对象,依次对组件多边形凸顶角、凸扇形区和多边形各边剩余线段划分包络圆,且带间隙的改进三步划分法则允许包络圆在组件边界上以适当的间隙分布.最后通过算例表明,三步划分法和带间隙的改进三步划分法能用尽量少的包络圆逼近二维组件,在组件装填布局优化设计中明显提高了组件装填布局优化效率.In order to explore the efficiency of finite circle method （FCM） and to reduce the circle number as much as possible, three new methods, i. e. the bisection algorithm, the three-step algorithm and the improved three-step algorithm with gap are proposed for the automatic generation of circles in this paper. The first one is to generate the circle for each borderline segment of the component by considering the segment length and the prescribed tolerance value. If this is not the case, the borderline segment will be equally divided into halves until the obtained circle satisfies the tolerance value over the whole borderlines of the component. The basic idea of the last two algorithms aims at covering the domain occupied by the component as much as possible. The circle generation is carried out sequentially from salient angle to the sector formed by the salient angle till the uncovered borderline segments of the component. Particularly, the three-step algorithm with gap allows that the generated circles are distributed with gap along the component contour. Lots of numerical examples are finally tested. It is shown that the three-step algorithm and the improved three-step algorithm with gap can approximate the component with fewer circles. Thus, they can improve considerably the efficiency of multi-components packing and layout optimization.

关 键 词：有限包络圆族方法 干涉判断 组件装填布局优化设计 

分 类 号：TB113[理学—数学]