Почему не делает этой реализации марта Jarvis (“Алгоритм обертывания подарка”) работа?

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

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" Arash Partow
  • Реализация снята более или менее непосредственно со статьи Wikipedia об алгоритме

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

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

ОБНОВЛЕНИЕ:

Jonathan Dursi поместил меня на правильном пути. Эта строка

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

должен быть заменен этим

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

Работы как очарование :-)

13
задан Svein Bringsli 19 October 2010 в 20:51
поделиться