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

摘要

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