Progetto di I.U.M. Modellazione Geometrica

Alternativa 3: Algoritmo di Jarvis

Funzione principale

Parametri di ingresso

• points: insieme di punti nel piano (di cui si vuole calcolare il guscio convesso).

Parametri di uscita

• hull: lista ordinata di punti nel piano (rappresenta i vertici di un poligono ordinati in senso antiorario, tale poligono sara' il guscio convesso dell'insieme di punti dati in ingresso).

Variabili locali

• bottom punto di ordinata minima (e, a parita' di ordinata, di ascissa massima) dell'insieme points.
• top punto di ordinata massima (e, a parita' di ordinata, di ascissa minima) dell'insieme points.
• current = punto corrente (l'ultimo punto trovato e il prossimo punto da trovare) sul contorno del guscio convesso

Pseudocodice

Algorithm Jarvis(input: points, output: hull)
 begin
    bottom = punto di ordinata minima in points;
    top = punto di ordinata massima in points;   
    hull = lista vuota;
    current = bottom;
    repeat 
      current = NextHullPointUp(current,points);
      aggiungi current alla lista hull;
    until (current==top);
    repeat 
      current = NextHullPointDown(current,points);
      aggiungi current alla lista hull;
    until (current==bottom);
 end

Ricerca del prossimo punto

• NextHullPointUp cerca il prossimo punto sul guscio convesso risalendo sulla parte destra del guscio convesso
• NextHullPointDown cerca il prossimo punto sul guscio convesso ridiscendendo sulla parte sinistra del guscio convesso

Parametri di ingresso

• start: un punto vertice del guscio convesso sulla parte destra del guscio
• points: l'insieme di punti

Parametri di uscita

• next: il punto di points che e' il vertice del guscio convesso seguente start in senso antiorario (cioe' risalendo).

Variabili locali

• p: un punto dell'insieme points

Pseudocodice della procedura di ricerca

Procedure NextHullPointUp(input: start, point, output: next)
begin
  next = scorri l'insieme points dall'inizio fino a trovare un 
         punto con ordinata maggiore di start oppure con ordinata
         uguale ed ascissa minore di start;
  p = next;
  repeat
  begin  
     p = scorri l'insieme points dalla posizione dopo next fino a
         trovare un punto con ordinata maggiore di start oppure con
         ordinata uguale ed ascissa minore di start;
     if p esiste then
     begin
       controlla la terna (start, next, p);
       if (svoltano a destra) OR 
          ( (sono allineati) AND 

            (dist(next,start)<dist(p,start)) )
       then next = p;
     end if
  end
  while l'insieme points non e' stato esaminato tutto
  return next;
end

• il punto start in ingresso sta sulla parte sinistra del guscio convesso
• considera i punti con ordinata minore o uguale a start anziche' maggiore o uguale

Strutture dati ed operazioni ausiliarie

Su tale lista sono necessarie almeno le operazioni:

• Inizializzazione della lista vuota
• concatenazione di un elemento in coda a una lista

Notare che, non essendo necessaria la cancellazione di elementi dalla lista, la lista puo' essere semplicemente linkata (non bidirezionalie). Per supportare efficientemente l'aggiunta di un punto in coda e' necessario l'uso di un puntatore alla coda della lista.

Se si implementa l'insieme points ad array, nella lista possono essere memorizzati gli indici dei corrispondenti punti anziche' i punti stessi.

Primitive fondamentali sono il calcolo dell'orientamento di una terna di punti che avete implementato nell'esercitazione guidata. [BINARY]