一种新的求平面点凸壳算法

摘要

本文提出了一种新的求平面点凸壳的算法。本算法的基本思想是:首先找出给定的二维点集的所有最外点(即Xmax,Ymax,Xmin,Ymin对应的点),则这些最外点肯定是凸壳上的点。再利用四个最外点将二维点集划分为四个相对的子区域。最后在这四个子区间内分别从一个最外点开始寻找与基准线夹角最大的点,迭代查找,并不断缩小查找区域,直至四个子区间都查找完毕。