Qualcuno di queste librerie quad-albero di buono?

Question

Sembra che un certo mio progetto richiederà l'uso di quad-alberi, qualcosa che non ho mai lavorato prima. Da quello che ho letto dovrebbero consentire sostanziali miglioramenti delle prestazioni rispetto a un tentativo di forza bruta al problema. Qualcuno di questi moduli Python è buono?

• Quadtree 0.1.2 < = No: in grado di eseguire in Python 3,1
• QuadTree < = Sì: semplice, mentre si lavora con rettangoli
• quadtree.py < = No: senza supporto per le operazioni necessarie

EDIT 1: Qualcuno sa di un'implementazione migliore di quello presentato nel wiki pygame?

EDIT 2: Ecco alcune risorse che altri potrebbero trovare utili per le tecniche di individuazione dei percorsi in Python.

• Game Entity Navigation
• Catch the Cootie

Answer 1

In this comment, joferkington si riferisce alla domanda attuale e dice:

Proprio per ciò che vale, scipy.spatial.KDTree (e/o scipy.spatial.cKDTree, che è scritto in C per motivi di prestazioni) è un scelta molto più robusta rispetto alle opzioni elencate.

Answer 2

A volte, non è ovvio come implementare strutture di dati come gli alberi in Python.

Ad esempio,

 D 
    / \ 
    B  F 
/\ /\ 
A C E G 

è una semplice struttura ad albero binario. In Python, lo si rappresenterebbe in questo modo:

[D,B,F] è un nodo con una sottostruttura sinistra e destra. Per rappresentare l'intero albero si avrebbe:

[D,[[B,A,C],[F,E,G]]] 

Questo è un semplice elenco di liste annidate in cui ogni nodo può essere un valore come la D o C, ed ogni nodo può essere una sottostruttura che è, ricorsivamente, un elenco di liste annidate. Potresti fare qualcosa di simile con un dizionario di dizionari. Questi tipi di implementazioni sono un po 'veloci e sporchi e potrebbero non essere accettabili in un compito in cui l'istruttore si aspetta una classe Node con puntatori ad altri nodi, ma nel mondo reale è generalmente meglio usare le implementazioni ottimizzate di elenchi/dizionari Python primo. Solo se il risultato è in qualche modo inadeguato, riscrivilo per essere più simile a come lo scriverai in C o Java.

Oltre a ciò, naturalmente, è necessario implementare i vari algoritmi per manipolare i vostri alberi, perché un quadtree non è solo un po 'di dati; è un insieme di regole su come inserire ed eliminare i nodi. Se questa non è una domanda corsi, quindi Quadtree 0.1.2 sarebbe probabilmente una buona idea.

Answer 3

L'indice pacchetto python produce 2 altre librerie durante la ricerca di quadtree: http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search

disclaimer: mai usato quadtree o qualsiasi di queste librerie.

Answer 4

Un'altra libreria da verificare è PyQuadTree, un indice quadtree in puro pitone che funziona anche su Python 3x. Tutto ciò che serve per aggiungere un oggetto è il suo riquadro di delimitazione come una sequenza di 4 lunghezze, quindi potrebbe essere usato per una varietà di scopi e persino di sistemi di coordinate negativi.

Sebbene io sia l'autore, ho appena preso la struttura/codice quadtree di qualcun altro e reso più user-friendly, aggiunto il supporto per quadrangolare e aggiunto documentazione. Un semplice esempio di come usarlo:

#SETUP 
import pyqtree 
spindex = pyqtree.Index(bbox=[0,0,1000,500]) 

#ADD SOME ITEMS 
for item in items: 
    spindex.insert(item=item, bbox=item.bbox) 

#RETRIEVE ITEMS FROM A REGION 
result = spindex.intersect(bbox=[233,121,356,242])