Strutture Dati: Rettangoli

[mrYellow]

Il Problema:
Ho dei rettangoli in un piano infinito che si sovrappongono l' uno all' altro ( uno può anche essere contenuto nell'altro).
Mi vengono dati dei punti casuali nel piano e io devo calcolare in quanti rettangoli è contenuto il punto.
I rettangoli sono identificati dalle coordinate del punto in basso a sinistra e da quelle del punto in alto a destra.

Tutto ciò deve essere fatto usando una struttura dati adeguata.


Stavo pensando a un grafo con una ricerca DFS... ma non sono sicuro.
Secondo voi?

Scusate se questa è la sezione sbagliata ma non sapevo dove altro postarlo.

ciao.

[anx721]

Come la fai con un grafo? A me viene in mente solo un vettore di rettangoli da scorrere linearmente, e controllare per ognuno se il punto e incluso o no...

[zampa28]

Rettangolo:
PuntoA=Ax;Ay PuntoB=Bx;By

Punto ricerca:
X=Xx;Xy

Test:
Xx >= Ax And Xx <= Bx And Xy >= Ay And Xy <= By

Ho sparato una fagianata?

[anx721]

Originariamente inviato da zampa28
Rettangolo:
PuntoA=Ax;Ay PuntoB=Bx;By

Punto ricerca:
X=Xx;Xy

Test:
Xx >= Ax And Xx <= Bx And Xy >= Ay And Xy <= By

Ho sparato una fagianata?

No, la formula e corretta, fermo restando che non capisco cosa centrino i grafi... :master:

[mrYellow]

Il problema è che scorrere un vettore o una lista comporta un tempo O(n)

Se riuscissi ad utilizzare un albero potrei calcolare il tutto in O(lg n). Tuttavia non riesco a trovare una condizione adatta per l'inserimento dei nodi.
Allora ho pensato a un grafo anche se non penso che questo diminuisca di molto il tempo di calcolo. anzi...

Mi hanno suggerito di usare un KD Tree o un BSP Tree o ancora un algoritmo scanline.Però non trovo documentazione valida su queste strutture.
Se qualcuno avesse qualche link mi farebbe un grande favore...

[anx721]

Certo che un albero o strutture simile aiuterebbero, il fatto è che non capisco come inserire i dati in un albero. Il fatto è che bisognerebbe stabilire un ordine totale sui rettangoli, questa relazione d'ordine dovrebbe essere in grado di farti capire se un punto appartiene o meno a un rettangolo. Se ad esempio ordini i rettangoli in base alla coordinata x di A, puoi con una ricerca logaritmica eliminare tutti quelli che hanno la coordinata x dell'estremo inferiore maggiore di x. Però in tutto, come tu hai fatto notare ci sono 4 vincoli da soddisfare sulle coordinate, quindi in questa strategia dovresti ad esempio usare 4 vettori per conservare i rettangoli, ogni vettore contiene tutti i rettangoli ordinati rispetto a una coordinata: A.x, A.y, B.x, B.y. Dato il punto X.x dovresti eseguire una ricerca su tutti e quatrro i vettori; ciò ti produce un sottovettore per ognuno su cui restringere la ricerca (il risultato finale sarebbe l'insieme dei rettangoli appartenenti a tutti e quattro questi sottovettori). Questo in generale puo ridurre il numero di rettangoli da confrontare, pero in un caso pessimo faresti comunque O(n) confronti. L'algoritmo basasto sulle snanlines serve in genereale per determinare se un punto e interno o no ad un poligono generico,ma nel caso di un rettangolo è piu immediato applicare direttamente la tua formula.

[mrYellow]

Ho cercato un po di documentazione in internet è credo di poter utilizzare un BSP Tree che credo sia un algoritmo utilizzato massicciamente nel campo grafico.

In pratica nel caso un rettangolo si sovrapponga ad un altro lo si divide continuamente fino ad ottenere dei sottorettangoli più piccoli che si riescono a sistemare in un nodo.

A questo punto è sufficente scorrere un cammino dell' albero per conoscere in quali rttangoli un punto è contenuto.

A chi interessase può trovare un pò di documentazione qui:
http://www.gamedev.net/reference/art...article657.asp