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.

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;

## Jarvis’ March

Tags: Ada, Ada2012, algorithm, computational, computer science, contract programming, convex, geometry, hull, Jarvis, Math, mathematics