Inspiriert von vi.sualize.us
Tor
Die Eingabe ist ein Graustufenbild und die Ausgabe ist ein Schwarzweißbild. Das Ausgabebild besteht nur aus einer geschlossenen Kurve (Schleife), die sich nicht mit sich selbst schneiden oder sich selbst berühren darf. Die Breite der Linie muss über das gesamte Bild konstant sein. Die Herausforderung besteht darin, einen Algorithmus dafür zu finden. Die Ausgabe muss nur das Eingabebild darstellen, aber mit jeder künstlerischen Freiheit. Die Auflösung ist nicht so wichtig, aber das Seitenverhältnis sollte ungefähr gleich bleiben.
Beispiel
Weitere Testbilder
popularity-contest
graphical-output
image-processing
fehlerhaft
quelle
quelle
The width of the line shall be constant throughout the whole image.
Aber immer noch ein nützlicher HinweisAntworten:
Java: Punktmatrix-Stil
Da noch niemand die Frage beantwortet hat, werde ich es versuchen. Zuerst wollte ich eine Leinwand mit Hilbert-Kurven füllen, aber am Ende habe ich mich für einen einfacheren Ansatz entschieden:
Hier ist der Code:
Update : Jetzt wird ein Zyklus erstellt, nicht nur eine einzelne Zeile
quelle
Python: Hilbert-Kurve (
373361)Ich habe beschlossen, eine Hilbert-Kurve mit variabler Granularität in Abhängigkeit von der Bildintensität zu zeichnen:
Eigentlich hatte ich vor, Entscheidungen auf verschiedenen Detailebenen zu treffen, wie "Dieser Punkt ist so hell, dass ich die Rekursion stoppen und zum nächsten Block übergehen werde!". Die Auswertung der Bildintensität vor Ort, die zu großen Bewegungen führt, ist jedoch sehr ungenau und sieht hässlich aus. Also habe ich mich nur entschieden, ob ich Level 1 überspringen oder eine andere Hilbert-Schleife zeichnen soll.
Hier ist das Ergebnis auf dem ersten Testbild:
Dank @githubphagocyte ist das Rendern ziemlich schnell (mit
turtle.tracer
). So muss ich nicht die ganze Nacht auf ein Ergebnis warten und kann in mein wohlverdientes Bett gehen. :)Ein bisschen Code Golf
@flawr: "kurzes programm"? Sie haben die Golfversion noch nicht gesehen! ;)
Also nur zum Spaß:
(
373361 Zeichen. Aber es wird ewig dauern, bis ich denturte.tracer(...)
Befehl entferne !)Animation von flawr
flawr: Mein Algorithmus wurde leicht modifiziert, was @DenDenDo mir sagte: Ich musste einige Punkte in jeder Iteration löschen, da sich die Konvergenz drastisch verlangsamen würde. Deshalb schneidet sich die Kurve von selbst.
quelle
screen.tracer(0)
stattturtle.speed(0)
. Möglicherweise müssen Sie den Bildschirm zu Beginn instanziieren, aber wenn dies die einzige Instanz des Bildschirms ist, werden alle Ihre Schildkröten automatisch ihm zugewiesen. Dann erstscreen.update()
am Ende die Ergebnisse anzeigen. Ich war erstaunt über den Geschwindigkeitsunterschied, als ich diesen entdeckte ...Python 3.4 - Problem mit Handlungsreisenden
Das Programm erstellt aus dem Original ein gedithertes Bild:
Für jedes schwarze Pixel wird zufällig ein Punkt in der Nähe der Pixelmitte generiert, und diese Punkte werden als ein Problem des Handlungsreisenden behandelt . Das Programm speichert in regelmäßigen Abständen eine HTML-Datei mit einem SVG-Bild, um die Pfadlänge zu verringern. Der Pfad beginnt sich selbst zu kreuzen und wird im Laufe der Stunden immer kürzer. Schließlich schneidet sich der Pfad nicht mehr selbst:
Das Programm verwendet drei verschiedene Ansätze zur Verbesserung der Lösung und misst die Leistung pro Sekunde für jeden. Die jedem Ansatz zugewiesene Zeit wird so angepasst, dass der Großteil der Zeit für den jeweils besten Ansatz zur Verfügung steht.
Ich habe anfangs versucht zu erraten, wie viel Zeit jedem Ansatz zugewiesen werden muss, aber es stellt sich heraus, dass der effektivste Ansatz im Verlauf des Prozesses sehr unterschiedlich ist. Daher ist es ein großer Unterschied, die automatische Anpassung fortzusetzen.
Die drei einfachen Ansätze sind:
Für Ansatz 3 wird ein Raster verwendet, in dem alle Linien aufgelistet sind, die durch eine bestimmte Zelle verlaufen. Anstatt jede Linie auf der Seite auf Schnittpunkte prüfen zu müssen, werden nur diejenigen geprüft, die eine gemeinsame Rasterzelle haben.
Ich hatte die Idee, das Problem des Handlungsreisenden in einem Blog-Post zu verwenden, den ich vor dem Posten dieser Herausforderung gesehen hatte, aber ich konnte es nicht aufspüren, als ich diese Antwort veröffentlichte. Ich glaube, das Bild in der Herausforderung wurde auch mit einem Verkäufer-Reiseansatz erstellt, kombiniert mit einer Art Wegeglättung, um die scharfen Kurven zu beseitigen.
Ich kann den spezifischen Blog-Beitrag immer noch nicht finden, aber ich habe jetzt einen Verweis auf die Originalarbeiten gefunden, in denen die Mona Lisa verwendet wurde, um das Problem der reisenden Verkäufer zu demonstrieren .
Die TSP-Implementierung hier ist ein hybrider Ansatz, mit dem ich zum Spaß für diese Herausforderung experimentiert habe. Ich hatte die verlinkten Artikel nicht gelesen, als ich das gepostet habe. Meine Annäherung ist im Vergleich dazu schmerzlich langsam. Beachten Sie, dass mein Bild hier weniger als 10.000 Punkte verwendet und viele Stunden benötigt, um so weit zu konvergieren, dass sich keine Linien kreuzen. Das Beispielbild im Link zu den Beiträgen verwendet 100.000 Punkte ...
Leider scheinen die meisten Links jetzt tot zu sein, aber die Arbeit "TSP Art" von Craig S. Kaplan & Robert Bosch 2005 funktioniert immer noch und gibt einen interessanten Überblick über verschiedene Ansätze.
quelle
Java - Schwingungen
Das Programm zeichnet einen geschlossenen Pfad und fügt Oszillationen hinzu, deren Amplitude und Frequenz von der Bildhelligkeit abhängen. Die "Ecken" des Pfades haben keine Schwingungen, um sicherzustellen, dass sich der Pfad nicht selbst schneidet.
Unten ein vergleichbarer Algorithmus, der auf einer Spirale basiert. ( Ich weiß, dass der Weg nicht schließt und dass er sich sicherlich schneidet , ich poste ihn nur der Kunst zuliebe :-)
quelle
Java - Rekursiver Pfad
Ich gehe von einem 2x3 geschlossenen Pfad aus. Ich scanne jede Zelle des Pfades und teile ihn in einen neuen 3x3-Unterpfad. Ich versuche jedes Mal, den 3x3-Unterpfad zu wählen, der dem Originalbild "ähnelt". Ich wiederhole den obigen Vorgang viermal.
Hier ist der Code:
quelle