Salve a tutti, qualcuno di voi è un esperto in prolog e lisp in grado di realizzare del codice relativo alle seguenti specifiche ?
Introduzione
Il calcolo delle chiglie convesse (convex hulls) è uno degli algoritmi fondamentali della geometria
computazionale. L’algoritmo ha numerosissime applicazioni e, una volta implementate correttamente
alcune primitive geometriche, è di una semplicità sorprendente.
Definizioni
Dato un insieme di punti P, l’insieme è convesso se, presi due qualunque punti p e q ? P, il segmento
pq è completamente all’interno di P. La convex hull di P è il più piccolo insieme convesso che
contiene tutti i punti di P. Nel seguito useremo la notazione CH(P) per indicare la convex hull di P
1
.
La CH(P) ha le seguenti proprietà.
• È la forma più semplice che “approssima” un insieme di punti.
• È il perimetro più corto che delimita P.
• È il poligono di area minore che copre tutti i punti di P.
Intuizione
Il dispositivo “meccanico” per calcolare CH(P) è costituito da una tavola di legno, chiodi, martello ed
un elastico.
1
Tutte le figure sono tratte dalle slides dei corsi di Sedgewick su Algoritmi e Strutture Dati di Princeton.2/5
Soluzioni
Vi sono molte soluzioni al problema del calcolo di CH(P). Se consideriamo un insieme di punti P come
input con |P| = N, allora il miglior algoritmo ha complessità temporale O(Nlg(N)). Una sua
implementazione usa il cosiddetto “Graham’s Scan” (la scansione di Graham).
Si sceglie il punto s ? P con l’ordinata minore (in caso di pareggio si sceglie quello con l’ascissa
minore).
Si ordinano i rimanenti punti secondo l’angolo polare che formano con s, in modo da ottenere un
poligono semplice (anche se non convesso).
Si considerano i punti in ordine e si scartano quelli che imporrebbero una “svolta a destra”.
Figura 1: I punti da cui bisognerebbe svoltare a destra sono scartati.
L’algoritmo è molto semplice, ma richiede l’implementazione molto attenta di una serie di primitive
geometriche. Scopo del progetto è di implementare tutte queste primitive e l’algoritmo per il calcolo
della CH(P).
Preliminari
Le primitive geometriche sono molto complesse da realizzarsi correttamente. Per il momento ci si
limiterà a punti nel piano a 2D con coordinate intere (questo vincolo è fondamentale).
L’interfaccia CL richiesta è la seguente
make-point x y ? point-2D
x point-2D ? <integer coordinates>
y point-2D ? <integer coordinate>3/5
La rappresentazione interna di un punto è lasciata alla vostra immaginazione. Comunque devono
valere le seguenti uguaglianze:
cl-prompt> (x (make-point 0 42))
0
cl-prompt> (y (make-point 42 123))
123
Per il Prolog le cose sono relativamente più semplici. Potete usare direttamente il meccanismo di
unificazione per gestire i punti ed estrarre le loro coordinate. Ovvero, potete usare il termine
pt(X, Y) per rappresentare un punto.
A questo punto avete bisogno di primitive geometriche più raffinate. In particolare dovrete
implementare il test “svolta a sinistra”. Avrete bisogno delle funzioni/predicati seguenti descritti di
seguito.
Area di un triangolo
Implementate una funzione area2 che calcoli l’area di un triangolo date le coordinate dei vertici. Dati
tre punti, a, b, e c (vertici del triangolo) si suggerisce di usare la formula:
2×A(a,b,c)=((
x(b)-x(a))
×(
y(c)-y(a)))
-((
y(b)-y(a))
×(
x(c)-x(a)))
Notate che il valore può essere negativo (quando i 3 punti sono ordinati in senso orario), il che è in
realtà molto utile: se il valore è positivo, allora
€
?abc è un angolo a sinistra, se è negativo allora
€
?abc è un angolo a destra. Il caso 0 è degenere e capita quando a, b e c sono collineari. Il capitolo 1
di [O98] spiega bene tutti i dettagli. Dato che il nostro interesse non è calcolare l’area del triangolo ma
capire se un certo angolo è legato a una “svolta a destra” non è necessario fare la divisione per 2 finale.
area2 a b c ? integer
In Prolog dovreto implementare il predicato
area2(A, B, C, Area)
Funzioni e predicati left, left-on, is-collinear, left/3,
left_on/3, collinear/3
Data la funzione area2, si possono scrivere i predicati:
left a b c ? boolean
left-on a b c ? boolean
is-collinear a b c ? boolean
che ci dicono se i tre punti rappresentano una svolta a sinistra oppure no.
In Prolog avrete i predicati:
left(A, B, C)
left_on(A, B, C)
collinear(A, B, C)
Angolo tra due punti
Infine avrete bisogno di una funzione angle2d che ritorni l’angolo (in radianti) tra due punti. Avete
bisogno di una funzione standard della libreria Common Lisp.
angle2d a b ? real ? [-p,p].
In Prolog il predicato diventa:
angle2d(A, B, R).4/5
Chiglia convessa
Date le funzioni di cui sopra potete implementare tranquillamente l’algoritmo per la costruzione di
CH(P).
ch points ? result
La variabile points(ovvero P) contiene una lista di punti, il risultato result (ovvero CH(P)) è anch'esso
una lista di punti.
In Prolog:
ch(Points, Result)
Altri suggerimenti
Avrete bisogno della funzione standard Common Lisp sort. Secondo il tipo d’implementazione che
sceglierete di fare potreste avere bisogno di push, pop e loop.
In Prolog potete usare il predicato sort (attenzione a com’è definito questo predicato in Prolog!)
Input (e Output)
Il vostro progetto deve prevedere anche una funzione (un predicato) che legga da file una serie di punti.
read-points filename ? points
filename è un nome di file e points è una lista di punti.
Il contenuto di filename è costituito da un numero pari d’interi, due per riga. Ad esempio questo è un
file di test corretto:
0 6
3 7
4 6
3 4
5 0
42 123
-1 0
1024 -42
0 -2
1 2
Attenzione ai punti duplicati.
In Prolog:
read_points(Filename, Points).
L’implementazione di read_points/2 in Prolog va fatta con attenzione, sfruttando tutte le
primitive di lettura e scrittura disponibili; in particolare si raccomanda di non perdere tempo leggendo
il file carattere per carattere al fine di ricostruire manualmente i numeri. Per facilitare la lettura del file
con i punti per Prolog vi suggeriamo di usare il seguente formato:
pt(0, 6).
pt(3, 7).
…
pt(42, 123).
Valutazione
Il vostro programma sarà controllato con set di files assolutamente arbitrari (di cui almeno uno
totalmente casuale), quindi, dovrete essere pronti a ogni evenienza.
I tests, dato un filename, sono costituiti da espressionisiffatte:
Lisp:
cl-prompt> (equalp expected-result (ch (read-points filename)))
Prolog:
?- read_points(Filename, Points),
ch(Points, CH),
CH = Expected_result.
La CH(P) è deterministica e quindi la sua struttura non cambia a seconda dell’implementazione sulla
base delle primitive proposte. Un’implementazione in conformità a primitive diverse non sarà
considerata. In particolare, il vincolo sul tipo dei numeri da usare (interi) fa si che non ci siano
problemi sul test di uguaglianza tra numeri.
Notate che vi sono diversi algoritmi per il calcolo di CH(P). L’algoritmo semplice e brutale ha
complessità O(N
3
), dove N è il numero di punti in ingresso. I correttori non hanno intenzione di
aspettare troppo per valutare ogni elaborato (i test si possono lanciare in automatico, magari con input
di oltre 100 punti)… quindi è meglio che implementiate degli algoritmi più efficienti.
Abbiamo a disposizione una serie di esempi standard che saranno usati per una valutazione oggettiva
dei programmi. In particolare, i files di test che useremo hanno un numero di punti dell’ordine di 102
e
sono generati in modo casuale.
Se i files sorgente non potranno essere letti/caricati negli ambienti Lisp (e Prolog; nb.: non
necessariamente Lispworks e SWI-Prolog), il progetto non sarà ritenuto sufficiente.
Il mancato rispetto dei nomi indicati per funzioni e predicati, o anche delle strutture proposte e della
semantica esemplificata nel testo del progetto, oltre a comportare ritardi e possibili fraintendimenti
nella correzione, può comportare una riduzione nel voto ottenuto o la non correzione dell’elaborato.