Motivo:
He visto este algoritmo descrito, y prefiero no reinventar la rueda si existe una implementación estándar. También aprendí que si hay una implementación scipy/numpy, generalmente es mucho más rápido que cualquier cosa que pueda enrollar en python.Nombre de este algoritmo, y hay una implementación numpy/scipy de él?
Descripción del algoritmo
Tengo un gran número de puntos en el plano (varios millones). Comenzando con una caja grande que abarca todos los puntos, me gustaría subdividir continuamente la caja en subcajas de igual área. La subdivisión continúa recursivamente mientras haya al menos 1,000 puntos en el recuadro secundario. El algoritmo devuelve un árbol que describe las subdivisiones y el mapeo de los puntos a cada nodo de hoja del árbol.
¿Cuál es el nombre de este algoritmo (algo así como dividir y conquistar?), ¿Y hay un método estándar para hacerlo cuando se le da una matriz numpy 2D de puntos?
¿te refieres quad-tree? –
Si la división en una dimensión es un árbol N-kD (para N = 2). También la división debe hacerse de tal manera que los tamaños * de las poblaciones * de las dos partes sean (aproximadamente) iguales. – wildplasser
@wildplasser desde un punto de vista computacional, estoy de acuerdo con usted acerca de la división en poblaciones de igual tamaño (para la profundidad mínima del árbol). Sin embargo, estoy tratando de replicar los resultados de un trabajo en el que hacen exactamente lo que digo, una división de _areas iguales. – Hooked