Марш Джарвиса

В вычислительной геометрии марш Джарвиса или алгоритм подарочной упаковки используется для вычисления выпуклой оболочки заданного набора точек. Алгоритм имеет широкий спектр приложений в математике и информатике, практически в распознавании образов, обработке изображений, статистике, географических информационных системах (ГИС) и теории игр.

Выпуклая оболочка или выпуклая оболочка набора точек P на евклидовой плоскости — это наименьшее выпуклое множество, содержащее P. Это похоже на обертывание множества точек P внутри границы с использованием самого внешнего меньшего набора точек P, как показано на иллюстрации. ниже.

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

Алгоритм марша Джарвиса реализован в Ada 2012 для демонстрации контрактного программирования. В процедуре Jarvis, если предварительное условие не менее 3 элементов в массиве не выполняется, будет возбуждено исключение. Демонстрационная программа перехватывает исключение, выводит ошибку исключения с сообщением «В массиве должно быть не менее 3 точек». а затем выйти изящно.

Спецификация пакета 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;

Тело пакета 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;

Основная демонстрационная программа 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;

Полный исходный код доступен на моем GitHub. Если вы найдете это полезным, пожалуйста, напишите мне сообщение.

Первоначально опубликовано на сайте adrianhoe.com 31 декабря 2016 г.

Марш Джарвиса

Вопросы по теме