algorithm geometry

algorithm - Encuentre el conjunto de rectángulos contiguos más grandes para cubrir múltiples áreas



geometry (4)

Estoy trabajando en una herramienta llamada Quickfort para el juego Dwarf Fortress . Quickfort convierte las hojas de cálculo en formato csv / xls en una serie de comandos para que Dwarf Fortress lleve a cabo para trazar un "plano" dentro del juego.

Actualmente estoy intentando resolver de manera óptima un problema de trazado de área para la versión 2.0 de esta herramienta.

Considere el siguiente "modelo" que define los comandos de trazado para una cuadrícula bidimensional. Cada celda de la cuadrícula debe ser excavada ("d"), canalizada ("c"), o dejada sin trazar ("."). Cualquier número de comandos de trazado distintos puede estar presente en el uso real.

. d . d c c d d d d c c . d d d . c d d d d d c . d . d d c

Para minimizar el número de instrucciones que deben enviarse a Dwarf Fortress, me gustaría encontrar el conjunto de rectángulos contiguos más grandes que se pueden formar para cubrir completamente, o "trazar", todas las celdas trazables. Para ser válido, todas las celdas de un rectángulo dado deben contener el mismo comando.

Este es un enfoque más rápido del que tomó Quickfort 1.0: trazando cada celda individualmente como un rectángulo 1x1. Este video muestra la diferencia de rendimiento entre las dos versiones.

Para el plano anterior, la solución se ve así:

. 9 . 0 3 2 8 1 1 1 3 2 . 1 1 1 . 2 7 1 1 1 4 2 . 6 . 5 4 2

Cada rectángulo del mismo número anterior denota un rectángulo contiguo. Los rectángulos más grandes tienen prioridad sobre los rectángulos más pequeños que también podrían formarse en sus áreas. El orden de la numeración / rectángulos no es importante.

Mi enfoque actual es iterativo. En cada iteración, construyo una lista de los rectángulos más grandes que podrían formarse a partir de cada una de las celdas trazables de la cuadrícula al extenderse en las 4 direcciones desde la celda. Después de ordenar la lista más grande primero, comienzo con el rectángulo más grande encontrado, marque sus celdas subyacentes como "trazadas" y grabo el rectángulo en una lista. Antes de trazar cada rectángulo, se comprueban sus celdas subyacentes para asegurarse de que aún no están trazadas (superpone una trama anterior). Luego comenzamos de nuevo, encontrando los rectángulos restantes más grandes que pueden formarse y representándolos hasta que todas las celdas se hayan trazado como parte de algún rectángulo.

Considero que este enfoque es un poco más optimizado que una búsqueda de fuerza bruta tonta, pero estoy desperdiciando muchos ciclos (re) calculando los rectángulos más grandes de las células y comprobando los estados de las células subyacentes.

Actualmente, esta rutina de descubrimiento de rectángulo se lleva la parte del león del tiempo de ejecución total de la herramienta, especialmente para planos grandes. He sacrificado cierta precisión por el simple hecho de considerar los rectángulos de las celdas que parecen formar la esquina de un rectángulo (determinado utilizando algunas heurísticas de celdas vecinas que no siempre son correctas). Como resultado de esta ''optimización'', mi código actual en realidad no genera correctamente la solución anterior, pero está lo suficientemente cerca.

En términos más generales, considero que el objetivo de los rectángulos más grandes primero es un enfoque "suficientemente bueno" para esta aplicación. Sin embargo, observo que si el objetivo es encontrar el conjunto mínimo (el número más bajo) de rectángulos para cubrir completamente varias áreas, la solución se vería así:

. 3 . 5 6 8 1 3 4 5 6 8 . 3 4 5 . 8 2 3 4 5 7 8 . 3 . 5 7 8

Este segundo objetivo en realidad representa una solución más óptima al problema, ya que menos rectángulos generalmente significa menos comandos enviados a Dwarf Fortress. Sin embargo, este enfoque me parece más cercano a NP-Hard, basado en mi limitado conocimiento de matemáticas.

Mire el video si desea comprender mejor la estrategia general; No he abordado otros aspectos del proceso de Quickfort, como encontrar la ruta del cursor más corta que traza todos los rectángulos. Posiblemente haya una solución a este problema que combine de manera coherente estas múltiples estrategias.

Se agradecería ayuda de cualquier forma.

En mi opinión, todas las soluciones que encuentran un conjunto de rectángulos que cubren el área original son correctas. Encontrar un conjunto más pequeño de rectángulos es mejor porque comprime / funciona mejor.

Por eso no aconsejaría tratar de encontrar la solución óptima. (Supongo que es NP-duro también).

Para una solución de ejecución más rápida, podría agrupar inicialmente la matriz en grupos de 4 celdas e intentar fusionarlas si son iguales. Después de eso, puedes fusionar grupos de 4 grupos, si son iguales. Y hazlo recursivamente si has terminado.

Esto no encontrará la solución óptima pero será muy rápido. Si sus matrices son grandes, con grandes áreas contiguas, la diferencia con el óptimo no será tan grande.

Encontré el artículo Algoritmos rápidos para particionar polígonos rectilíneos simples de San-Yuan Wu y Sartaj Sahni, que podrían ser de su interés. En su ejemplo, la región con el carácter ''d'' forma un polígono rectilíneo, también las regiones con ''c'' y ''.''. Este artículo incluye algoritmos para polígonos rectilíneos simples sin orificios .

Si un polígono incluye orificios, hay algoritmos que se ejecutan con tiempo O (n ^ 3/2 log n), como indica JM Keil en el documento Descomposición del polígono en la página 11.

Si la minimización de la longitud total de los segmentos de línea introducidos en el proceso de partición es el otro criterio de optimización , el problema se vuelve NP-completo si el polígono contiene agujeros (página 12). Para estos problemas existen algoritmos de aproximación (el documento se refiere a los documentos con tales algoritmos). Si el polígono no contiene agujeros, hay un algoritmo de tiempo O (n ^ 4).

Esto no es realmente una respuesta, pero utilizando una búsqueda ingenua puedes obtener

. 1 . 2 3 3 4 1 5 2 3 3 . 1 5 2 . 6 7 1 5 2 8 6 . 1 . 2 8 6

Básicamente, comienza desde la esquina superior izquierda y la usa como la esquina superior izquierda de su próximo rectángulo, luego verifica hasta dónde puede extenderla hacia la derecha y hacia abajo, luego encuentra la celda superior e izquierda de los bits restantes y así sucesivamente. .

Es probable que esto sea muy ineficaz en algunos casos, pero es rápido ya que no tiene que volver a calcular nada.