算法笔记（二）凸包问题convex hull

本文主要是介绍算法笔记（二）凸包问题convex hull，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、问题定义：

（1）输入：平面上的n个点的集合Q ；输出： CH(Q)，即Q的凸包

（2）Q的凸包：是一个最小凸多边形 P，Q的点在P上或者在P内

（3）凸多边形P： 连接P内任意两点的边都在P内

2、基本思想：

（1）当沿着凸包逆时针漫游时，总是向左转；

（2）在极坐标系下按照极角大小排列，然后按逆时针方向漫游点集，去除非凸包顶点(非左转点)

3、伪代码：

4、时间复杂性分析：T(n)=O(nlogn)

这篇关于算法笔记（二）凸包问题convex hull的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！