In questi giorni sto realizzando una applicazione di dataentry web, che sarà il primo step di un progettone rivolto all'archeologia. La mia applicazione si occupa di raccogliere le informazioni di migliaia (centinaia di migliaia per la precisione) di unità stratigrafiche, imputate dagli archeologi di campo che effettuano gli scavi.

Uno dei successivi step del progetto prevede di rielaborare le informazioni "spaziali" di queste unità. In particolare c'è un problemino che mi si prospetta, che deriva dal metodo di lavoro degli archeologi. Quando un archeologo rimuove una unità stratigrafica, ovvero una porzione di terra, un sasso, un reperto, etc... tipicamente rileva la sua posizione segnando alcuni punti sulla superficie dell'unità, il cui numero dipende in realtà dalle dimensioni dell'unità stessa.

Il problema è che questi "punti" stanno tutti sulla superficie "superiore" e mai su quella inferiore, come si vede dal seguente schizzo della sezione.

Lo schema è bidimensionale, ma occorre tenere presente che in realtà i punti sono sparsi in uno spazio tridimensionale.

Ora, il problema informatico è il seguente: dati i punti delle unita stratigrafiche US0, US1 e US2 ed una relazione di tipo "sta sopra", "sta sotto" che lega le unità che sono a contatto tra loro, determinare la superficie sottostante dell'unità US1 allo scopo di ottenere un volume chiuso.

Io qualche ideuzza ce l'ho, ma accetto ogni tipo di suggerimento, compreso "licenziati che fai prima".

powered by IMHO 1.2


Commenti (6) -

# | Adrian Florea | 04.03.2005 - 22.40

Secondo me la relazione "<=" (sta sotto) è fra i punti delle unità stratigrafiche e non fra le unità stratigrafiche.

Così, potresti considerare che la coppia dell'insieme dei punti di rilievo con la relazione "<=" fanno un insieme parzialmente ordinato (un poset) e l'unità stratigrafica diventa un sottoinsieme totalmente ordinato (una catena).

Il tuo problema si riduce quindi a quello di determinare la partizione minima di catene di un poset (che dovrebbe essere un algoritmo conosciuto).

# | Luca Minudel | 04.03.2005 - 23.04

la struttura che descrivi è fatta di nodi ed archi che uniscono i nodi ed è detta grafo.



il primo passo è verificare che il grafo sia effettivamente piano (ossia sia possibile "disegnarlo su carta" senza dover incrociare archi uno sopra l'altro). se non è piano... la cosa si complica ancora di più. per verificare se è piano... c'è un semplice teorema.



ora un grafo piano determina delle superfici quando ha dei circuiti (una sequenze di nodi connessi da archi che parte da un nodo e orna sullo stesso nodo). anche qui c'è un teorema che dice come verificare se esistono circuiti.



trovare il cammino ora è un problema di ricerca operativa. i nodi con un solo arco (quindi uniti solo ad un altro nodo) non ti interessano (puoi elmininarli). se ti restano solo nodi con due archi hai 1 solo cammino (e quindi una sola superficie). se invece hai nodi con 3 o più archi puoi avere + cammini. qui l'algoritmo di Dijkstra potrebbe aiutarti.



per il sopra e sotto, devi definire una superficie di riferimento e calcolare la distanza dai nodi alla superficie.



HTH

# | robymes@hotmail.com (Roberto Mes | 04.03.2005 - 23.31

scusa Andrea, una curiosità puramente curiosa : in questo progettone avrete anche a che fare con i GIS, oppure si tratta di un progetto puramente din interfacce utente alfanumeriche?

saluti

# | Adrian Florea | 04.03.2005 - 23.40

Mi rendo conto adesso che, quando rilevi un'unità stratigrafica, i suoi punti di rilievo si dovrebbero "<="-are con punti di rilievo di unità stratigrafiche precedenti - da qui, forse, la tua relazione tra unità e non tra punti...



P.S.: Andrea, la rete di questo cliente ha uno stupido problema: per questo i miei commenti arrivano 2-3 volte quando posto dal lavoro. Potresti per cortesia cancellare tu i commenti doppiati? Grazie e scusami...

# | Andrea Boschin | 05.03.2005 - 00.41

Ok, mi rendo conto che probabilmente ho espresso male il problema (per quanto io sia un programmatore non sono nemmeno lontanamente un teorico, perciò perdonatemi...); Detto questo ecco alcune precisazioni:



1) Adrian, nel tuo ultimo commento hai centrato la questione. I punti vengono raccolti tutti assieme e appartengono tutti alla stessa unità stratigrafica e la relazione si applica all'unità e non ai punti. Purtroppo la relazione di "sta sotto" è più un concetto "umano" che "formale" infatti riconducendomi allo schema se ipotizzi che il punto più alto della US2 sia più alto di quello della US1, ti renderai conto che esso pur "stando sopra" in realtà viene considerato come "stante sotto", perchè "visivamente" la US2, nel punto di contatto è sotto alla US1. (ho abbondato di virgolette ma creo sia chiaro).



2) Luka, non mi è chiaro con esattezza cosa tu identifichi con "nodo" e cosa con "arco", ma mi sembra di capire che 1 nodo = 1 punto e 1 arco = unione di due punti. Detto questo devo approfondire il tuo metodo, però devi considerare che stiamo parlando di una supeficie tridimensionale e non di un arco come lo si vede nella sezione in figura. Questo implica che da un nodo partano n archi, ma credo anche che imponga che il grafo sia per forza di cose piano se uso il metodo classico di definizione di una superficie "per triangoli". Ti diro comunque che ho già informato il cliente che per risolvere il problema, ho bisogno di due punti di riferimento che mi permettano di avere un Vettore G che mi dia un orientamento alla nube di punti (pura intuizione).



3) Roberto. La risposta giusta è "Ni". Per ora non si parla di GIS, ma come hai facilmente intuito prima o poi ne avrò a che fare...

# | robymes@hotmail.com (Roberto Mes | 05.03.2005 - 01.34

Per qualsiasi suggerimento/chiacchera da bar/curiosità/amenità sul GIS fammi pure un fischio, mi farà piacere scambiare due parole in merito!

saluti

Aggiungi Commento