Inspirado por vi.sualize.us
Gol
La entrada es una imagen en escala de grises y la salida es una imagen en blanco y negro. La imagen de salida consta de una sola curva cerrada (bucle) que no puede cruzarse consigo misma ni tocarse. El ancho de la línea será constante en toda la imagen. El desafío aquí es encontrar un algoritmo para hacerlo. La salida solo tiene que representar la imagen de entrada, pero con cualquier libertad artística. La resolución no es tan importante, pero la relación de aspecto debería ser la misma.
Ejemplo
Más imágenes de prueba
The width of the line shall be constant throughout the whole image.
Pero sigue siendo una pista útilRespuestas:
Java: estilo de matriz de puntos
Como nadie ha respondido la pregunta todavía, lo intentaré. Primero quería llenar un lienzo con curvas de Hilbert, pero al final opté por un enfoque más simple:
Aquí está el código:
Actualización : ahora crea un ciclo, no solo una sola línea
fuente
Python: curva de Hilbert (
373361)Decidí dibujar una curva de Hilbert con granularidad variable dependiendo de la intensidad de la imagen:
En realidad, planeé tomar decisiones en diferentes niveles de detalle, como "¡Este lugar es tan brillante que detendré la recursión y pasaré al siguiente bloque!". Pero evaluar la intensidad de la imagen localmente que conduce a grandes movimientos es muy impreciso y se ve feo. Así que terminé con solo decidir si omitir el nivel 1 o dibujar otro bucle de Hilbert.
Aquí está el resultado en la primera imagen de prueba:
Gracias a @githubphagocyte el renderizado es bastante rápido (usando
turtle.tracer
). Por lo tanto, no tengo que esperar toda la noche para obtener un resultado y puedo ir a mi cama merecida. :)Algún código de golf
@flawr: "programa corto"? ¡No has visto la versión de golf! ;)
Así que solo por diversión:
(
373361 caracteres. ¡Pero tomará una eternidad desde que elimino elturte.tracer(...)
comando!)Animación por flawr
flawr: mi algoritmo está ligeramente modificado a lo que @DenDenDo me dijo: tuve que eliminar algunos puntos en cada iteración porque la convergencia se ralentizaría drásticamente. Es por eso que la curva se cruzará sola.
fuente
screen.tracer(0)
lugar de hacerloturtle.speed(0)
. Es posible que deba crear una instancia de la pantalla al comienzo, pero si es la única instancia de pantalla, todas sus tortugas se asignarán automáticamente a ella. Luego, justoscreen.update()
al final para mostrar los resultados. Me sorprendió la diferencia de velocidad cuando descubrí esto por primera vez ...Python 3.4 - Problema de vendedor ambulante
El programa crea una imagen difuminada del original:
Para cada píxel negro, se genera aleatoriamente un punto cerca del centro de píxeles y estos puntos se tratan como un problema de vendedor ambulante . El programa guarda un archivo html que contiene una imagen SVG a intervalos regulares mientras intenta reducir la longitud de la ruta. El camino comienza a auto intersectarse y gradualmente se vuelve menos durante varias horas. Finalmente, el camino ya no se auto intersecta:
El programa utiliza 3 enfoques diferentes para mejorar la solución y mide el rendimiento por segundo para cada uno. El tiempo asignado a cada enfoque se ajusta para dar la mayor parte del tiempo a cualquier enfoque que tenga el mejor rendimiento en ese momento.
Inicialmente intenté adivinar qué proporción de tiempo asignar a cada enfoque, pero resulta que el enfoque que es más efectivo varía considerablemente durante el curso del proceso, por lo que es muy importante seguir ajustándose automáticamente.
Los tres enfoques simples son:
Para el enfoque 3, se utiliza una cuadrícula que enumera todas las líneas que pasan a través de una celda determinada. En lugar de tener que verificar la intersección de cada línea de la página, solo se verifican las que tienen una celda de cuadrícula en común.
Se me ocurrió la idea de utilizar el problema del vendedor ambulante de una publicación de blog que vi antes de que se publicara este desafío, pero no pude localizarlo cuando publiqué esta respuesta. Creo que la imagen en el desafío también se produjo utilizando un enfoque de vendedor ambulante, combinado con algún tipo de suavizado de ruta para eliminar las curvas cerradas.
Todavía no puedo encontrar la publicación específica del blog, pero ahora he encontrado referencias a los documentos originales en los que se utilizó la Mona Lisa para demostrar el problema del vendedor ambulante .
La implementación de TSP aquí es un enfoque híbrido con el que experimenté por diversión para este desafío. No había leído los documentos vinculados cuando publiqué esto. Mi enfoque es dolorosamente lento en comparación. Tenga en cuenta que mi imagen aquí usa menos de 10,000 puntos, y toma muchas horas para converger lo suficiente como para no tener líneas de cruce. La imagen de ejemplo en el enlace a los documentos usa 100,000 puntos ...
Desafortunadamente, la mayoría de los enlaces parecen estar muertos ahora, pero el documento "TSP Art" de Craig S Kaplan & Robert Bosch 2005 todavía funciona y ofrece una visión general interesante de diferentes enfoques.
fuente
Java - Oscilaciones
El programa dibuja un camino cerrado y agrega oscilaciones cuya amplitud y frecuencia se basan en el brillo de la imagen. Las "esquinas" de la ruta no tienen oscilaciones para asegurarse de que la ruta no se cruza entre sí.
Debajo de un algoritmo comparable que se basa en una espiral. ( Sé que el camino no se cierra y que ciertamente se cruza , solo lo publico en aras del arte :-)
fuente
Java - Ruta recursiva
Comienzo desde un camino cerrado de 2x3. Escaneo cada celda de la ruta y la divido en una nueva subruta 3x3. Intento cada vez elegir la ruta secundaria 3x3 que "se parece" a la imagen original. Repito el proceso anterior 4 veces.
Aquí está el código:
fuente