基于当前基线垂直落差最大化的凸壳递归新算法

摘要

本文依据同构化凸壳构造基本定理,率先发现并证明了凸壳顶点的分布域性态与垂直落差特性;首次给出当前基线垂直落差最大化的二维点集凸壳算法构造创新思想,提出了比迄今最优秀凸壳算法之一的快凸壳算法效率更高的、基于当前垂直落差最大化的凸壳递归新算法,指出了它具有进一步改造为并行算法的潜力.该新算法的主要特点是:1)找出初始点分布域的所有最外点(其个数,下限为3,上限为8),作为所求凸壳的初始顶点.2)删除这些最外点所构成最外点凸多边形(其边数,下限为3,上限为8)所覆盖的凸壳内点后,把所剩点分布域,分为若干个初始子分布域(其个数,下限为0,上限为4).3) ①对各个非空初始子分布域顺次调用本新算法的递归过程子算法,分别在各初始子分布域中找出其当前基线垂直落差最大点(其个数,下限为1,上限为2),并作为其各初始子分布域内凸壳的新顶点;②删除当前基线与垂直落差最大点所构成基线凸多边形(其边数,下限为3,上限为4)内的凸壳内点后,把所剩点分布域,分为多个更小的子分布域(其个数,下限为0,上限为2);③对各个更小的当前子分布域,分别递归调用过程子算法,以找出其当前基线的垂直落差最大点作为凸壳新顶点.