Quadtree con duplicati

Question

Quadtree con duplicati

#1 da (3 voti)
#2 da (2 voti)
#3 da (2 voti)
#4 da (2 voti)
#5 da (2 voti)

10

Sto implementando un quadtree. Per coloro che non conoscono questa struttura dati, sto includendo la seguente piccola descrizione:

A Quadtree is a data structure and is in the Euclidean plane what an Octree is in a 3-dimensional space. A common use of quadtrees is spatial indexing.

To summarize how they work, a quadtree is a collection — let's say of rectangles here — with a maximum capacity and an initial bounding box. When trying to insert an element into a quadtree which has reached its maximal capacity, the quadtree is subdivided into 4 quadtrees (a geometric representation of which will have a four times smaller area than the tree before insertion); each element is redistributed in the subtrees according to its position, ie. the top left bound when working with rectangles.

So a quadtree is either a leaf and has less elements than its capacity, or a tree with 4 quadtrees as children (usually north-west, north-east, south-west, south-east).

La mia preoccupazione è che se si tenta di aggiungere duplicati, che si tratti dello stesso elemento più volte o di più elementi diversi con la stessa posizione, i quadranti hanno un problema fondamentale con la gestione dei bordi.

Ad esempio, se lavori con un quadruplo con una capacità di 1 e il rettangolo unitario come riquadro di delimitazione:

[(0,0),(0,1),(1,1),(1,0)]

E prova a inserire due volte un rettangolo il cui limite superiore sinistro è l'origine: (o similmente se provi ad inserirla N + 1 volte in un quadruplo con una capacità di N > 1)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

Il primo inserimento non sarà un problema:

Mapoiilprimoinserimentoattiveràunasuddivisione(perchélacapacitàè1):

Entrambi i rettangoli sono quindi inseriti nella stessa sottostruttura.

Quindi di nuovo, i due elementi arriveranno nello stesso quadruplo e attiveranno una sottodivisione ...

E così via, e così via, il metodo di suddivisione verrà eseguito indefinitamente perché (0, 0) sarà sempre nella stessa sottostruttura dei quattro creati, il che significa che si verifica un problema di ricorsione infinito.

È possibile avere un quadriplesso con duplicati? (In caso contrario, si può implementarlo come Set )

Come possiamo risolvere questo problema senza rompere completamente l'architettura di un quadruplo?

data-structures trees indexing

posta Pierre Arlaud 17.06.2014 - 15:44

fonte

5 risposte

Leggi altre domande sui tag data-structures trees indexing

Abbiamo bisogno di dati di test o possiamo fare affidamento su test unitari e test manuali? Come disaccoppiare completamente il modello da Visualizza / Controller in Java Swing

score 3 · Answer 1

Stai implementando una struttura dati, quindi devi prendere decisioni di implementazione.

A meno che il quadruplo non abbia qualcosa di specifico da dire sull'unicità - e io non sono consapevole che lo faccia - questa è una decisione di implementazione. È ortogonale alla definizione di un quadrifoglio e puoi scegliere di gestirlo come vuoi. Il quadruplo ti dice come inserire e aggiornare le chiavi, ma non se devono essere univoci, o cosa puoi allegare a ciascun nodo.

Prendere decisioni di implementazione non è reinventare la ruota , almeno non più di scrivere la tua implementazione in primo luogo.

Per confronto, la libreria standard C ++ offre un set unico, un multiset non univoco, una mappa univoca (essenzialmente un insieme di coppie chiave-valore ordinate e confrontate solo dalla chiave) e una multimap non univoca. Sono tutti in genere implementati utilizzando lo stesso albero rosso-nero e nessuno infrange l'architettura , semplicemente perché la definizione dell'albero rosso-nero non ha nulla da dire sull'unicità delle chiavi o sui tipi memorizzati nei nodi foglia.

Infine, se pensi che ci sia una ricerca su questo, trovala, e poi possiamo discuterne. Forse c'è qualche invarianza quadrupla che ho trascurato, o qualche vincolo aggiuntivo che consente prestazioni migliori.

score 2 · Answer 2

Penso che ci sia un malinteso qui.

A quanto ho capito, ogni nodo quadrifoglio contiene un valore indicizzato da un punto. In altre parole, contiene la tripla (x, y, valore).

Contiene anche 4 puntatori ai nodi figli, che possono essere nulli. Esiste una relazione algoritmica tra le chiavi e i collegamenti secondari.

I tuoi inserti dovrebbero apparire così.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

Il primo inserto crea un nodo (genitore) e inserisce un valore in esso.

Il secondo insert crea un nodo figlio, vi collega ad esso e inserisce un valore in esso (che potrebbe essere lo stesso del primo valore).

Quale nodo figlio è istanziato dipende dall'algoritmo. Se l'algoritmo si trova nella forma [x) e lo spazio delle coordinate si trova nell'intervallo [0,1), ogni bambino occuperà l'intervallo [0,0.5) e il punto verrà posizionato nel figlio NW.

Non vedo una ricorsione infinita.

score 2 · Answer 3

2

La risoluzione comune che ho incontrato (nei problemi di visualizzazione, non nei giochi) è quella di abbandonare uno dei punti, sia in sostituzione che in sostituzione.

Suppongo che il punto principale a favore sia che è facile da fare.

risposta data 28.02.2015 - 02:39

fonte

score 2 · Answer 4

Suppongo che tu stia indicizzando gli elementi che sono tutti della stessa dimensione, altrimenti la vita diventa complessa, o lenta, o entrambi ......

Un nodo Quadtree non ha bisogno di avere una capacità fissa. La capacità è utilizzata per

