Dlaczego ta implementacja Marca Jarvisa ("Algorytm pakowania prezentów") nie działa?

Question

Próbuję zaimplementować algorytm Jarvisa do znajdowania wypukłego kadłuba zestawu punktów, ale z jakiegoś powodu to nie działa. To jest moje wykonanie:

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 jest prosta lista punktów.
• Orientacja jest funkcja z biblioteki Arash Partow za „FastGEO”
• Realizacja jest podnoszony bardziej lub mniej bezpośrednio z Wikipedia article on the algorithm

Co się dzieje, jest to, że metoda rozpoczyna się dodając ten sam punkt na aHull kółko . W jednym przypadku testowym wysyłam punkty (200; 200) (300; 100) (200; 50) i (100; 100), a algorytm rozpoczyna się od dodania (100; 100) do wartości, która jest poprawna, ale potem zaczyna dodawać (200; 200) w kółko.

Oczywiście zrobiłem coś złego w mojej realizacji, ale dla mojego życia nie widzę co.

UPDATE:

Jonathan Dursi umieścić mnie na właściwe tory. Ta linia

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

należy zastąpić tego

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

działa jak czar :-)

Answer 1

To nie jest chyba conicidence że (200; 200) jest punktem 0.

Wygląda na to, nie jesteś wyjątkiem aktualny punkt (vPointOnHull) od bycia punkt końcowy (vEndPoint), a twoja implementacja Orientacji nie odrzuca tej sprawy; prawdopodobnie zwraca LHS, jeśli iloczyn jest pozytywny, a jeśli vPointOnHull == vEndPoint, iloczyn krzyżowy wynosi zero, a więc nigdy LHS. Więc nic nigdy nie zastąpi Punktu 0 po wybraniu Punktu 0, i voila.

Można zmodyfikować Orientację, aby zwrócić "Zdegenerowany" lub coś podobnego w tym przypadku, a także odrzucić punkt, lub można wykluczyć bieżący punkt z punktu będącego zawsze punktem końcowym. Zauważ, że nie chcesz robić rzeczy oczywistej, odfiltruj bieżące punkty CH z punktu ustawionego podczas marszu, ponieważ musisz odkryć, że punkt końcowy jest pierwszym punktem do zamknięcia pętli.

Aktualizacja: Rozglądając się trochę na rzeczy FastGEO, prawdopodobnie aktualizowania Orientacja nie jest droga (choć nieco bardziej myśl powinna iść do kolinearna punktów w przypadku tego algorytmu, jeśli nie są współliniowe punkty na kadłub, naprawdę chcesz najbliższy pierwszy, więc chciałbyś mieć klauzulę else if Orientation = Collinear then.. update vEndpoint if new point is closer po tej instrukcji if).

Najprostszym może być po prostu dodać kilka linii śledzenie aktualnych indeksów, dzięki czemu można łatwo przetestować dla równości: coś trochę jak

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

Pętla dodaje za pomocą tego wiersza kodu:

aHull.Add(vPointOnHull); 

vPointOnHull jest przypisany tylko w tych liniach:

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

Już wyjaśnił, że LeftMostPoint dodaje poprawnie, więc powtarzać musi pochodzić z vEndPoint, który jest przypisany w tych liniach:

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

Więc myślę ostatniego zadania (co jest w poniższej instrukcji if) nigdy nie zostanie osiągnięty.

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

--jeroen