Creo que comenzaría con lo siguiente, que está cerca de lo que @belisarius ya propuso. Si tiene requisitos adicionales, como preferir rectángulos "casi cuadrados" a "largos y delgados", deberá modificar este enfoque ingenuo. Asumiré, en aras de la simplicidad, que los puntos están distribuidos aproximadamente de forma aleatoria.
- 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.
- Cuenta 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.
- En función de la distribución de puntos entre los medios rectángulos, mueva la línea para equilibrar las cosas nuevamente. Entonces, si, por casualidad, el primer corte divide los puntos 1/3, 2/3, mueve la línea a la mitad de la mitad pesada del rectángulo. Vaya al paso 2. (Tenga cuidado de no quedar atrapado aquí, moviendo la línea en pasos decrecientes primero en una dirección, luego en la otra.)
- Ahora, pase cada uno de los semicregulos en una llamada recursiva a esta función, en el paso 1.
Espero que describa la propuesta lo suficientemente bien. Tiene limitaciones: producirá un número de rectángulos igual a una 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 te gusta ese enfoque, quizás podrías comenzar con una cuadrícula regular con algunos múltiplos (10 - 100 quizás) del número de rectángulos que deseas. Cuenta 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 bien, si satisface sus requisitos lo suficientemente bien, puede 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 sea mucho más rápido ya que solo tendrías que contar los puntos en cada pequeño rectángulo una vez.
No he pensado realmente en el tiempo de ejecución de ninguno de estos; Tengo una preferencia por el enfoque anterior porque hago una buena cantidad de programación paralela y tengo montones de procesadores.
¿Quieres (aproximadamente) el mismo número de puntos en cada subrectángulo? Creo que sí, pero no está del todo claro. –
Sí, quiero el mismo número de puntos en cada subrect. –
Si no impone restricciones en la forma de los rectángulos, el problema es unidimensional, y todo lo que tiene que hacer es cortar un segmento con la misma cantidad de puntos (coordenada x de los puntos). Me parece que estás olvidando alguna restricción de "topología" –