Progetto di I.U.M. Modellazione Geometrica

Alternativa 2: Algoritmo QuickHull

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

left e right punto di ascissa minima e massima dell'insieme points.
left_subset, right_subset insiemi di punti passati alle chiamate della procedura ricorsiva
left_hull, right_hull liste ordinate di punti, il risultato delle chiamate alla procedura ricorsiva

Pseudocodice

Algorithm QuickHull(input: points, output: hull)
 begin
    left = punto di ascissa minima in points;
    right = punto di ascissa massima in points;
    left_subset = insieme vuoto;
    right_subset = insieme vuoto;
    for (ogni punto p in points)
       begin
         if ( la terna di punti left,right,p 
              definisce una svolta a sinistra )
            inserici p in left_subset;
         if ( la terna di punti left,right,p 
              definisce una svolta a destra )
            inserici p in right_subset;
         /* altrimenti nulla: sappiamo gia' che p non e'
            vertice del guscio convesso */
       end
  Recursive(left,right,left_subset,&left_hull);
  Recursive(right,left,right_subset,&right_hull);
  hull = concatenazione di right + left_hull + left + ritgh_hull;

Dove viene usata la funzione ausiliaria Recursive, dettagliata piu' avanti.

Differenza rispetto a quanto scritto nelle dispense

Nella versione delle dispense, le liste risultato delle chiamate alla funzione Recursive contenevano anche i due punti left e right, ed era poi necessario evitare la duplicazione di questi punti quando si ricombinavano i risultati parziali.

Qui e' sembrato piu' semplice fare si' che i risultati parziali non contenessero questi due punti, che pertanto devono essere inseriti esplicitamente al momento della ricombinazione.

La procedura ricorsiva

Parametri di ingresso

source e dest: due punti nel piano
work: un insieme di punti giacenti tutti alla sinistra della retta orientata da source a dest

Parametri di uscita

partial_hull: lista ordinata dei punti di work che appartengono al guscio convesso dell'insieme originale points, ordinati consistentemente con l'ordinamento antiorario del guscio convesso.

Variabili locali

far: punto dell'insieme work avente distanza massima dalla retta per source e dest
aux1, aux2: insiemi di punti passati alle chiamate ricorsive
partial1, partial2: liste di punti, risultato delle chiamate ricorsive

Pseudocodice della procedura ricorsiva

Procedure Recursive(input: source, dest, work, 
                    output: partial_hull)
{
  partial_hull = lista vuota;
  if ( l'insieme work non e' vuoto )
  {  
     aux1 = insieme vuoto;
     aux2 = insieme vuoto;
     far = FarthestPoint(source,dest,work);
     for ( ogni punto p in work )
       begin
         if ( la terna far,dest,p definisce svolta a sinistra )
            inserisci p in aux1;
         if ( la terna source,far,p definisce svolta a sinistra )
            inserisci p in aux2;
       end
     Recursive(far,dest,aux1,&partial1);
     Recursive(source,far,aux2,&partial2);
     partial_hull = concatenazione di partial1 + far + partial2;
  end

Dove e' usata la funzione ausiliaria FarthestPoint che seleziona il punto far avente distanza massima dalla retta per source e dest, descritta piu' avanti.

Differenza rispetto a quanto scritto nelle dispense

Come osservato a proposito della funzione principale, anche qui il punto far non e' contenuto nelle liste rislutato delle chiamate risorsive, e quindi deve essere aggiunto esplicitamente.

Questa scelta e' sembrata piu' semplice rispetto a quella riportata sulle dispense (dove poi era necessario eliminare il punto far da una delle due liste prima di concatenarle).

Selezione del punto di distanza massima

Il punto, nell'insieme work, avente distanza massima dalla retta source-dest, viene selezionato come il punto p che massimizza l'area del triangolo source,dest,p.

Questa condizione e' equivalente a quella di massima distanza dalla retta in quanto il triangolo ha come base il segmento source-dest (sempre uguale, indipendentemente da p) e come l'altezza la distanza di p dalla retta.

Confrontare le aree dei triangoli equivale a confrontare i valori assoluti dei determinanti associati alle terne di punti source,dest,p (lo stesso determinante di cui si stima il segno per calcolare l'orientamento della svolta).

Questo perche' tale determinante in valore assoluto e' uguale all'area del parallelogramma di vertici p,source,dest,p+source-dest, area che e' esattamente doppia di quella del triangolo source,dest,p.

Nel caso piu' punti di work (per esempio due: p1 e p2) abbiano distanza massima dalla retta source-dest, si sceglie, per esempio, quello piu' a destra. A tale scopo, si controlla l'orientamento della terna di punti source,p1,p2.

Pseudocodice per il punto di distanza massima

Function FarthestPoint(input: source, dest, work, output: far)
 begin
   area = -1;
   for ( ogni punto p in work )
     begin
      aux = fabs( determinante della terna di punti source,dest,p )
      if (aux>area) 
        begin  area = aux; far = p;  end
      else if (aux==area) and 
              ( la terna source,far,p definisce una svolta a destra )
             begin  area = aux; far = p;  end
     end
   return far;
 end

Strutture dati ed operazioni ausiliarie

Sono necessarie liste linkate di punti per rappresentare il risultato finale hull ed i risultati intermedi delle chiamate alla procedura ricorsiva (left_hull, right_hull, partial1, partial2).

Su tali liste sono necessarie almeno le operazioni:

Inizializzazione della lista vuota
concatenazione di due liste e concatenazione di un elemento in coda a una lista (usate per la combinazione dei risultati parziali)

Notare che, grazie alla variante adottata rispetto alle dispense, non e' necessaria la cancellazione di elementi da tali liste. Quindi, le liste possono essere semplicemente linkate (non bidirezionali). Per supportare la concatenazione e' pero' necessario l'uso di un puntatore alla coda della lista.

Gli insiemi di punti ausiliari left_subset, right_subset, aux1, aux2 possono anch'essi essere implementati come liste. Su tali liste sono necessarie l'operazione di inizializzazione, di inserimento di un elemento, e di scansione degli elementi. Si puo' ultilizzare lo stesso tipo di lista usato per hull e per i risultati delle procedure ricorsive.

La struttura dati per l'insieme points puo' essere un array.

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

Primitive fondamentali sono il calcolo del determinate associato ad una terna di punti, ed il calcolo dell'orientamento di una terna di punti che avete implementato nell'esercitazione guidata.