Почему эта реализация Марса Джарвиса ( "Алгоритм упаковки подарков" ) не работает?

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

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 - это простой список точек.
  • Ориентация - это функция из библиотеки Arash Partow "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

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

Ответы

Ответ 1

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

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

Вы можете изменить Orientation, чтобы вернуть "Degenerate" или что-то в этом случае, а также отклонить точку или вы можете исключить текущую точку из когда-либо конечной точки. Обратите внимание, что вы не хотите делать очевидную вещь, отфильтровывайте текущие точки 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;

Ответ 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];

- Йерун