Warum funktioniert diese Implementierung von Jarvis 'March ("Gift wrapping algorithm") nicht?

Question

Ich versuche, Jarvis Algorithmus zum Finden der konvexen Hülle einer Reihe von Punkten zu implementieren, aber aus irgendeinem Grund funktioniert es nicht. Dies ist meine Implementierung:

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 ist eine einfache Liste von Punkten.
• Orientierung ist eine Funktion von Arash Partow Bibliothek „FastGEO“
• Die Umsetzung mehr oder weniger direkt aus dem geschieht

Wikipedia article on the algorithm angehoben Was ist, dass das Verfahren den gleichen Punkt beginnt das Hinzufügen immer und immer wieder aHull . In einem Testfall sende ich die Punkte (200; 200) (300; 100) (200; 50) und (100; 100) ein, und der Algorithmus beginnt mit der Addition von (100; 100) zu aHull, was korrekt ist, aber dann es beginnt immer wieder (200; 200) hinzuzufügen.

Offensichtlich habe ich etwas falsch in meiner Umsetzung gemacht, aber für das Leben von mir kann ich nicht sehen was.

UPDATE:

Jonathan Dursi hat mich auf dem richtigen Weg.

aHull.Add(vPointOnHull); 

vPointOnHull ist: Diese Zeile

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

sollte mit diesem

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

wirkt wie ein Zauber :-)

Answer 1

Es ist wahrscheinlich kein conicidence, dass (200; 200) Punkt ist 0.

Es sieht aus wie Sie nicht den aktuellen Punkt ohne (vPointOnHull) aus dem Wesen Endpunkt (vEndPoint), und Ihre Implementierung von Orientation weist diesen Fall nicht zurück; vermutlich gibt es LHS zurück, wenn das Kreuzprodukt positiv ist, und wenn vPointOnHull == vEndPoint, ist das Kreuzprodukt Null, also niemals LHS. Also ersetzt nichts jemals den Punkt 0, wenn einmal Punkt 0 ausgewählt ist, und voila.

Sie könnten die Ausrichtung ändern, um in diesem Fall "Entartete" oder etwas zurückzugeben, und auch den Punkt ablehnen, oder Sie könnten den aktuellen Punkt ausschließen, der jemals der Endpunkt ist. Beachten Sie, dass Sie nicht das Offensichtliche tun möchten, sondern die aktuellen CH-Punkte während des Durchmarschs aus dem Punktsatz herausfiltern, da Sie feststellen müssen, dass der Endpunkt der erste Punkt ist, an dem die Schleife geschlossen wird.

aktualisieren: Auf der Suche um ein bisschen am FastGEO Sachen, wahrscheinlich Orientierung Aktualisierung ist nicht der Weg zu gehen (wenn auch ein wenig mehr Gedanken in die kollineare Punkte Fall in diesem Algorithmus gehen sollte, wenn es auf kollineare Punkte sind der Rumpf, Sie wollen wirklich den nächsten zuerst, so dass Sie eine else if Orientation = Collinear then.. update vEndpoint if new point is closer Klausel nach der if-Anweisung möchten).

Easiest könnte nur ein paar Zeilen die Verfolgung der aktuellen indicies hinzuzufügen sein, so dass Sie leicht auf Gleichheit testen:

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

Die Schleife fügt mit dieser Codezeile ersetzt werden nur in diesen Zeilen zugewiesen:

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

Sie bereits erklärt, dass LeftMostPoint korrekt hinzugefügt wird, so dass die Wiederholung von vEndPoint kommen müssen, die in diesen Zeilen zugeordnet:

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

Also ich denke, die letzte Aufgabe (die in der folgenden if-Anweisung), wird nie erreicht.

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

--jeroen