安德鲁算法求凸包
凸包
凸包 百度百科:二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈
求解
凸包可以看做是最外边的一圈点,因此凸包一定是一个凸多边形,我们可以根据凸多边形的性质来求解。
如果我们给按照顺时针方向给凸多边形的所有边一个正方向:
有如下性质,对于所有相邻点,凸多边形上的其他点一定在这两个相邻点确定的向量的“右侧”。
那么我们在维护凸包的过程中,只需不断的查看在当前情况下,“左侧”是否有点,有点的话就要把当前点去掉,选取左侧的点。
安德鲁算法
维护过程:
- 先以横坐标为第一关键字,纵坐标为第二关键字,将所有点排序。
- 如果栈中有大于等于两个点,判断等待点是否在栈中最后两个点组成的向量的左侧,如果是,那么弹出栈顶元素。不断循环直到不再弹出元素。
- 压入等待点。
上面的过程即可维护出上凸包。下凸包同理。
代码
1 |
|