2010-02-19 21 views
11

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?Qualcuno di queste librerie quad-albero di 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.

+0

penso che saltato un passo qui: se si dispone di "alcuna esperienza precedente con quad-alberi e nessuna idea di come usarli", quindi come fai a sapere una quadtree la biblioteca è ciò di cui hai bisogno? Anche supponendo di aver trovato una corrispondenza perfetta per le tue esigenze, non avresti problemi ad usarlo correttamente? IMO, devi studiare il problema un po 'di più prima di iniziare a implementare le cose. –

+4

@Bears: visita http://meta.stackoverflow.com se non capisci perché LMGTFY e l'offuscamento dei link sono scoraggiati su SO. – balpha

+4

@Bears ti mangerà: http://meta.stackexchange.com/questions/5280/embrace-the-non-googlers –

risposta

9

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.

+0

Grazie per l'aggiornamento! Hai appena vinto il premio. :-) –

+1

Per essere onesti, scipy.spatial.KDTree è solo una soluzione migliore se l'installazione di scipy è un'opzione. Potrebbe non essere (scipy ha alcune dipendenze interessanti). – alastair

1

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.

+0

Quadtree 0.1.2 non funzionerà in Python 3.1 poiché non ci sono setuptools. La fonte deve essere compilata prima per funzionare su Windows. –

+0

Se hai davvero bisogno delle prestazioni, puoi compilare il modulo per Python 3.1. Se non puoi farlo tu stesso, vai su comp.lang.python e chiedi se c'è qualcuno che può farlo per te. –

3

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])