精华内容
下载资源
问答
  • 凸包

    2017-12-01 21:36:01
    凸包

    写在前面

    最近因为某道鬼题需要求凸包,吓得我赶紧去恶补了一发。

    概念(copy自百度百科)

    在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1,…Xn)的凸组合来构造.
    在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
    用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有的点。
    如下图:
    这里写图片描述

    求凸包

    暴力

    枚举两个点确定一条直线,然后判断其它的所有点是否在这条直线的一侧,如果是,则这两个点是凸包上的点。时间复杂度是O(n3)的。

    当然还可以分治,(具体怎么做留坑)

    Jarvis步进法

    首先选择x坐标最小(相同x坐标时y坐标最小,下面不再解释)的一个点A,这肯定是凸包上一个点。以这个点为原点,构出一个新坐标系xAy,将剩余所有点按与y轴负方向的极角排序,取第一个点即为凸包上的点,然后继续以这个点建立坐标系,重复上述操作。时间复杂度O(nk)k为凸包上点的个数)。

    Graham扫描法

    也是先选择x坐标最小的点,然后也极角排序。和Jarvis步进法不同的是:我们维护一个单调栈,直接扫描,维护一个有向左转趋势的点集。

    Melkman算法(以后再说)

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,573
精华内容 3,829
关键字:

凸包