基于边界链码的球链接形状拼图算法

作者：胡振震^*; 吴若非; 蒋旭; 孙光

来源：计算机应用, 2018, S2: 196-269.

• 边界链码
• 球链接形状
• 拼图游戏
• 拼图算法
• 矩阵填充

针对可扩展的球链接形状拼图,提出了一种基于边界链码的拼图算法。首先利用由Morre方法改进的边界检测方法生成边界链码,然后通过原始链与差分链的相互转换实现链接球形状的翻转和旋转,其次基于最大数量链码匹配、合理性检查实现形状拼接,最后通过链码与形状矩阵互相转换完成形状定位和结果显示。矩阵大小为5～9的拼图实验中,一次实验所用拼图次数为1的实验数占比从0. 69下降到0. 02,说明随着拼图矩阵增大,拼图复杂度升高。对矩阵大小为6～10的拼图做1 000次实验,与基于矩阵填充的算法相比,基于边界链码的算法平均用时最高下降了68. 2%,分析表明该算法效率提升的关键是减少了拼图过程形状选择的随机性。