凸包
写在前面
最近因为某道鬼题需要求凸包,吓得我赶紧去恶补了一发。
概念(copy自百度百科)
在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1,…Xn)的凸组合来构造.
在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有的点。
如下图:
求凸包
暴力
枚举两个点确定一条直线,然后判断其它的所有点是否在这条直线的一侧,如果是,则这两个点是凸包上的点。时间复杂度是
当然还可以分治,(具体怎么做留坑)。
Jarvis步进法
首先选择
Graham扫描法
也是先选择