Progetto di I.U.M. Modellazione Geometrica

Alternativa 1: Algoritmo di Graham

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

center: punto nel piano (rappresenta un punto interno al guscio convesso, usato come centro per calcolare un ordinamento radiale dei punti dati).
la stessa lista hull (parametro di uscita) viene usata temporaneamente per contenere un poligono inizialmente non convesso, che verra' gradatamente trasformato nel guscio convesso dell'insieme di punti dati.

Pseudocodice

Algorithm Graham(input: points, output: hull)
 begin
    center = FindInternalPoint(points);
    RadialSort(center,points,hull);
    GrahamScan(hull);
 end

Dove sono usate le funzioni ausiliarie:

FindInternalPoint: trova un punto interno al guscio convesso dell'insieme di punti points.
Si puo' semplicemente prendere il baricentro dell'insieme.
RadialSort: ordina i punti di points radialmente in senso antiorario attorno al punto center ed inizializza la lista hull con i punti di points cosi' ordinati.
All'uscita da RadialSort, la lista hull rappresenta un poligono, non necessariamente convesso, che sara' successivamente trasformato nel guscio convesso mediante eliminazione di vertici.
Il funzionamento di RadialSort e' dettagliato piu' avanti.
GrahamScan: implementa la scansione di Graham, che modifica la lista hull eliminando da essa i punti che non sono vertici del guscio convesso di points.
All'uscita da GrahamScan, la lista hull rappresenta un poligono convesso, che e' il guscio convesso di points.
Il funzionamento di GrahamScan dettagliato piu' avanti.

Calcolo dell'ordinamento radiale

Suggerimento

