Алгоритм упаковки подарков (март Джарвиса) - один запуск с использованием кросс-продукта

Question

В известной книге "Введение в алгоритмы - 3-е издание" Алгоритм упаковки подарков для нахождения выпуклой оболочки набора точек в 2D-пространстве описывается как требующий либо:

1. 2 работает для нахождения левой и правой цепей выпуклой оболочки отдельно
2. сортировка полярных углов относительно последнего сегмента выпуклой оболочки

чтобы использовать трюк Cross Product для сортировки полярных углов и получения правильных результатов.

Однако мне кажется, что достаточно рассмотреть только самую последнюю точку выпуклой оболочки. Вот мой подход (при условии, что на входе нет 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 и соединяете ее с pLast, затем вы проверяете, что все остальные точки лежат слева от нее, если есть любая другая точка q справа от нее, тогда вы берете q вместо p, обратите внимание что вам не нужно снова проверять все точки, которые вы уже проверили для p, поскольку все точки слева от pLast->p также находятся слева от pLast->q, поэтому вы продолжаете проверять q с остальными точками. Предыдущее наблюдение подразумевает, что когда вы закончили проверку всех точек, все остальные точки лежат слева от pLast->pNext, и, таким образом, pNext является точкой в ​​выпуклой оболочке.

Цель марша Джарвиса состоит в том, чтобы найти такой правый сегмент, и именно так алгоритм спроектирован, способ, которым вы можете найти такой правый сегмент, может отличаться, и я полагаю, что область книги не настолько тщательна, чтобы показать все возможные реализации, поэтому я предполагаю, что предложите только эти два, так как это не книга по вычислительной геометрии.