¿Por qué no funciona esta implementación de Jarvis 'March ("Algoritmo de envoltura de regalos")?

Question

Estoy tratando de implementar el algoritmo de Jarvis para encontrar el casco convexo de un conjunto de puntos, pero por alguna razón no funciona. Este es mi aplicación:

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 es una simple lista de puntos.
• La orientación es una función de la biblioteca de Arash Partow "FastGEO"
• La aplicación se levanta más o menos directamente de la Wikipedia article on the algorithm

Lo que sucede es que el método se inicia añadiendo el mismo punto a ahull una y otra . En un caso de prueba, envío los puntos (200; 200) (300; 100) (200; 50) y (100; 100), y el algoritmo comienza por agregar (100; 100) a una Casilla que es correcta, pero luego comienza a agregar (200; 200) una y otra vez.

Obviamente he hecho algo mal en mi implementación, pero por mi vida no puedo ver qué.

ACTUALIZACIÓN:

Jonathan Dursi me puso en el camino correcto. Esta línea

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

debe ser reemplazado con esta

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

funciona como un encanto :-)

Answer 1

Probablemente no sea un conicidence que (200; 200) es el punto 0.

Parece que usted no está excluido el punto actual (vPointOnHull) de ser el punto final (vEndPoint), y su implementación de Orientación no rechaza ese caso; presumiblemente devuelve LHS si el producto cruzado es positivo, y si vPointOnHull == vEndPoint, el producto cruzado es cero, por lo tanto, nunca LHS. De modo que nada reemplaza nunca al Punto 0 una vez que se selecciona el Punto 0, et voila.

Puede modificar Orientation para devolver "Degenerate" o algo así en ese caso, y también rechazar el punto, o puede excluir que el punto actual sea el punto final. Tenga en cuenta que no desea hacer lo obvio, filtre los puntos CH actuales desde el punto establecido mientras avanza, porque necesita encontrar que el punto final es el primer punto para cerrar el ciclo.

actualización: Mirando a su alrededor un poco en la materia FastGEO, probablemente, la actualización de orientación no es el camino a seguir (aunque un poco más de pensamiento debe entrar en el caso puntos colineales en este algoritmo, si hay puntos alineados en el casco, realmente quiere el más cercano primero, por lo que le gustaría una cláusula else if Orientation = Collinear then.. update vEndpoint if new point is closer después de esa declaración if).

más fácil podría ser simplemente añadir un par de líneas de hacer el seguimiento de los índices del actuales para que pueda probar fácilmente por la igualdad: algo un poco como

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

El bucle se suma el uso de esta línea de código:

aHull.Add(vPointOnHull); 

vPointOnHull es solo asignado en estas líneas:

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

Usted ya se ha explicado que se añade correctamente LeftMostPoint, por lo que la repetición debe venir de vEndPoint, que se asigna en estas líneas:

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

así que supongo que la última asignación (que se encuentra en el siguiente sentencia if), nunca se alcanza.

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

--jeroen