Filling问题的最优化原理及其求解方法研究

As a new type of research area，the filling problem is much more difficult to study and still at the exploratory stage, for the complexity of the shape together with the unequal disks overlapping each other. From a different perspective, this project explores the optimal theories and solving methods of the filling problem based on the medial axis transform and Mathematical Programming. Starting from the distance and area functions, the mathematical programming method is employed to construct the programming models. Based on the optimal conditions, the internal connections between the medial axis and the filling problem, and some disciplinary conclusions are derived. Moreover, new academic ideas are developed for further research. On the basis of theoretical research, the generic solving strategies and methods for two dimensional shapes are studied. Finally, as a further goal, this project discusses the applications in the NC machining of 2.5D pockets, the step machining method for the 2.5D pockets is developed. The expected research results contribute not only to solving the filling problem and understanding the optimal theories of such problems ,but also to facilitating the interaction of different disciplines.

Filling 问题作为一类新型的填充，由于填充圆相互的交织覆盖，以及填充圆半径的无规律变化，所涉及的内容复杂，研究的难度较大，研究历史短，亟待深入研究的问题多等等。本项目拟基于中轴变换与数学规划两个平台，研究Filling 问题的最优化原理及其求解方法。在分析距离函数、面积函数特性的解析基础上，建立Filling 问题的数学规划模型；给出模型的最优条件、论证其与中轴变换的内在联系、提炼出相关规律性认识，为Filling问题的研究注入新鲜的学术思想。在深化理论认识的基础上，开展算法研究，发展出有效的适合任意自由曲线边界Filling问题的求解策略与方法。最后，探讨Filling问题在2.5D型腔零件数控加工中的应用，发展出2.5D型腔多刀点位式的数控加工方案。预期本项目的研究成果不仅对解决Filling问题有重要价值，也对回答图形学中的最优化问题、促进学科之间的交叉融合具有重要指导意义。

Filling 问题是介于Covering和packing之间的一类新型填充问题，它允许填充圆相互的交织覆盖，以及填充圆半径的无规律变化，但却不能超出域的边界。本项目从引入两个特殊函数着手，以距离函数为不等式为约束，以面积函数最大为目标，构建出Filling问题的最优化模型为其理论研究与求解奠定了理论基础。依据K-T条件推导出的Filling问题的最优条件，据此证明了Filling问题同中轴变换之间的基本关系，以及特征点凸体包容准则。通过直接对等梯度条件式的求解发展出了凸多边Filling问题的解算方法，验证了上述理论与方法的正确性和有效性。