Si puo' utilizzare la funzione qsort delle librerie standard C, che implementa l'algoritmo di QUICKSORT (nota: questo e' solo suggerimento, non deve essere inteso come vincolante).

A tale scopo e' necessario che i punti da ordinare siano contenuti in un array, quindi e' conveniente implementare l'insieme points come un array.

Inoltre bisogna fornire una funzione di confronto che, dati due punti, ritorna:

-1 se il primo punto precede il secondo
+1 se il secondo punto precede il primo
0 se i due punti coincidono

La dichiarazione C della funzione di confronto deve essere del tipo:

int ComparePoints(const void* arg1, const void* arg2)

dove arg1 e arg2 sono dichiarati come puntatori generici (tipo void*), ma saranno in pratica puntatori al tipo che implementa un punto.
Internamente alla funzione ComparePoints, verra' fatto un cast da puntatori generici a puntatori a punti.
Per esempio, supponendo che nel nostro programma un punto sia implementato come un array di due float, le prime linee della funzione ComparePoints conterranno due istruzioni del tipo:

  float * p1 = (float *)(arg1);
  float * p2 = (float *)(arg2);

Invece supponendo che sia implementato come indice intero in un array, convertiremo:

  int i1 = *(int *)(arg1);
  int i2 = *(int *)(arg2);

dopo di che all'interno della funzione si useranno le variabili p1 e p2.

Funzione di confronto fra due punti

Quale che sia l'algoritmo di ordinamento utilizzato (qsort delle librerie C, o una funzione scritta da voi), e' necessaria una primitiva che, dati due punti p1 e p2, stabilisca quale dei due precede l'altro:

se la coordinata radiale theta1 di p1 (in un sistema di coordinate radiali centrato nel punto center) e' minore della coordinata radiale theta2 di p2, allora p1 precede p2.
se la coordinata radiale theta1 di p1 e' maggiore della coordinata radiale theta2 di p2, allora p2 precede p1.
se le coordinate radiali theta1 e theta2 sono uguali, allora la discriminazione fra p1 e p2 avviene basandosi sulla distanza da center: se la distanza center-p1 e' minore della distanza center-p2, allora p1 precede p2, altrimenti p2 precede p1.

L'implementazione della funzione di confronto non calcola le coordinate radiali theta1 e theta2. Invece si basa sul controllo delle svolte.

Precisazione rispetto a quanto scritto nelle dispense

E' stato detto che il controllo se l'angolo theta1 e' minore (maggiore) di theta2 equivale al controllo se la terna di punti center,p1,p2 definisce una svolta a sinistra (a destra).
In realta' questo vale solo se la differenza in valore assoluto fra theta1 e theta2 e' minore di 180 gradi.

Nel caso generale e' opportuno prima distinguere il quadrante in cui giacciono i punti p1 e p2 rispetto a center. Dato un sistema di assi cartesiani con origine in center, numeriamo i quattro quadranti nel modo usuale:

     |
  2  | 1
-----+-----
  3  | 4
     |

Se il quadrante di p1 e' minore del quadrante di p2, allora p1 precede p2 (e viceversa).
Se p1 e p2 giacciono nello stesso quadrante, allora possiamo operare il controllo sull'orientamento della terna perche' certamente la differenza degli angoli theta1 e theta2 e' minore di 180 gradi.

Se i punti center, p1 e p2 sono allineati, non e' necessario calcolare le distanze center-p1 e center-p2, ma si possono operare controlli sulle coordinate x ed y separatamente, in base al quadrante nel quale ci troviamo.

Pseudocodice della funzione di confronto

Function ComparePoints(input: p1, p2)
 begin
   q1 = quadrante di p1 rispetto a center;
   q2 = quadrante di p2 rispetto a center;
   if (q1<q2) return "p1 precede p2";
   if (q2<q1) return "p2 precede p1";
   /* altrimenti sono nello stesso quadrante, controllo la svolta */
   if (la terna di punti center,p1,p2 definisce una svolta a sinistra) 
      return "p1 precede p2";
   if (la terna di punti center,p1,p2 definisce una svolta a destra)
      return "p2 precede p1";
   /* altrimenti sono allineati, controllo le distanze */
   diff_x = p2.x - p1.x;
   diff_y = p2.y - p1.y;
   switch (q1) /* a seconda del quadrante, nota che q1==q2 */
      begin
        case 1:
         if (diff_x>0) or (diff_y>0) return "p1 precede p2";
         else return "p2 precede p1";
        case 2:
         if (diff_x<0) or (diff_y>0) return "p1 precede p2";
         else return "p2 precede p1";
        case 3:
         if (diff_x<0) or (diff_y<0) return "p1 precede p2";
         else return "p2 precede p1";
        case 4:
         if (diff_x>0) or (diff_y<0) return "p1 precede p2";
         else return "p2 precede p1";
      end
 end

Scansione di Graham

Idea

Esaminare successivamente terne di vertici consecutivi sul contorno del poligono corrente. Se l'angolo da essi formato e' concavo, eliminare il punto centrale della terna.

Il poligono corrente e' quello contenuto nella lista hull. Tale lista deve essere implementata come una lista circolare linkata bidirezionalmente. Vedere anche piu' avanti.

Nelle dispense si e' detto che:

si inizia a scandire la lista da un punto
per ogni terna esaminata (formata dal punto corrente e dai due successivi):
- (1) se la terna definisce una svolta a sinistra (angolo convesso), si avanza sull'elemento successivo della lista
- (2) altrimenti (angolo concavo), si elimina il punto centrale della terna (nella lista, e' l'elemento successivo a quello corrente) e si arretra sull'elemento precedente nella lista
si termina quando si giunge nuovamente al punto iniziale.

Precisazione rispetto a quanto scritto nelle dispense

Il criterio di uscita dal ciclo della scanzione di Graham non e' esattamente quello detto sopra.

L'intenzione e' quella di terminare quando si e' giunti al punto di partenza dopo aver esaminato tutta la lista muovendosi all'avanti.

Invece, con la condizione di terminazione scritta sopra, puo' succedere di tornare al punto di partenza arretrando in seguito alla cancellazione di vertici. In questo caso non bisogna terminare.

Condizione di terminazione rivista

Sia N il numero di vertici di hull al momento di iniziare la scansione.

Osservazione: Ho compiuto un ciclo completo sul poligono se ho eseguito il caso (1) esattamente N volte.

E' facile verificarlo considerando i due casi:

Tutti i punti appartengono al guscio convesso. All'inizio della scansione hull rappresenta gia' un poligono convesso. Nessun vertice viene eliminato, si esegue sempre il caso (1), avanzando sul vertice successivo. Dopo N avanzamenti sono di nuovo al punto di partenza.
Il guscio convesso dei punti ha K vertici, con K minore di N. Durante la scansione, da hull vengono eliminati N-K vertici, eseguendo altrettante volte il caso (2). Ogni volta che il caso (2) viene eseguito, si arretra di un vertice, quindi per riavanzare dovro' eseguire una volta il caso (1). Inoltre, per compiere un giro completo del guscio convesso finale tornando al punto di partenza, dovro' eseguire K volte il caso (1). In totale, il passo (1) e' eseguito N-K+K=N volte.

E' conveniente introdurre un contatore, inizializzato a 0 prima di cominciare la scansione, che viene incrementato di 1 ogni volta che si esegue il caso (1). La scansione termina quando il valore del contatore raggiunge N+1.

Pseudocodice della scansione di Graham

Procedure GrahamScan(input/output: hull)
 begin
  pos1 = prima posizione nella lista hull;
  count = 0;
  num = numero di elementi in hull;
  repeat
    pos2 = posizione succesisva a pos1 in hull;
    pos3 = posizione succesisva a pos2 in hull;
    p1 = il punto contenuto nella posizione pos1;
    p2 = il punto contenuto nella posizione pos2;
    p3 = il punto contenuto nellaposizione pos3;
    if ( la terna p1,p2,p3 definisce una svolta a sinistra )
       pos1 = posizione succesisva a pos1 in hull;
       count++;
    else
       cancella la posizione pos2 da hull;
       pos1 = posizione precedente a pos1 in hull;
  until ( count == num+1 );
 end

Strutture dati ed operazioni ausiliarie

La principale struttura dati ausiliaria e' la lista circolare linkata bidirezionalmente di punti che implementa hull.

Su tale lista sono necessarie almeno le operazioni:

Inizializzazione della lista vuota ed inserimento di un elemento (usate per costruire hull come lista dei punti ordinati radialmente)
Selezione della prima posizione (punto di partenza per la scansione di Graham)
Selezione della posizione precedente e a quella successiva ad una posizione data
Accesso al punto contenuto in una posizione della lista
Cancellazione di una posizione dalla lista

La struttura dati per l'insieme points puo' essere un array (scelta conveniente anche in considerazione del fatto che su tale insieme va applicato un algoritmo di ordinamento, vedere anche sopra).

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

Primitiva fondamentale e' il calcolo dell'orientamento di una terna di punti che avete implementato nell'esercitazione guidata.