Qual è la differenza principale tra un quadtree e kd-tree? Capisco che dividano i punti in molte dimensioni, ma non capisco perché dovremmo usarne uno sull'altro. Ho bisogno di una struttura che mi permetta di contare quanti punti (punti 2D) sono in una data regione. Fondamentalmente, sto cercando di rilevare gruppi di punti.Differenza tra quadtree e kd-tree
La differenza (algoritmicamente) è: in quadri, i dati che raggiungono un nodo sono suddivisi in celle fisse (2^d), di dimensioni uguali, mentre in kdtrees, i dati sono suddivisi in due regioni sulla base di alcuni dati di analisi (es. la mediana di alcune coordinate). I quadranti non si adattano bene alle dimensioni elevate, a causa della dipendenza esponenziale della dimensione. Anche le strutture dei dati differiscono nelle loro complessità temporali delle query.
Dato che sei interessato ai punti 2D, la struttura dei dati potrebbe funzionare per te. Gli alberi KD sono molto facili da interrogare per intervalli e sono generalmente preferiti su quadri. Ti suggerisco di usarli.
Vedere anche http://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree – naught101