Consideremos una región (2D) rellenada con líneas de forma aleatoria (figura siguiente). Estamos interesados en llenar los espacios vacíos entre las líneas incluyendo cuatro bordes de la frontera de una manera:
0- maximizar el tamaño de las parcelas;
1- La forma de los paquetes de relleno es cuadrada alineada horizontal o verticalmente;
2- La forma de los paquetes de relleno es cuadrada, es decir, una alineación relajada ;
3- forma de las parcelas de relleno es cualquier cuadrilátero. nuestra pregunta original
Así que por ahora hay tres escenarios diferentes.
Nota que las líneas son de la forma [x1,y1,x2,y2] conjunto de puntos, números reales.
[* * *] Las ideas de posibles soluciones/algoritmos/repuntes de código/etc son más que bienvenidas.
Actualización 1: Podríamos conseguir una solución para el primer caso:
Los pasos son:
1- líneas
2- rasterización de líneas en un mapa de bits
3- buscar celdas cercanas para cada celda de color deseado (es decir, del mismo color) con una función objetivo para maximizar el área, es decir, el número de celdas.
Funciona bien, pero sólo cubre el primer escenario y además es lento.
Actualización 2:
Suponemos que el lector está familiarizado con el concepto de llenado de espacios con baldosas. Puede seguir el enlace para inspirarse. Sin embargo, tenga en cuenta que nuestro problema es diferente. Ya que no llenamos el espacio vacío al azar y no elegimos el tamaño al azar. La solución debe ser iterativa. Para todos los casos, no hay límite en el número de parcelas que se ajustan. De hecho, el usuario puede limitar el número de iteraciones, eligiendo un área mínima para las parcelas, por ejemplo. Esto es obvio en el ejemplo dado anteriormente en el que discretizamos las líneas en píxeles con un tamaño especificado. Es decir, el procedimiento debe ejecutarse hasta que se llene toda el área vacía respetando el criterio, por ejemplo, el área máxima de las parcelas.
Actualización 3:
resumen:
Una de las aplicaciones es averiguar la distribución de los bloques de "roca" intactos extraíbles en una "mina" muy fracturada. Esto podría ser muy útil para muchos aspectos, como el diseño de las perforaciones, la evaluación financiera, etc.
descripción:
Para una mina de roca decorativa (piedra) los productos que son los bloques de rocas intactas cortadas como cubos rectangulares el precio depende estrechamente del tamaño del bloque. La extracción de un bloque de una zona adecuada, es decir, sin ninguna fractura importante, será deseable si la cantidad de piezas restantes es lo más pequeña posible. Por lo general, los trozos pequeños de roca no tienen un valor económico relativo y se consideran así como residuos.
La pregunta de este post investiga soluciones para este tipo de problemas.
Una visión matemática del problema puede ser la siguiente:
2D: Encuentre todos los rectángulos que puedan extraerse de una región 2D dada con algunas líneas optimizadas para un tamaño de rectángulo lo más grande posible.
3D: Encuentre todos los cubos rectangulares que puedan extraerse de una región 3D dada con algunos subplanos (mejor: polígonos) optimizados para un tamaño de bloque lo más grande posible.
Dado que esto forma parte de una investigación en curso, algunas de las preguntas formuladas en los comentarios no tienen respuestas seguras que podamos ofrecer. Creemos que la información proporcionada hasta ahora es suficiente para obtener una visión general del problema. No obstante, proporcionamos algunos detalles en la medida de lo posible para beneficio de la comunidad.
Puede poner algunas restricciones a la solución de la última pregunta, aunque, creemos que siempre es posible añadir más después. Por ejemplo, sigue estas: {caso 2D}
El mejor tamaño de un bloque (rectángulo económicamente óptimo) que se puede extraer en las condiciones mencionadas anteriormente, es 1x1 m dado 10x10 m para la región del ejemplo. Se trata de una restricción definida en función del valor económico. El tamaño mínimo de trabajo para el corte, etc., es 0.15x0.15 m ; así que este es el segundo límite de tamaño.
La figura anterior muestra la función de valor económico en función del tamaño del bloque. Así, para este caso concreto, cada pieza de roca menor que 0.15x0.15 m es sólo un desperdicio. No habrá un tamaño de bloque mayor que 1.7x1.7 m debido a los límites de funcionamiento.
