Relleno de espacio entre líneas 2D aleatorias

23

Considere una región (2D) llena de líneas al azar (a continuación se muestra la Figura). Nos interesa llenar los espacios vacíos entre las líneas, incluidos cuatro bordes de borde de una manera:

0- maximizando el tamaño de las parcelas;
1- la forma de rellenar las parcelas se alinea cuadrada horizontal o verticalmente;
2- la forma de los paquetes de relleno es cuadrada, es decir, alineación relajada ;
3- la forma de los paquetes de relleno es cualquier cuadrángulo. < em> nuestra pregunta original

Por ahora, hay tres escenarios diferentes.
Nota que las líneas tienen la forma [x1,y1,x2,y2] point set, números reales.

[* * *] Las ideas de posibles soluciones / algoritmos / fragmentos de código / etc son más que bienvenidas.

Actualización1:Podríamosadministrarunasoluciónparaelprimercaso:

Los pasos son:
1- líneas
2- rasterizando líneas en un mapa de bits
3- buscando celdas cercanas para cada celda del color deseado (es decir, el mismo color) con una función objetivo para maximizar el área, es decir, el número de celdas.

Funciona bien, sin embargo, cubre solo el primer escenario y también es lento.

Actualización 2:
Asumimos que el lector está familiarizado con el concepto de espacio-relleno-mosaico. Puedes seguir el enlace para inspirarte. Sin embargo, tenga en cuenta que nuestro problema es diferente. Como 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 están ajustando. De hecho, es responsabilidad del usuario limitar el número de iteración, eligiendo un área mínima para parcelas, por ejemplo. Esto es obvio en el ejemplo dado anteriormente en el que discretizamos líneas en píxeles con un tamaño específico. Es decir, el procedimiento debe ejecutarse hasta que se llene un área vacía completa, respetando el criterio, por ejemplo, el área máxima de las parcelas.

Actualización 3:
resumen:
Una aplicación es averiguar la distribución de bloques de "roca" intactos extraíbles en una "mina" muy fracturada. Esto podría ser muy útil para muchos aspectos, incluidos el diseño de perforación, la evaluación financiera, etc.
description:
Para una mina de roca decorativa (piedra), los productos que son bloques de rocas intactas cortadas como cubos rectangulares, el precio depende en gran medida del tamaño del bloque. La extracción de un bloque de un área adecuada, es decir, sin una fractura mayor será deseable si la cantidad de partes restantes es lo más pequeña posible. Por lo general, las pequeñas piezas de roca no tienen un valor económico relativo y se consideran desechos.
La pregunta en este post investiga soluciones para este tipo de problema.

Una vista matemática del problema se puede expresar de la siguiente manera:
2D: Encuentre todos los rectángulos que podrían extraerse de una región 2D determinada con algunas líneas optimizadas para obtener el mayor tamaño de rectángulo posible.
3D: Encuentre todos los cubos rectangulares que podrían extraerse de una región 3D determinada con algunos subplanos (mejor: polígonos) optimizados para un tamaño de bloque más grande posible.

Dado que esto es parte de una investigación en curso, algunas de las preguntas formuladas en los comentarios a continuación no tienen ciertas respuestas que podamos proporcionar. Creemos que la información proporcionada aquí hasta el momento es realmente suficiente para tener una idea general del problema. Sin embargo, proporcionamos algunos detalles como podemos para los beneficios de la comunidad.
Puede poner algunas restricciones en la solución para la pregunta final, aunque creemos que siempre es posible agregar más más tarde. Por ejemplo, siga estos: {Caso 2D}
El mejor tamaño de un bloque (rectángulo económicamente óptimo) que se extraerá en las condiciones mencionadas anteriormente, es 1x1 m dado 10x10 m para la región en el ejemplo. Esta es una restricción definida basada en el valor económico. El tamaño mínimo viable para cortar, etc., sea 0.15x0.15 m ; así que este es el segundo límite de tamaño.

La figura de arriba muestra la función de valor económico dependiendo del tamaño del bloque. Así que para este caso particular, cada pieza de roca más pequeña que 0.15x0.15 m es simplemente un desperdicio. No habrá un tamaño de bloque mayor que 1.7x1.7 m debido a los límites de operación.

    
pregunta Developer 21.11.2012 - 09:39

1 respuesta

2

Tengo una idea de cómo trabajas iterativamente desde bloques grandes hasta bloques más pequeños usando FME (de Safe Software). Para el registro, no trabajo para ellos, pero parece que elogio su herramienta lo suficiente ...

  1. Use "BoundingBoxReplacer" en el área de interés.
  2. Reproyecte en un sistema de coordenadas local (para más adelante cuando necesite "mosaico" en pies / metros).
  3. Buffer las líneas con transformador "Bufferer". Solo necesita un tamaño arbitrario, por ejemplo .01 pies / metros. Lo que estamos buscando aquí es un polígono de la línea para el siguiente paso.
  4. Agrega un transformador "Tiler". Especifique un tamaño de mosaico grande (estimado o no) en pies o metros. Lo que estamos haciendo aquí es agrupar el área de interés en bloques cuadrados. Dependiendo del conjunto de datos, comience en grande para obtener realmente los valores atípicos grandes.
  5. Agrega un transformador "Clipper". Lo que estamos haciendo aquí es esencialmente dividir el conjunto de datos para ver qué mosaicos son buenos / malos. En la salida, los mosaicos que están "Dentro" son demasiado grandes. Sin embargo, los azulejos que están "Fuera" son lo suficientemente grandes y están listos para cortar ...
  6. Aquí es donde se complica, pero no es difícil ... Vamos a hacer un bucle en el transformador para que reutilicemos el BoundingBox original, pero recortemos las áreas que ya están listas para cortar. Entonces, agregue un recortador y enrute el recortador como los mosaicos de "Salida" en la salida anterior del recortador. Ahora tenemos un solo polígono que está listo para volver a funcionar.
  7. Usa el marcador de nuevo, esta vez especificando un mosaico más pequeño. Por ejemplo, si usaste baldosas de 100 metros antes, prueba con 90 metros.
  8. Agregue otro recortador, con el recortador de entrada como las líneas en búfer y el recorte de entrada como los mosaicos más pequeños como entrada.

Enjuague y repita tantas veces como sea necesario usando baldosas más pequeñas cada vez. He adjuntado el inicio de una mesa de trabajo que usaría como un enfoque.

Según su descripción (bien detallada), por ahora solo funcionará con su opción 1. Sin dedicar demasiado tiempo todavía.

De todos modos, este es solo un enfoque con el que comenzaría por lo menos filtrar el trigo de la paja.

    
respondido por el Matthew Brucker 05.10.2013 - 08:56

Lea otras preguntas en las etiquetas