Inspirado por vi.sualize.us
Objetivo
A entrada é uma imagem em escala de cinza e a saída é uma imagem em preto e branco. A imagem de saída consiste em apenas uma curva fechada (loop) que não pode se cruzar com ela mesma ou se tocar. A largura da linha deve ser constante em toda a imagem. O desafio aqui é encontrar um algoritmo para isso. A saída apenas tem que representar a imagem de entrada, mas com qualquer liberdade artística. A resolução não é tão importante, mas a proporção deve permanecer a mesma.
Exemplo
Mais imagens de teste
The width of the line shall be constant throughout the whole image.
Mas ainda uma dica útilRespostas:
Java: estilo de matriz de pontos
Como ninguém respondeu à pergunta ainda, vou tentar. Primeiro, eu queria preencher uma tela com curvas de Hilbert, mas no final optei por uma abordagem mais simples:
Aqui está o código:
Atualização : agora ele cria um ciclo, não apenas uma única linha
fonte
Python: curva de Hilbert (
373361)Decidi desenhar uma curva de Hilbert com granularidade variável, dependendo da intensidade da imagem:
Na verdade, planejei tomar decisões em diferentes níveis de detalhes, como "Este local é tão brilhante que vou parar a recursão e passar para o próximo bloco!". Mas avaliar a intensidade da imagem localmente, levando a grandes movimentos, é muito impreciso e parece feio. Então acabei decidindo pular o nível 1 ou desenhar outro loop de Hilbert.
Aqui está o resultado na primeira imagem de teste:
Graças a @githubphagocyte, a renderização é bem rápida (usando
turtle.tracer
). Portanto, não tenho que esperar a noite toda por um resultado e posso ir para a minha merecida cama. :)Algum código de golfe
@ flawr: "programa curto"? Você ainda não viu a versão do golfe! ;)
Então, apenas por diversão:
(
373361 caracteres. Mas levará uma eternidade desde que eu remova oturte.tracer(...)
comando!)Animação por flawr
flawr: Meu algoritmo está ligeiramente modificado para o que o @DenDenDo me disse: eu tive que excluir alguns pontos em cada iteração porque a convergência diminuiria drasticamente. É por isso que a curva se cruza.
fonte
screen.tracer(0)
vez deturtle.speed(0)
. Pode ser necessário instanciar a tela no início, mas se for a única instância da tela, todas as suas tartarugas serão automaticamente atribuídas a ela. Então,screen.update()
no final, para exibir os resultados. Fiquei espantado com a diferença de velocidade quando eu descobri isso ... primeiroPython 3.4 - Problema do vendedor ambulante
O programa cria uma imagem pontilhada a partir do original:
Para cada pixel preto, um ponto é gerado aleatoriamente próximo ao centro do pixel e esses pontos são tratados como um problema de vendedor ambulante . O programa salva um arquivo html contendo uma imagem SVG em intervalos regulares, enquanto tenta reduzir o comprimento do caminho. O caminho começa a se auto-interceptar e gradualmente se torna menos ao longo de várias horas. Eventualmente, o caminho não é mais auto-interceptado:
O programa usa 3 abordagens diferentes para melhorar a solução e mede o desempenho por segundo de cada um. O tempo alocado para cada abordagem é ajustado para dedicar a maior parte do tempo a qualquer abordagem com melhor desempenho naquele momento.
Inicialmente, tentei adivinhar qual a proporção de tempo a ser alocada para cada abordagem, mas acontece que a abordagem mais eficaz varia consideravelmente durante o processo, portanto, faz uma grande diferença continuar ajustando automaticamente.
As três abordagens simples são:
Para a abordagem 3, uma grade é usada, listando todas as linhas que passam por uma determinada célula. Em vez de precisar verificar todas as linhas da página em busca de interseção, apenas as que possuem uma célula de grade em comum são verificadas.
Tive a idéia de usar o problema do vendedor ambulante em uma postagem de blog que vi antes do lançamento deste desafio, mas não consegui encontrá-lo quando publiquei esta resposta. Acredito que a imagem no desafio foi produzida usando uma abordagem de vendedor ambulante, combinada com algum tipo de suavização de caminho para remover as curvas fechadas.
Ainda não consigo encontrar o post específico do blog, mas agora encontrei referência aos documentos originais nos quais a Mona Lisa foi usada para demonstrar o problema do vendedor ambulante .
A implementação do TSP aqui é uma abordagem híbrida com a qual experimentei por diversão para este desafio. Eu não tinha lido os papéis vinculados quando publiquei isso. Minha abordagem é dolorosamente lenta em comparação. Observe que minha imagem aqui usa menos de 10.000 pontos e leva muitas horas para convergir o suficiente para não ter linhas de cruzamento. A imagem de exemplo no link para os documentos usa 100.000 pontos ...
Infelizmente, a maioria dos links parece estar morta agora, mas o artigo "TSP Art" de Craig S Kaplan e Robert Bosch 2005 ainda funciona e fornece uma visão geral interessante das diferentes abordagens.
fonte
Java - Oscilações
O programa desenha um caminho fechado e adiciona oscilações cuja amplitude e frequência são baseadas no brilho da imagem. Os "cantos" do caminho não têm oscilações para garantir que o caminho não se cruze.
Abaixo de um algoritmo comparável baseado em uma espiral. ( Eu sei que o caminho não fecha e que certamente se cruza , eu apenas o coloco em nome da arte :-)
fonte
Java - Caminho Recursivo
Eu começo de um caminho fechado 2x3. Examino cada célula do caminho e divido-a em um novo subcaminho 3x3. Tento cada vez que escolher o subcaminho 3x3 que "se parece" com a imagem original. Repito o processo acima 4 vezes.
Aqui está o código:
fonte