从时间复杂度上来看,极点是O(n4),极边是O(n3),那么,还有没有可能使时间复杂度更小呢?
如上图所示将外部点X加入到原凸包,(即S黄Vt蓝V所在的凸包)那么可以观察到,将会组成新的凸包XS黄Vt,也就是说,逆时针来看,保留st这段,舍弃ts这段。
那么st这段为什么要保留,而ts这段为什么舍弃呢?分界点s,t有什么特征呢?
这还是涉及到了toLeft原理。根据每个点的直接前驱和直接后继在x点到该点的直线的关系,可以分为四种情况
1,xt是凸包的切线,不管t是直接后继也好,直接前驱也好,都在xt这条线的右侧,即R+R
2,xs也是凸包的切线,不管t是直接后继也好,直接前驱也好,都在xs这条线的左侧,即L+L
3,对点黄V,x->黄V这条线,黄V的直接后继(即在S黄V这段)在线的右侧,黄V的直接前驱(即在黄V到t这段)在线的左侧,即R+L
4,对点蓝V,x->蓝V这条先,蓝V的直接后继(即在t蓝V这段)在线的左侧,蓝V的直接前驱(即在蓝V到s这段)在线的右侧,即L+R
所以,对于添加的外部点X来说,只要找到了两个点ts即可,保留st,舍弃ts,将X缝合起来,形成新凸包xs黄vt。
如果新添加的点X在内部,如下图所示,则每个点都是R+L,凸包不变。