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 (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;
The full source code is available at my GitHub. If you find it useful, please drop me a message.
Originally published at adrianhoe.com on December 31, 2016.
