[C] rappresentazione dello spazio infinito

[teju]

Devo rappresentare dei rettangoli nello spazio infinito bidimensionale.

Questi quadrati sono determinati da due punti A(a, b) e B(c, d), dove A è l'estremo sinistro basso del rettagolo e B è l'estremo destro alto.

Mi servirà poi trovare il rettangolo più vicino in alto, in basso e a sinistra e destra, ad un punto dato C(e, f).

Una lista di elementi con dentro le coordinate dei punti A e B è la struttura ovviamente più semplice da realizzare, ma la ricerca del rettangolo più vicino implica ogni volta leggere tutta la lista...

Avevo anche pensato ad un albero binario, ordinato su "a", se uguali su "b", se uguali su "c" e infine ancora se uguali su "d", ma così facendo ho facilità a fare la ricerca del rettangolo più vicino a destra ma lo stesso per le ricerche a sinistra, alto e basso devo scorrere tutto l'albero...

Avevo a questo punto pensato a 4 alberi costruiti sugli stessi elementi, ovvero ogni elemento ha il puntatore sinistro e destro per l'albero ordinato secondo la "a", secondo la "b", secondo la "c" e secondo la "d", ma così facendo la cancellazione del rettangolo è un casino assurdo!!!!

idee di implementazione??

[unomichisiada]

Io applicherei la stessa tua idea dell'albero binario multipuntatore ad una lista ordinata.In altre parole costruirei ciascun

nodo della quale contenente 4 puntatori,ad esempio left,right,bottom e up,seguendo il primo si otterrebbe la lista dei nodi

ordinati rispetto alla sinistra,seguendo il secondo alla destra e così via...Ovviamente la lista la devi mantenere ordinata

inserendo in modo ordinato rispetto a ciascuna catena di puntatori,anche la cancellazione deve preservare l'ordine rispetto a

tutte e quattro le catene.La ricerca in questo modo diventa ultra efficiente perchè il più vicino è sempre la testa della

lista,la cancellazione e l'inserimento sono lineari rispetto alla lunghezza delle liste e l'implementazione ha una difficoltà

decisamente gestibile (con gli alberi magari si incasina di più).Ovviamente è una soluzione da adottare se prevedi di fare

molte ricerche e relativamente poche cancellazioni e inserimenti,se il tuo insieme di rettangoli è invece molto dinamico

l'efficienza ne risente e devi trovare qualcos'altro.

[teju]

Originariamente inviato da unomichisiada
Ovviamente è una soluzione da adottare se prevedi di fare
molte ricerche e relativamente poche cancellazioni e inserimenti

Si, è proprio questo il caso! Di certo le ricerche saranno moltissime di più rispetto a inserimenti/cancellazioni!!!

[unomichisiada]

Allora fai così che è la cosa più semplice.Ciao