平面点集凸壳的快速近似算法

摘要

提出并实现了平面点集凸壳的一种新的近似算法--多方向极值法.该算法首先根据用户输入的控制参数,顺序生成一系列极值方向,每个方向有对应的极值表达式;然后扫描平面点集中的点,依每个点的坐标更新各方向上的极值点信息;最后按照一定的顺序装配各极值点并去重,得到该平面点集的一个近似凸壳.实验表明,该算法执行效率高,不但可以单独应用在一些对时间要求比较苛刻而对精度要求不高的场合,而且可以作为快速凸壳算法的一个预处理过程.