0

在著名的“Introduction to Algorithms - 3rd edition”一书中，用于在 2D 空间中找到一组点的凸包的礼品包装算法被描述为需要：

  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

如果 p3 位于定向线 p1->p2 的右侧，则 nonLeftTurn(p1, p2, p3) 返回 true：

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

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

谢谢！

4

1 回答 1

0

该方法是正确的，您不需要凸包的最后一段。您需要找到可以使用 pLast 形成的“最右边”段，这意味着您需要所有剩余点都在该段的左侧，这样的段显然是凸包的一部分，并且您的程序是正是这样做的。你可以画成这样，你取任意点 p 并将它与 pLast 连接，然后你验证所有剩余的点都在它的左边，如果在它的右边有任何其他点 q，那么你取 q 而不是 p，注意你不需要再次检查你已经检查过 p 的所有点，因为 pLast->p 左侧的所有点也在 pLast->q 的左侧，所以你继续检查 q 剩余的点。先前的观察表明，当您检查完所有点后，

Jarvis March 的目标是找到这样的最右边的部分，这就是算法的设计方式，你找到这样的最右边的部分的方式可能会有所不同，我想这本书的范围并没有那么彻底地展示所有可能的实现，所以我猜它只建议这两个，因为它不是计算几何书。

于 2015-05-18T14:58:05.003 回答