La marche de Jarvis ou l'emballage de cadeau

Algorithmique > Enveloppes convexes > Marche de Jarvis [ Commenter ]

Complexité en temps

La marche de Jarvis est un algorithme que l'on qualifie de « sensible à la sortie ». En effet, sa complexité d'exécution en temps est de la forme Ω(n.h) ; où h est le nombre de sommets du plus petit polygône convexe Ρ comprenant tous les points de Γ.

Cet algorithme est donc très efficace lorsque le polygône optimum ne comprend que peu de sommets. Il est en revanche très lent, puisque quasi-quadratique, lorsque h est grand par rapport à n.

Principe de fonctionnement

Après avoir sélectionné un point A que l'on sait appartenir à Ρ (par exemple car c'est celui qui a la plus petite coordonnée x), on va chercher, parmis tous les points restants le point B tel que tous les autres points soient à droite de (AB). On prend alors B et on répète le processus jusqu'à retrouver le point de départ A. Cette méthode est analogue à l'encerclement de l'ensemble de points Γ avec une ficelle, ou du papier cadeau.

Code (Pascal)

type 
  TVector = record X,Y: Double; end;
  TVectorArray = Array of TVector;

function Jarvis(T: TVectorArray; N: Integer): TVectorArray;

  function SensDirect(A,B,C: TVector): Boolean;
  begin
    Result:=(((C.X-A.X)*(B.Y-A.Y)-(B.X-A.X)*(C.Y-A.Y))>0);
  end;

var
  I,A0,A,B: Integer;
  MinX: Double;
begin

  SetLength(Result,0);

  // Recherche du point le plus à gauche
  MinX:=T[0].X;
  A0:=0;
  For I:= 0 to N-1 do
    if (T[I].X<=MinX) then
      begin
        MinX:=T[I].X;
        A0:=I;
      end;

  // Génération de l'enveloppe convexe
  A:=A0;
  Repeat
    if (A=0) then
      begin
        B:=1;
        For I:= 2 to N-1 do
          if SensDirect(T[A],T[B],T[I]) then B:=I;
      end
    else
      begin
        B:=0;
        For I:= 1 to A-1 do
          if SensDirect(T[A],T[B],T[I]) then B:=I;
        For I:= A+1 to N-1 do
          if SensDirect(T[A],T[B],T[I]) then B:=I;
      end;
    SetLength(Result,Length(Result)+1);
    Result[Length(Result)-1]:=T[B];
    A:=B;
  Until (A=A0);

end;