二维形状的金字塔分解

摘要：

二维形状的金字塔分解在形状编码和形状分析中具有广泛的应用. 为解决在拼图游戏中无法提供所有类型的标准件这个问题, 提出一种基于多边形最长对角线的二维形状金字塔分解方法. 首先将任意多边形划分为 2 个子多边形; 然后基于可视性原理构建 2 个子多边形之间的可见性距离矩阵, 由该矩阵的最大元素给出最长对角线; 最后以最长对角线为底, 在不引入额外顶点的情况下, 通过分而治之的方法分解出尽可能大的金字塔形状. 实验结果表明, 该方法得到的结果接近最优解, 并且在拼图游戏的应用中展示了其有用性和有效性.

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

所属期刊栏目：30

分类号：TP391.41(计算技术、计算机技术)

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

在线出版日期：2018-08-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1236-1242