group

Jarvis’ March

In computational geometry, Jarvis’ march or gift wrapping algorithm is used to compute the convex hull of a given set of points. The algorithm has broad range of applications in mathematics and computer science practically in pattern recognition, image processing, statistics, geographic information system (GIS) and game theory.
Convex hull or convex envelope of a set of P points in a Euclidean plane is the smallest convex set that contains P. It is like wrapping the set of P points inside a boundary using the outermost smaller set of P points, as depicted in an illustration below.
jarvis
The pseudo code:
Jarvis (S)
   with pre condition of at least 3 elements in S

   Left ← find the leftmost point in S

   P ← Left

   Initialize the array of Result to -1

   repeat
      for I from S'First to S'Last loop
         p ← S(P)
         q ← S(I)
         r ← S(Q)
         if orientation of triplet (p, q, r) = counter clockwise
            Q ← I
      end loop
      Result(P) ← Q
      P ← Q
   until P = Left 
The Jarvis’ march algorithm is implemented in Ada 2012 to demonstrate contract-based programming. In procedure Jarvis, if a pre condition of at least 3 elements in the array is not met, an exception will be raised. The demo program catches the exception, prints the exception error with a message “Must have at least 3 points in the array.” and then exit gracefully.
The package specification, jarvis_march.ads:

pragma Assertion_Policy(Check);
      
package Jarvis_March is
      
   type Orientation is ( Colinear, Clockwise, Counter_Clockwise );
      
   type Point is
      record
         X : Integer;
         Y : Integer;
      end record;
   
   type Points is array ( Integer range <> ) of Point;
   type Result is array ( Integer range <> ) of Integer;
   
   procedure Jarvis ( Ps : in     Points;
                      R  :    out Result )
      with Pre => ( Ps'Length > 2 );
      
private
 
   function Find_Orientation ( P, Q, R : Point )
      return Orientation;
      
   function Find_Leftmost ( Ps : Points )
      return Integer;
      
end Jarvis_March;
The package body, jarvis_march.adb:

package body Jarvis_March is

   procedure Jarvis ( Ps : in     Points;
                      R  :    out Result )
   is
      
      Size     : Natural := Ps'Length;
      
   begin
      declare
         Left, P, Q  : Integer;
      begin
         R := ( others => -1 );
            
         Left := Find_Leftmost ( Ps );
            
         P := Left;
            
         Search_Loop:
            loop
                  
               Q := ( ( P + 1 ) mod Size ) + 1;
                  
               for I in Ps'First .. Ps'Last loop
                  if ( Find_Orientation ( Ps ( P ), Ps ( I ), Ps ( Q ) ) = Counter_Clockwise ) then
                     Q := I;
                  end if;
               end loop;
                     
               R ( P ) := Q;
               P := Q;
                  
               exit Search_Loop when P = Left;
            end loop Search_Loop;
      end;            
   end Jarvis;
   
   function Find_Leftmost ( Ps : Points ) return Integer is
   
      L    : Integer := Ps'First;
      P, Q : Point;
      
   begin
      
      for I in 1 .. Ps'Length loop
         
         P := Ps ( I );
         Q := Ps ( L );
         
         if ( P.X < Q.X ) then
            L := I;
         end if;
      end loop;

      return L;

   end Find_leftmost;

   function Find_Orientation ( P, Q, R : Point ) return Orientation is
   
      Direction : Integer;

   begin
      Direction := ( Q.Y - P.Y ) * ( R.X - Q.X ) - ( Q.X - P.X ) * ( R.Y - Q.Y );

      if Direction = 0 then
         return Colinear;
      end if;

      if Direction > 0 then
         return Clockwise;
      else
         return Counter_Clockwise;
      end if;
         
   end Find_Orientation;
   
end Jarvis_March;
The main demo program, jarvistest.adb:

with Ada.Exceptions;    use Ada.Exceptions;
with Ada.Text_IO;       use Ada.Text_IO;
with Jarvis_March;      use Jarvis_March;
   
procedure jarvistest is
   
   -- Comment/uncomment the two lines below to test the pre condition of the
   -- contract assertion in procedure Jarvis
   Ps : Points ( 1 .. 7 ) := ( ( 0, 6 ), ( 1, 2 ), ( 1, 1 ), ( 2, 1 ), ( 3, 1 ), ( 0, 0 ), ( 4, 3) );
--   Ps : Points ( 1 .. 2 ) := ( ( 0, 6 ), ( 1, 2 ) );
   R  : Result ( Ps'Range );
   
   P : Point;
   
begin

   Jarvis ( Ps, R );
   
   for I in R'Range loop
      if ( R ( I ) /= -1 ) then
         P := Ps ( I );
         Put_Line ( "(" & Integer'Image ( P.X ) & ", " & Integer'Image ( P.Y ) & ")" );
      end if;
   end loop;
      
exception
   when Error : others => Put_Line (Ada.Exceptions.Exception_Name ( Error ) & ": Must have at least 3 points in the array.");
      
end jarvistest;
 Terminal output.
This article is also published at Medium.
The full source code is available at my GitHub. If you find it useful, please drop me a message.