Consenti a ciascun nodo dell'albero di dimensione fissa nella memoria o su disco - non richiesto se il nodo dell'albero contiene un insieme di elementi di dimensioni variabili e stai utilizzando un sistema di allocazione dello spazio che gestisce. (Ad es. Oggetti java / c # in memoria.)
Decidi quando dividere un nodo.
- Potresti semplicemente ridefinire la regola, in modo che un nodo sia diviso se contiene più di "n" elementi del distretto, in cui il distretto è definito in base alla posizione degli elementi.
- O usa un " elemento composito ", quindi se ci sono molti elementi nella stessa posizione, introduci un nuovo elemento che contiene un elenco di questi elementi moltiplicati.

score 2 · Answer 5

Quando hai a che fare con problemi di indicizzazione spaziale, in realtà consiglio di iniziare con un hash spaziale o il mio preferito: la semplice vecchia griglia.

...ecapirneledebolezzeprimadipassareallestruttureadalberocheconsentonorappresentazionisparse.

Unodegliovvipuntidebolièchesipotrebbesprecarememoriasumoltecellevuote(ancheseunagrigliaimplementatainmodocorrettonondovrebberichiederepiùdi32bitpercella,amenochenonsiabbianoeffettivamentemiliardidinodidainserire).Unaltroèchesesihannoelementididimensionimoderatechesonopiùgrandidelledimensionidiunacellaespessosiestendono,adesempio,dozzinedicelle,sipuòsprecaremoltamemoriainserendoqueglielementidimediagrandezzainmoltopiùcellecheideali.Allostessomodo,quandoeseguiqueryspaziali,potrestidovercontrollarepiùcelle,avoltemoltopiùdiquantosiaideale.

Mal'unicacosachepuòesseredefinitaconunagrigliaperrenderlaottimalerispettoauncertoinputècellsize,chenontilasciatroppopensareegiocarci,edèperquestocheèilmiogo-tostrutturadeidatiperproblemidiindicizzazionespazialefinoatrovaremotivipernonusarlo.Èsemplicedaimplementareenonrichiedediarmeggiareconqualcosadipiùdiunsingoloingressodiruntime.

Puoiotteneremoltodaunasemplicevecchiagrigliaehoeffettivamentebattutounsaccodiimplementazionidiquad-treeekdtreeusatenelsoftwarecommercialesostituendoleconunasemplicevecchiagriglia(sebbenenonfosseronecessariamentelaquellimeglioimplementati,magliautorihannospesomoltopiùtempodei20minutichehospesopermontareunagriglia).Eccounapiccolacosarapidachehomontatoperrispondereadunadomandaaltroveusandounagrigliaperilrilevamentodellecollisioni(nemmenoottimizzataveramente,solopocheoredilavoro,ehodovutopassarelamaggiorpartedeltempoadimpararecomefunzionailpathpathperrisponderealladomandaedèstataanchelaprimavoltacheimplementavoquestotipodirilevamentodellecollisioni):

Un'altradebolezzadellegriglie(masonocarenzegeneralipermoltestrutturediindicizzazionespaziale)èchesesiinserisconomoltielementicoincidentiosovrapposti,comemoltipunticonlastessaposizione,verrannoinseritinellostessoidenticocella(e)edegradanoleprestazioniquandoattraversanoquellacella.Allostessomodoseinseriscimoltielementimassimichesonomolto,moltopiùgrandidelledimensionidellacella,vorrannoessereinseritiinuncaricodicelleeutilizzaremoltamemoriaedegradareiltemporichiestoperqueryspazialisututtalalinea.

Tuttavia,questidueproblemiimmediatidicuisopraconelementicoincidentiemassiccisonoinrealtàproblematiciperletuttestrutturediindicizzazionespaziale.Lasemplicevecchiagrigliainrealtàgestiscequesticasipatologiciunpo'megliodimoltialtripoichéalmenononvuolesuddividereinmodoricorsivolecellulepiùepiùvolte.

Quandoiniziconlagrigliaetidirigiversoqualcosacomeunquad-treeounalberoKD,allorailproblemaprincipalechevuoirisolvereèilproblemaconglielementichevengonoinseritiintroppecelle,avendotroppicellee/odovercontrollaretroppecelleconquestotipodirappresentazionedensa.

Masepensiadunquad-treecomeottimizzazionesuunagrigliapercasid'usospecifici,alloraaiutaancoraapensareall'ideadiuna"dimensione minima della cella", per limitare la profondità della suddivisione ricorsiva dei nodi quad-tree. Quando lo fai, lo scenario peggiore del quad-tree si degraderà ancora nella griglia densa alle foglie, solo meno efficiente della griglia dal momento che richiederà tempo logaritmico per lavorare da root a cella della griglia invece di tempo costante. Tuttavia, pensare a quella dimensione minima delle celle eviterà lo scenario infinito di loop / ricorsione. Per gli elementi massicci ci sono anche alcune varianti alternative come i quadricotteri allentati che non si dividono necessariamente in modo uniforme e potrebbero avere AABB per i nodi figlio che si sovrappongono. I BVH sono interessanti anche come strutture di indicizzazione spaziale che non suddividono uniformemente i loro nodi. Per elementi coincidenti contro strutture ad albero, la cosa principale è semplicemente imporre un limite alla suddivisione (o come altri hanno suggerito, semplicemente rigettarli o trovare un modo per trattarli come se non stessero contribuendo al numero univoco di elementi in una foglia quando si determina quando la foglia deve suddividersi). Un albero di Kd potrebbe anche essere utile se si anticipano gli input con molti elementi coincidenti, poiché è necessario considerare una sola dimensione per determinare se un nodo deve essere suddiviso in mediana.