礼品包装算法(Jarvis March) -使用交叉产品的单次运行

Question

在著名的《算法导论-第三版》一书中，用于在二维空间中寻找一组点的凸包的礼物包装算法被描述为需要:

1. 分别运行2次查找凸包的左右链
2. 对凸壳最后一段的极角进行排序

，以便使用叉乘技巧来排序极角并得到正确的结果。

然而，在我看来，只考虑凸壳的最新点就足够了。以下是我的方法(假设输入中没有3个共线点):

pLast = latest found point of the Convex Hull
<p1, p2, ..., pk> = points that are not (yet) in the Convex Hull
pNext = the next point of the Convex Hull (trying to find this)
pNext = p1 
for i=2 to k 
   if (nonLeftTurn(pLast, pNext, pi) == true)
      pNext = pi

这里nonLeftTurn(p1, p2, p3)返回true如果p3在方向线p1->p2的右边:

nonLeftTurn(p1, p2, p3):
   if ( (p2 - p1) x (p3 - p1) <= 0)
      return true
   else
      return false

在我看来，这个方法是正确的。我错过了什么?你能不能提供一个反例，因为我找不到。

谢谢!

Answer 1

这个方法是正确的，你不需要最后一段凸包。你需要找到可以用pLast形成的"最右边"的线段，这意味着你需要所有剩余的点都在该线段的左侧，这样的线段显然是凸包的一部分，你的程序就是这样做的。图片如下,你采取任何点p和连接体,然后你确认所有剩余点谎言离开,如果有任何其他点的吧,然后你把q的p,注意,你不需要再次检查你已经检查所有点p,因为所有的点左边的左边的体-> p也体-> q,然后你继续检查问剩下的点。前面的观察表明，当您检查完所有点时，所有剩余的点都位于pLast->pNext的左侧，因此pNext是凸包中的一个点。

Jarvis的行军目标是找到这样的最右边的段，这是算法的设计方式，你找到这样的最右边的段的方式可能不同，我想这本书的范围不是那么彻底，以显示所有可能的实现，所以我猜它只建议这两个，因为它不是一个计算几何书。