在上节中,两部分子凸包有重合的部分,不简洁。这一节是沿着某个方向,子凸包不重叠,如下图
根据以前的方法,很可能认为是两个子凸包上顶点与上顶点相连,下顶点与下顶点相连,形成两条支撑线,缝合成一个新的凸包。如下图所示
实际上不尽然,如下图所示
那么该如何进行呢?左边的子凸包的最右侧的点和左侧子凸包的最左点开始连线。
如下图所示,连接点R和点1
进行zigzag,如果一侧的顶点前驱和后继不是同时toleft,或者toleft,则继续找它的后继(或者前驱)。如果前驱和后继的toleft同号了,则反向计算。直至到两个支撑线t-t,b-b
步骤如下:
LR继续向下走
LL换向
异号,继续
这样就得到了上边的支撑线,同理,可以得到下边的支撑线,缝合成一个新的凸包