二维形状的金字塔分解

摘要

二维形状的金字塔分解是几何处理中的一个基本问题,被广泛应用于形状编码和形状分析中.求解二维形状的最优金字塔分解(块数最少)是一个NP难问题.本文首先实现了由Aggarwal和Suri提出的算法,它基于可视性原理能够在3O(nlog n)时间和O(n)空间内求出任意多边形的最长对角线;然后基于最长对角线,本文提出了分而治之的金字塔分解算法,并证明了它的平均时间复杂度为O(nlog n).大量的实验结果表明,本文算法的运行速度非常快,实际的运行时间与边界上的采样点数基本呈线性关系,而且最终得到的金字塔分解结果接近最优解。