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

New Recurrence Algorithm for Finding Convex Hull Based on Maximum Current Base Line Vertical Drop

作　　者：周启海[1] 黄涛[1] 

机构地区：[1]西南财经大学信息技术应用研究所

出　　处：《计算机科学》2008年第7期219-223,240,共6页Computer Science

摘　　要：本文依据同构化凸壳构造基本定理,率先发现并证明了凸壳顶点的分布域性态与垂直落差特性;首次给出当前基线垂直落差最大化的二维点集凸壳算法构造创新思想,提出了比迄今最优秀凸壳算法之一的快凸壳算法效率更高的、基于当前垂直落差最大化的凸壳递归新算法,指出了它具有进一步改造为并行算法的潜力。该新算法的主要特点是:1)找出初始点分布域的所有最外点(其个数,下限为3,上限为8),作为所求凸壳的初始顶点。2)删除这些最外点所构成最外点凸多边形(其边数,下限为3,上限为8)所覆盖的凸壳内点后,把所剩点分布域,分为若干个初始子分布域(其个数,下限为0,上限为4)。3)①对各个非空初始子分布域顺次调用本新算法的递归过程子算法,分别在各初始子分布域中找出其当前基线垂直落差最大点(其个数,下限为1,上限为2),并作为其各初始子分布域内凸壳的新顶点;②删除当前基线与垂直落差最大点所构成基线凸多边形(其边数,下限为3,上限为4)内的凸壳内点后,把所剩点分布域,分为多个更小的子分布域(其个数,下限为0,上限为2);③对各个更小的当前子分布域,分别递归调用过程子算法,以找出其当前基线的垂直落差最大点作为凸壳新顶点。In this paper,the domain state natures and vertical drop characters of the apexes of a convex hull are found and proofed in the lead ＇a creative new thought for constructing an algorithm with the maximum current base line vertical drop is given＇a new recurrence algorithm of finding convex hull based on maximum current base line vertical drop which is better than the quick hull algorithm for convex hulls as one of the most excellent convex hull algorithms is advanced the potentialities to reform into parallel algorithm are pointed out. The general characters of this new recur- rence algorithm are： 1） Find out all most-outslde points （its total lower limit is 3, and upper limit is 8） as the initial apexes of a convex hull. 2） After deleting all interior points covered by the most-outslde points＇ convex polygon, the rest points＇ domain is divided into some initial sub-domalns （its total lower limit is 0 ,and upper limit is 4）. 3） 1st, to every not empty current initial sub-domaln, call separately the recurrence procedure sub-algorithm to find out the maximum current base vertical drop points of the current sub-domain （its total lower limit is 1 ,and upper limit is 2） as the convex hull apexes~ 2od, after deleting all interior points covered by the current base＇s convex polygon, the rest points＇ sub-do- main is divided into some smaller sub-domalns （its total lower limit is 0, and upper limit is 2）; 3ra, to every not empty smaller current sub-domaln, call separately the recurrence procedure sub-algorithm to find out the maximum current base vertical drop points of the current sub-domaln as the convex hull apexes.

关 键 词：同构化 当前基线垂直落差 凸壳 递归算法 

分 类 号：TP75[自动化与计算机技术—检测技术与自动化装置] TP311[自动化与计算机技术—控制科学与工程]