计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2013年
z1期
178-181
,共4页
凸壳%平面点集%特征点%角域%分治%迭代
凸殼%平麵點集%特徵點%角域%分治%迭代
철각%평면점집%특정점%각역%분치%질대
convex hull%planar point set%trait-point%triangle-region%divide-conquer%iteration
提出一种新的平面点集凸壳构建算法,算法基于角域处理的过程对点集分而治之计算凸壳,基于特征角计算的方法成对查找角域特征点,利用初始角域划分和角域更新的机制不断缩小问题规模,从而迅速逼近凸壳边.针对大规模数据点集,算法又引入迭代思想,利用算法本身对非凸壳点的快速删除能力进一步加速凸壳求解进程,使得算法性能进一步提升,算法时间复杂度和空间复杂度均为O(n).实验结果表明,这是一个可行、高效而且稳定的算法,易于推广到三维,也容易改进成并行算法.
提齣一種新的平麵點集凸殼構建算法,算法基于角域處理的過程對點集分而治之計算凸殼,基于特徵角計算的方法成對查找角域特徵點,利用初始角域劃分和角域更新的機製不斷縮小問題規模,從而迅速逼近凸殼邊.針對大規模數據點集,算法又引入迭代思想,利用算法本身對非凸殼點的快速刪除能力進一步加速凸殼求解進程,使得算法性能進一步提升,算法時間複雜度和空間複雜度均為O(n).實驗結果錶明,這是一箇可行、高效而且穩定的算法,易于推廣到三維,也容易改進成併行算法.
제출일충신적평면점집철각구건산법,산법기우각역처리적과정대점집분이치지계산철각,기우특정각계산적방법성대사조각역특정점,이용초시각역화분화각역경신적궤제불단축소문제규모,종이신속핍근철각변.침대대규모수거점집,산법우인입질대사상,이용산법본신대비철각점적쾌속산제능력진일보가속철각구해진정,사득산법성능진일보제승,산법시간복잡도화공간복잡도균위O(n).실험결과표명,저시일개가행、고효이차은정적산법,역우추엄도삼유,야용역개진성병행산법.
