Algoritmo de partición espacial

Question

Tengo un conjunto de puntos que están contenidos dentro del rectángulo. Me gustaría dividir los rectángulos en subrectángulos en función de la densidad de puntos (dando una serie de subrectángulos o densidad deseada, lo que sea más fácil).

La partición no tiene que ser exacta (casi cualquier aproximación mejor que la red normal), pero el algoritmo tiene que hacer frente a la gran cantidad de puntos: aprox. 200 millones. Sin embargo, el número deseado de subrectángulos es sustancialmente más bajo (alrededor de 1000).

¿Alguien sabe algún algoritmo que pueda ayudarme con esta tarea en particular?

Answer 1

Solo para entender el problema. Lo siguiente es crudo y actúa mal, pero quiero saber si el resultado es lo que quieres>

Asunción> El número de rectángulos es incluso
Asunción> La distribución de puntos es notablemente 2D (no hay una gran acumulación en una línea)

Procedimiento>
Bisecte n/2 veces en cualquier eje, enrollando de un extremo a otro de cada rectángulo determinado que se contaba "pasó" los puntos y almacenan el número de puntos aprobados en cada iteración. Una vez contado, busque el rectángulo seleccionando por los puntos contados en cada bucle.

¿Es eso lo que quieres lograr?

Answer 2

Creo que busca un árbol estándar de división KD de KD o espacios binarios. (Puedes buscarlo en Wikipedia).

Como tiene muchos puntos, es posible que desee dividir solo aproximadamente los primeros niveles. En este caso, debe tomar una muestra aleatoria de sus 200 millones de puntos, tal vez 200k de ellos, y dividir el conjunto de datos completos en el punto medio de la submuestra (a lo largo de cualquier eje más largo). Si realmente elige los puntos al azar, la probabilidad de que se pierda un gran grupo de puntos que deben subdividirse será aproximadamente cero.

Ahora tiene dos problemas de unos 100 millones de puntos cada uno. Divida cada uno a lo largo del eje más largo. Repita hasta que deje de tomar submuestras y divida todo el conjunto de datos. Después de diez iteraciones de la amplitud, habrá hecho.

Si tiene un problema diferente: debe proporcionar marcas de tick a lo largo del eje X e Y y completar una cuadrícula a lo largo de las mejores que pueda, en lugar de tener la descomposición irregular de un árbol KD: tome su submuestra de puntos y Encuentre los percentiles 0/32, 1/32, ..., 32/32 a lo largo de cada eje. Dibuja tus líneas de cuadrícula allí, luego llene la cuadrícula de 1024 elementos resultante con tus puntos.

Answer 3

R-árbol

Answer 4

Creo que comenzaría con lo siguiente, que está cerca de lo que @Belisarius ya propuso. Si tiene algún requisito adicional, como preferir rectángulos 'casi cuadrados' a los 'largos y delgados', necesitará modificar este enfoque ingenuo. Asumiré, en aras de la simplicidad, que los puntos se distribuyen aproximadamente al azar.

1. Divida su rectángulo inicial en 2 con una línea paralela al lado corto del rectángulo y corriendo exactamente a través del punto medio.
2. Cuente el número de puntos en ambos medios rectángulos. Si son iguales (suficientes), vaya al paso 4. De lo contrario, vaya al paso 3.
3. Basado en la distribución de puntos entre los medios rectángulos, mueva la línea para igualar las cosas nuevamente. Entonces, si, perchance, el primer corte divide los puntos 1/3, 2/3, mueva la línea a mitad de camino hacia la mitad pesada del rectángulo. Vaya al paso 2. (Tenga cuidado de no quedarse atrapado aquí, moviendo la línea en pasos siempre disminuyendo primero en una dirección, luego en la otra).
4. Ahora, pase cada uno de los medios rectángulos a una llamada recursiva a esta función, en el paso 1.

Espero que describe la propuesta lo suficientemente bien. Tiene limitaciones: producirá una serie de rectángulos iguales a alguna potencia de 2, así que ajústelo si eso no es lo suficientemente bueno. Lo he expresado recursivamente, pero es ideal para la paralelización. Cada división crea dos tareas, cada una de las cuales divide un rectángulo y crea dos tareas más.

Si no le gusta ese enfoque, tal vez podría comenzar con una cuadrícula regular con algunos múltiples (10 - 100 quizás) del número de rectángulos que desea. Cuente el número de puntos en cada uno de estos pequeños rectángulos. Luego comience a pegar los pequeños rectángulos hasta que el rectángulo menos pequeño contenga (aproximadamente) el número correcto de puntos. O, si satisface sus requisitos lo suficientemente bien, podría usar esto como un método de discretización e integrarlo con mi primer enfoque, pero solo coloque las líneas de corte a lo largo de los límites de los pequeños rectángulos. Esto probablemente sería mucho más rápido, ya que solo tendría que contar los puntos en cada pequeño rectángulo una vez.

Realmente no he pensado en el tiempo de ejecución de ninguno de estos; Tengo preferencia por el enfoque anterior 'porque hago una buena cantidad de programación paralela y tengo montones de procesadores.

Answer 5

Buena pregunta.

Creo que el área que necesita investigar es la "geometría computacional" y el problema de "K-particioning". Hay un enlace que podría ayudarlo a comenzar aquí

Puede encontrar que el problema en sí es NP-Hard, lo que significa que un buen algoritmo de aproximación es el mejor que obtendrá.

Answer 6

haría Clúster K-means o Diagrama de Voronoi ¿Sea una buena opción para el problema que está tratando de resolver?

Answer 7

Eso se parece Análisis de conglomerados.

Answer 8

Lo haría Quadtree ¿trabajar?

Un Quadtree es una estructura de datos de árbol en la que cada nodo interno tiene exactamente cuatro hijos. Los quadrees se usan con mayor frecuencia para dividir un espacio bidimensional al subdividirlo recursivamente en cuatro cuadrantes o regiones. Las regiones pueden ser cuadradas o rectangulares, o pueden tener formas arbitrarias. Esta estructura de datos fue nombrada Quadtree por Raphael Finkel y JL Bentley en 1974. Una partición similar también se conoce como Q-Tree. Todas las formas de quadrees comparten algunas características comunes:

• Descomponen el espacio en células adaptables
• Cada celda (o cubo) tiene una capacidad máxima. Cuando se alcanza la capacidad máxima, el cubo se divide
• El directorio de árbol sigue la descomposición espacial del quadtree