Motivazione:
Ho visto questo algoritmo descritto e preferirei non reinventare la ruota se esiste un'implementazione standard. Ho anche imparato che se c'è un'implementazione di scipy/numpy, di solito è molto più veloce di qualsiasi cosa riesca a ottenere da solo in python.Nome di questo algoritmo e c'è un'implementazione numpy/scipy di questo algoritmo?
Algoritmo Descrizione
Ho un gran numero di punti sul piano (diversi milioni). A partire da una grande scatola che comprende tutti i punti, mi piacerebbe suddividere continuamente la scatola in sotto-caselle di uguale area. La suddivisione continua in modo ricorsivo mentre ci sono almeno 1.000 punti nella sottocasella. L'algoritmo restituisce un albero che descrive le suddivisioni e la mappatura dei punti su ciascun nodo foglia dell'albero.
Qual è il nome di questo algoritmo (qualcosa come divide e conquista?), E c'è un metodo standard per farlo quando viene assegnato un array di punti numerico 2D?
intendi quad-tree? –
Se la suddivisione in una dimensione è un albero N-kD (per N = 2). Anche la scissione dovrebbe essere fatta in modo tale che le dimensioni * delle popolazioni * delle due parti siano (circa) uguali. – wildplasser
@wildplasser da un punto di vista computazionale, sarei d'accordo con te sulla suddivisione lungo popolazioni di uguali dimensioni (per profondità minima dell'albero). Tuttavia, sto cercando di replicare i risultati di un foglio in cui fanno esattamente come dico, una scissione di pari livello. – Hooked