求两个凸包上切线时，外层while循环的必要性是什么？

已知两个按逆时针排序的凸多边形a、b，inda是多边形a的最右点，indb是多边形b的最左点，Orientation函数用于判断三点的方向（常规定义：返回值>0表示三点逆时针排列，=0表示共线，<0表示顺时针排列）。

用户提供的算法代码如下：

bool done = 0;

while (!done)
{
    done = 1;
    while (orientation(b[indb], a[inda], a[(inda+1)%n1]) >=0)
        inda = (inda + 1) % n1;

    while (orientation(a[inda], b[indb], b[(n2+indb-1)%n2]) <=0)
    {
        indb = (n2+indb-1)%n2;
        done = 0;
    }
}

你的理解有误，外层while循环是保证算法收敛到真正的上切线端点的关键，不能省略，原因如下：

• 第一个内层循环：固定indb的位置，把inda调整到当前indb对应的a的上切线点——也就是确保从b[indb]出发，a[inda]是a上能形成上切线的最优点（此时a[(inda+1)%n1]不会在b[indb]->a[inda]的逆时针方向/上方）。
• 第二个内层循环：固定调整后的inda，把indb调整到当前inda对应的b的上切线点。但这个调整过程中indb的位置发生了变化（此时done被设为0），意味着之前找到的inda已经不是新indb对应的最优上切线点了——因为b的切点变了，a的切点可能需要跟着更新。
• 外层循环的作用就是触发这个"互相调整"的过程：只要indb发生过变动，就重新回去调整inda，再基于新的inda调整indb，直到某次循环中indb没有任何变动（done保持为1），此时的(a[inda], b[indb])才是两个凸包真正的上切线端点。

举个直观的例子：初始inda是a的最右点，indb是b的最左点。第一次调整inda后，indb向左（逆时针方向）移动了2个点；这时候新的indb对应的a的上切线点已经不是之前的inda了，必须重新调整inda，反复这个过程直到两者都不再变化，才能得到正确的结果。

内容的提问来源于stack exchange，提问作者Sneh Raval