Algoritmo de eclosión de rectángulo óptimo

Question

Estoy buscando un algoritmo para sombrear un rectángulo con la longitud de línea total más corta, para que un objeto de área determinada pueda pasar a través de la eclosión.

Por ejemplo, dado un rectángulo de 5x3 cm, y tramo con líneas paralelas de 1 cm de ancho, el objeto más grande que puedo pasar a través de la escotilla es un cuadrado de 1 cm de lado. He utilizado un total de 22 cm (es decir, 4x3 + 2x5) de líneas de sombreado. Así que para pasar un área de 1 cm2, he usado 22 cm de líneas de sombreado.

El algoritmo debe encontrar un patrón que minimice las líneas de sombreado generales a partir de los 22 cm actuales, mientras que no permite que pase un área con más de 1 cm2 (no es necesario que el objeto tenga la forma de un cuadrado o un rectángulo, es el área general que asuntos).

Editar: Siguiendo el ejemplo de nlucaroni, encontré la Conjetura de Honeycomb que indica que cualquier partición del plano en regiones de área igual tiene perímetro al menos el de la cuadrícula hexagonal regular, que responde a mi pregunta parcialmente.

Answer 1

Necesita formas que formen una tessellation . El hexágono es probablemente tu mejor apuesta. Sin embargo, ¿qué sucede si la forma por la que está pasando no se ajusta exactamente al patrón de teselación?

Observe las teselaciones y averigüe si su patrón / pantalla / sombreado tiene que ser regular o no, tiene que ajustarse al objeto que se está probando, etc.

si de hecho lo está construyendo a partir de infinitas líneas rectas que forman áreas = 1, entonces lo mejor que puede hacer es un cuadrado (adelante, encuentre el máximo del área con respecto a la proporción de lados, o encuentre perímetro con respecto a la relación de lados tomando la derivada).

tu pregunta es bastante vaga / incompleta, s, esto es todo lo que tengo para ti.

Answer 2

Problema limpio. Sospecho que el algoritmo va a ser realmente simple, sin embargo, debe haber algún " óptimo " conjunto de ángulos de pantalla para usar que minimizan el tamaño de apertura para una longitud de cable determinada.

En realidad, esto me recuerda un poco el problema del corte de la torta, en el que estás tratando de encontrar la cantidad mínima de cortes rectos para hacer x rebanadas de torta. Por lo tanto, la solución puede ser a lo largo de las líneas de, para cada cable, tratar de hacer la mayor reducción en el tamaño del objeto más grande que puede pasar. Eso significaría cortar los "agujeros" más grandes " por la mitad con cada cable agregado, cuando sea posible.

editar: cuando probé el algoritmo propuesto, obtuve resultados que eran peores que la versión ingenua. Definitivamente, debe tener en cuenta el tamaño mínimo al colocar los cables.

Answer 3

¿Qué significa sombrear un rectángulo?

¿Puedes reformular tu pregunta?

También, durante la reformulación, indique qué debe recibir el algoritmo como entrada y qué debe producir como salida.