论文研究 求平面点集凸壳的一种新算法.pdf

在研究了大量的求平面点集凸包的算法基础上，提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点，构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域；对于一个线段区域上的点只需要找出右侧的点，分别和线段的两个端点连接得到新的多边形链，依次这样处理每个点，直到结束。这样就得到四个简单多边形单调链，然后对单调链求凸点，时间复杂度为O（n），最后求得的每个凸点就是平面点集的凸壳，此算法总的时间复杂度不超过O（n log n）。