Strutture Dati: SP-Sesquigrafo?

[PGI]

Premetto che ho le idee abbastanza confuse poichè termino or ora la lettura di un libro sulle strutture dati che allinea novecento pagine con indice di comprensibilità 3 (dove 0 è il bustrofedico e 10 topolino).

Vorrei evitare di reinventare l'acqua calda, quindi chiedo a voi se esista una struttura dati avente le caratteristiche che seguono.

Scopo: ripartizione di uno spazio tridimensionale in volumi cubici di pari dimensioni. Ogni vertice di quello che dovrebbe essere un grafo, rappresenta un cubo appartenente a questo spazio ed è identificato dal baricentro (nX, nY, nZ). Ogni vertice ha 6 lati.

Il tutto per poter ottenere, con altre magie, un algoritmo O(1) che trovi per un punto P(x,y,z) la regione di spazio a cui appartiene.

Nei libri che ho per le mani il caso su esposto appartiene al ramo dei grafi generici. Insomma, un "Sesquigrafo di ripartizione dello spazio" non sembra aver destato molto interesse negli studiosi :D. Non è che qualcuno ha per mani uno studio su un caso simile, risolto con una bella struttura dati precotta, possibilmente disponibile in rete (aggiungo, che non sia un albero BSP)?

Ciao.

[a2000]

sì.
geometria analitica 1.

[a2000]

ma com'è che non sapete un ca@@o ! :confused:

anche le cose più semplici e banali.

poi per "non reinventarsi l'acqua calda" (e in realtà perchè non si conosce una beneamata minchia) si mettono 100 righe di codice, 10 dll 10 volte la memoria e il tempo di calcolo per fare quello che si fa istantaneamente con 5 istruzioni.

[a2000]

comunque è confortante: in italia non riusciranno a fare un altro ground zero ...... c'è già ! :D

[/\/\@®¢Ø]

Originariamente inviato da PGI
Il tutto per poter ottenere, con altre magie, un algoritmo O(1) che trovi per un punto P(x,y,z) la regione di spazio a cui appartiene.

Come ha fatto velatamente intendere a2000, il problema e' banale se consideri regioni cubiche (e' sostanzialmente come trovare la parte intera di un numero reale). Se invece ti serve qualcosa di piu' generale, nel tuo libro (quale e' ?) piu' che nella sezione dei grafi controlla in quella dedicata alla geometria computazionale. Dovresti trovare cio' che ti serve.

[PGI]

Gentilissimo a2000, generalmente non comprendo bene ciò che dici, mi pare di averlo già ricordato una volta. Carenze mie, hai una sintassi articolata, merito tuo.

In questa occasione tuttavia credo di aver ben compreso.

Del tutto evidente che "non reinventarsi l'acqua calda" significhi che io abbia una vaga idea di quello di cui parlo, chè se fossi certo non affronterei il rischio della tua scortesia chiedendo se esistano soluzioni che già risolvono un problema tanto elementare da essere offensivo. Mi era parso altresì di averlo sottolineato in apertura, è tuttavia possibile che tu scriva meglio di quanto non legga.

Quantomeno il beneficio del dubbio avresti potuto concedermelo, forse avrei studiato le soluzioni proposte cercando di impararle, non aver fatto studi scientifici non agevola (rimedierò a breve) ma impegnarsi riduce il divario.

Per la disastrosa situazione in cui si troverebbe l'informatica nazionale mi sento di rassicurarti. Non sono un programmatore professionista nè saltuario, batto le dita sulla tastiera per diletto: la mia ignoranza non contribuirà al cumulo di macerie e ad esserne certo chiederò di essere rimosso dal forum. Il rischio è grande non vorrei essere responsabile involontario di un peggioramento della situazione.

Naturalmente frequenterò con ansia i siti accademici di divulgazione attendendo il tuo contributo alla rifondazione dell'informatica.

Ciao.

Pierluigi.

[/\/\@®¢Ø]

Originariamente inviato da PGI
Scopo: ripartizione di uno spazio tridimensionale in volumi cubici di pari dimensioni. Ogni vertice di quello che dovrebbe essere un grafo, rappresenta un cubo appartenente a questo spazio ed è identificato dal baricentro (nX, nY, nZ). Ogni vertice ha 6 lati.

Come dicevo prima, se i cubi sono tutti uguali non e' molto difficile.
Per semplificare consideriamo cubi tutti di dimensionue unitaria e centrati su coordinate intere.
A questo punto trovare le coordinate del baricentro del cubo a cui un punto appartiene e' sufficiente arrotondare le coordinate ai valori interi piu' vicini.
Il punto (0.2 , 10.3, -4.8) apparterra' al cubo con baricentro in (0,10,-5).
Ad esempio in python

def find_cube( x , y , z ):
return ( round(x) , round(y) , round(z) )

Tutto qui !
Per lati di dimensione differente o con centri in posizione un po' differente e' sufficiente un cambio di coordinate.

[a2000]

Originariamente inviato da PGI
....


sorry.

ma ci vuole rispetto, oltre che per le persone, anche per le cose e la seconda "cosa" è il cubo :)

[a2000]

Originariamente inviato da PGI
...
chiederò di essere rimosso dal forum.
...


senti, sono veramente dispiaciuto.

comunque anche se le "cose" vanno rispettate sono sempre le cose per le persone e non viceversa.

penso che tu possa rivedere la tua decisione.