平面散乱点集凸包的快速生成算法

作者：刘广忠; 黄琳娜

来源：工程图学学报, 2008, (04): 111-114.

• 计算机应用
• 凸包生成算法
• 平面点集凸包
• 计算几何 computer application
• hull-building algorithm
• hull of planar point set
• computational geometry

凸包问题是计算几何的基本问题,在实际工程中得到了广泛的应用。传统的凸包生成算法一般需要两个步骤,首先将离散点按照某种特性排序,然后进行凸包生成。依据快速排序算法的思想,提出一种"一步法"构建平面点集凸包的算法,将构建平面点集的凸包问题与排序问题结合起来,在排序过程中快速生成点集凸包。整个过程达到时间复杂度下限O(nlogn)。该算法在"河北省蓄滞洪区信息管理系统"中得到了实际应用,效果理想。

• 单位
  河北工程技术高等专科学校