Hace poco descubrí el famoso problema de geometría de la galería de arte.
Reel explicativo aquí
Me dio curiosidad como en diversos estudios se ponía una cota máxima al número máximo de guardias necesarios, pero no había documentada una formula para obtener el mínimo exacto o en que posiciones se deben colocar.
Así que me puse a analizarlo, y esta fue la forma que descubrí para resolverlo por mi cuenta:
Bueno, pues el mapa de prueba que me hice fue el de abajo a continuación ya que es bastante sencillo y era un caso muy concreto donde solo se necesitan dos guardias, y una de las paredes (la superior) puede ser vigilada un fragmento por un guardia, y el otro fragmento por el otro guardia.
Lo primero que hice para tener en cuenta este posible escenario, fue buscar todos los ángulos "abiertos" de la figura, y proyectar las lineas de forma que generamos nuevos vertices en la figura.
Ahora iteramos las lineas ya subdivididas (verde) y obtenemos para cada una el area desde donde esta es visible (coloreada de rojo), que viene a ser la intersección del area visible de sus dos vertices.
Vamos a continuar pero quiero que veáis lo que pasa con los siguientes 5:
Lo mismo pasa con los dos primeros que calculamos y el que viene a continuación
Cada area aquí es un subconjunto de la anterior, siendo las dos últimas incluso idénticas. El tema es que si necesitas al menos un guardia necesariamente en un subconjunto pequeño de otro más grande, ese guardia de ese subconjunto ya estará también en los grandes, por lo que podemos obviarlos.
Total, que al final las areas calculadas que nos quedan son las siguientes:
Así que ahora solo nos queda colocar guardias de forma que haya al menos 1 en cada zona de color rojo. Esto lo haremos calculando todas las combinaciones de posibles intersecciones, que nos pueden dar:- Un sub-area
- Un único vértice
- Intersección vacía ∅
Si fuésemos a calcularlo en un programa, usaríamos algoritmo de backtracking.
Para este ejemplo simple, la solución sería 2 guardias: el primero en la intersección del area 1 y 2, y el segundo en la intersección del area 3 y 4.
En otros mapas podrían haber intersecciones de 3 areas a la vez, o incluso dejar tal cual alguno de los areas calculados sin intersecciones con otras areas.
¡Y ya esta! ¿Dudas? ¿Comentarios? ¿Sugerencias?
