二维形状的金字塔分解  

Pyramidal Decomposition of 2D Shapes

作　　者：刘邦权[1,2] 陈双敏[1] 辛士庆 刘箴[1] 孟赟[2] 孙德超[4] 屠长河[3] Liu Bangquan;Chen Shuangmin;Xin Shiqing;Liu Zhen;Meng Yun;Sun Dechao;Tu Changhe(Faculty of Electrical Engineering and Computer Science,Ningbo University Ningbo 315211;College of Information Engineering,Ningbo Dahongying University Ningbo 315175;School of Computer Science and Technology;Shandong University Ji ＇nan 25010;4College of Electronics and Computer,Zheyiang Wanli University Ningbo 315100)

机构地区：[1]宁波大学信息科学与工程学院,宁波315211 [2]宁波大红鹰学院信息工程学院,宁波315175 [3]山东大学计算机科学与技术学院,济南250101 [4]浙江万里学院电子与计算机学院,宁波315100

出　　处：《计算机辅助设计与图形学学报》2018年第7期1236-1242,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61772016;61373068;U1636111;61761166005);宁波市自然科学基金(2016A610041;2016A610040;2016A610042);浙江省科技计划项目(LGG18F020001;2016C33195);浙江省教育厅科研项目(Y201534799);浙江省文化厅项目(zw2016049)

摘　　要：二维形状的金字塔分解在形状编码和形状分析中具有广泛的应用.为解决在拼图游戏中无法提供所有类型的标准件这个问题,提出一种基于多边形最长对角线的二维形状金字塔分解方法.首先将任意多边形划分为2个子多边形;然后基于可视性原理构建2个子多边形之间的可见性距离矩阵,由该矩阵的最大元素给出最长对角线;最后以最长对角线为底,在不引入额外顶点的情况下,通过分而治之的方法分解出尽可能大的金字塔形状.实验结果表明,该方法得到的结果接近最优解,并且在拼图游戏的应用中展示了其有用性和有效性.Pyramidal decomposition of a 2 D shape has a wide range of applications in shape encoding and shape analysis. In order to find common pieces that can be approximately assembled into a set of given shapes, we propose a longest-diagonal based pyramidal decomposition algorithm. First, we partition the input polygon into two sub-polygons along an arbitrary diagonal. Then we construct a visibility based distance matrix between the two sub-polygons to encode the distances between vertices. After that, the longest diagonal can be quickly found with the help of the distance matrix. Finally, we take the longest diagonal as the base and decompose the input shape in a divide-and-conquer style. Extensive experimental results show that our solution is very close to the optimal one. We also demonstrate its use in puzzle designing.

关 键 词：金字塔分解 最长对角线 分而治之 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]