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

时间:2022-09-30 10:53:23
【文件属性】:

文件名称:论文研究-求平面点集凸壳的一种新算法.pdf

文件大小:353KB

文件格式:PDF

更新时间:2022-09-30 10:53:23

论文研究

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


网友评论