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

New efficient approximate convex hull algorithm for very large planar point set

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

A new approximate convex hull algorithm for very large planar point set is presented. That is multi-direction extreme value approximate convex hull algorithm, and is called MDEV for short. Firstly, according to the control parameter given by the user, a series of extreme directions are created automatically, and every direction has its corresponding extreme value expression; Secondly, the planar point set is scanned, and the information of the extreme value points in every direction is updated according to the coordinates of every point in the point set; At last, the extreme value points are assembled in a certain order and the duplicate ones are gotten rid, then the approximate convex hull is gained. The experiment shows that the algorithm is very efficient. It can be used in the situation, which is rigor for executing time but not for precision. Also, it can be used as a preprocessing course of efficient convex hull algorithms.