Почему не работает эта реализация Jarvis 'March («Алгоритм упаковки подарков»)?

Question

Я пытаюсь реализовать алгоритм Джарвиса для нахождения выпуклой оболочки набора точек, но по какой-то причине он не работает. Это моя реализация:

procedure TPointList.ConvexHull(aHull : TPointList); //Return the convex hull of a set of 2D points
var
  vPointOnHull  : TPoint2D;
  vEndpoint     : TPoint2D;
  I             : integer;
begin
  aHull.Clear;
  if Count < 3 then exit;

  vPointOnHull := Self.LeftMostPoint;
  repeat
    aHull.Add(vPointOnHull);
    vEndpoint := Self.Point[0];

    for I := 1 to Self.Count-1 do
      if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then
        vEndpoint := Self.Point[I];

    vPointOnHull := vEndpoint;
  until vEndpoint = aHull.Point[0];
end;

• TPointList представляет собой простой список точек.
• Ориентация является функцией из библиотеки Араша Партоу "FastGEO"
• Реализация более или менее непосредственно взята из статьи Википедии об алгоритме

В результате метод снова и снова добавляет одну и ту же точку к aHull. В одном тестовом примере я отправляю точки (200; 200) (300; 100) (200; 50) и (100; 100), и алгоритм начинается с добавления (100; 100) к aHull, что правильно, но затем он начинает добавлять (200; 200) снова и снова.

Очевидно, что я сделал что-то не так в своей реализации, но за свою жизнь я не вижу что.

UPDATE:

Джонатан Дурси поставил меня на правильный путь. Эта строка

if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then    

следует заменить на этот

if (vPointOnHull = vEndpoint) or (Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide) then

Работает как шарм: -)

Answer 1

Вероятно, это не совпадение, что (200; 200) является точкой 0.

Похоже, вы не исключаете текущую точку (vPointOnHull) из конечной точки (vEndPoint), и ваша реализация ориентации не отвергает этот случай; по-видимому, он возвращает LHS, если перекрестный продукт положительный, а если vPointOnHull == vEndPoint, перекрестный продукт равен нулю, поэтому никогда не LHS. Так что ничто никогда не заменит точку 0, если точка 0 выбрана и т. Д.

Вы можете изменить Ориентацию, чтобы она возвращала «Вырождение» или что-то в этом случае, а также отклонить точку, или вы можете исключить текущую точку из когда-либо конечной точки. Обратите внимание, что вы не хотите делать очевидную вещь, отфильтровывать текущие точки CH из заданной точки во время прохождения, потому что вам нужно найти, что конечная точка является первой точкой, закрывающей цикл.

Обновление : Оглядываясь немного на вещи FastGEO, вероятно, не стоит обновлять Ориентацию (хотя в этом алгоритме нужно немного больше думать о коллинеарных точках; если есть коллинеарные точки на корпусе, вы действительно хотите сначала найти ближайший, поэтому вам нужно выражение else if Orientation = Collinear then.. update vEndpoint if new point is closer после этого оператора if).

Проще всего добавить пару строк, отслеживающих текущие показатели, чтобы вы могли легко проверить на равенство: что-то вроде

iPointOnHull := Self.IndexOfLeftMostPoint;
vPointOnHull := Self.LeftMostPoint
...
vEndpoint := Self.Point[0];
iEndPoint := 0;
if (iPointOnHull = 0) then 
begin
    vEndPoint := Self.Point[1];
    iEndPoint := 1;
end
...
vPointOnHull := vEndPoint;
iPointOnHull := iEndPoint;

Answer 2

Цикл добавляет с использованием этой строки кода:

aHull.Add(vPointOnHull);

vPointOnHull назначается только в следующих строках:

vPointOnHull := Self.LeftMostPoint;
vPointOnHull := vEndpoint;

Вы уже объяснили, что LeftMostPoint добавлено правильнотаким образом, повтор должен исходить из vEndPoint, который присваивается в следующих строках:

vEndpoint := Self.Point[0];
vEndpoint := Self.Point[I];

Так что я думаю, что последнее назначение (которое находится в приведенном ниже операторе if) никогда не будет достигнуто.

  if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then
    vEndpoint := Self.Point[I];

- Йероен