| Bytes | Lang | Time | Link |
|---|---|---|---|
| nan | Scratch | 250718T110153Z | Rhaixer |
| nan | 140830T154847Z | trichopl | |
| nan | 140824T135601Z | Arnaud | |
| nan | 140820T025450Z | Arnaud | |
| 361 | Python Hilbert curve | 140818T220709Z | Falko |
| nan | 140818T194032Z | Roy van |
Scratch, dot matrix style
Try it on Scratch
Try it on TurboWarp
Works practically the same way as @Roy van Rijn's answer, which I didn't realize until I looked through the other answers more carefully.
Uses a modified color detector script which checks only grayscale colors (of which there are 256 - so much faster). "Dips" are then drawn based on how dark the current pixel is.
Run this in TurboWarp with High Quality Pen and Turbo Mode on. Otherwise the image will bear anti-aliasing effects.
Add your own images as costumes in the suite sprite, and navigate through them using the right and left arrow keys. Hit space once you've selected your desired image.
Tip: if you're seeing a monkey, try squinting your eyes or making the image smaller
Python 3.4 - Traveling Salesman Problem
The program creates a dithered image from the original:
For each black pixel a point is randomly generated near the pixel centre and these points are treated as a traveling salesman problem. The program saves an html file containing an SVG image at regular intervals as it attempts to reduce the path length. The path starts out self intersecting and gradually becomes less so over a number of hours. Eventually the path is no longer self intersecting:
'''
Traveling Salesman image approximation.
'''
import os.path
from PIL import Image # This uses Pillow, the PIL fork for Python 3.4
# https://pypi.python.org/pypi/Pillow
from random import random, sample, randrange, shuffle
from time import perf_counter
def make_line_picture(image_filename):
'''Save SVG image of closed curve approximating input image.'''
input_image_path = os.path.abspath(image_filename)
image = Image.open(input_image_path)
width, height = image.size
scale = 1024 / width
head, tail = os.path.split(input_image_path)
output_tail = 'TSP_' + os.path.splitext(tail)[0] + '.html'
output_filename = os.path.join(head, output_tail)
points = generate_points(image)
population = len(points)
save_dither(points, image)
grid_cells = [set() for i in range(width * height)]
line_cells = [set() for i in range(population)]
print('Initialising acceleration grid')
for i in range(population):
recalculate_cells(i, width, points, grid_cells, line_cells)
while True:
save_svg(output_filename, width, height, points, scale)
improve_TSP_solution(points, width, grid_cells, line_cells)
def save_dither(points, image):
'''Save a copy of the dithered image generated for approximation.'''
image = image.copy()
pixels = list(image.getdata())
pixels = [255] * len(pixels)
width, height = image.size
for p in points:
x = int(p[0])
y = int(p[1])
pixels[x+y*width] = 0
image.putdata(pixels)
image.save('dither_test.png', 'PNG')
def generate_points(image):
'''Return a list of points approximating the image.
All points are offset by small random amounts to prevent parallel lines.'''
width, height = image.size
image = image.convert('L')
pixels = image.getdata()
points = []
gap = 1
r = random
for y in range(2*gap, height - 2*gap, gap):
for x in range(2*gap, width - 2*gap, gap):
if (r()+r()+r()+r()+r()+r())/6 < 1 - pixels[x + y*width]/255:
points.append((x + r()*0.5 - 0.25,
y + r()*0.5 - 0.25))
shuffle(points)
print('Total number of points', len(points))
print('Total length', current_total_length(points))
return points
def current_total_length(points):
'''Return the total length of the current closed curve approximation.'''
population = len(points)
return sum(distance(points[i], points[(i+1)%population])
for i in range(population))
def recalculate_cells(i, width, points, grid_cells, line_cells):
'''Recalculate the grid acceleration cells for the line from point i.'''
for j in line_cells[i]:
try:
grid_cells[j].remove(i)
except KeyError:
print('grid_cells[j]',grid_cells[j])
print('i',i)
line_cells[i] = set()
add_cells_along_line(i, width, points, grid_cells, line_cells)
for j in line_cells[i]:
grid_cells[j].add(i)
def add_cells_along_line(i, width, points, grid_cells, line_cells):
'''Add each grid cell that lies on the line from point i.'''
population = len(points)
start_coords = points[i]
start_x, start_y = start_coords
end_coords = points[(i+1) % population]
end_x, end_y = end_coords
gradient = (end_y - start_y) / (end_x - start_x)
y_intercept = start_y - gradient * start_x
total_distance = distance(start_coords, end_coords)
x_direction = end_x - start_x
y_direction = end_y - start_y
x, y = start_x, start_y
grid_x, grid_y = int(x), int(y)
grid_index = grid_x + grid_y * width
line_cells[i].add(grid_index)
while True:
if x_direction > 0:
x_line = int(x + 1)
else:
x_line = int(x)
if x_line == x:
x_line = x - 1
if y_direction > 0:
y_line = int(y + 1)
else:
y_line = int(y)
if y_line == y:
y_line = y - 1
x_line_intersection = gradient * x_line + y_intercept
y_line_intersection = (y_line - y_intercept) / gradient
x_line_distance = distance(start_coords, (x_line, x_line_intersection))
y_line_distance = distance(start_coords, (y_line_intersection, y_line))
if (x_line_distance > total_distance and
y_line_distance > total_distance):
break
if x_line_distance < y_line_distance:
x = x_line
y = gradient * x_line + y_intercept
else:
y = y_line
x = (y_line - y_intercept) / gradient
grid_x = int(x - (x_direction < 0) * (x == int(x)))
grid_y = int(y - (y_direction < 0) * (y == int(y)))
grid_index = grid_x + grid_y * width
line_cells[i].add(grid_index)
def improve_TSP_solution(points, width, grid_cells, line_cells,
performance=[0,0,0], total_length=None):
'''Apply 3 approaches, allocating time to each based on performance.'''
population = len(points)
if total_length is None:
total_length = current_total_length(points)
print('Swapping pairs of vertices')
if performance[0] == max(performance):
time_limit = 300
else:
time_limit = 10
print(' Aiming for {} seconds'.format(time_limit))
start_time = perf_counter()
for n in range(1000000):
swap_two_vertices(points, width, grid_cells, line_cells)
if perf_counter() - start_time > time_limit:
break
time_taken = perf_counter() - start_time
old_length = total_length
total_length = current_total_length(points)
performance[0] = (old_length - total_length) / time_taken
print(' Time taken', time_taken)
print(' Total length', total_length)
print(' Performance', performance[0])
print('Moving single vertices')
if performance[1] == max(performance):
time_limit = 300
else:
time_limit = 10
print(' Aiming for {} seconds'.format(time_limit))
start_time = perf_counter()
for n in range(1000000):
move_a_single_vertex(points, width, grid_cells, line_cells)
if perf_counter() - start_time > time_limit:
break
time_taken = perf_counter() - start_time
old_length = total_length
total_length = current_total_length(points)
performance[1] = (old_length - total_length) / time_taken
print(' Time taken', time_taken)
print(' Total length', total_length)
print(' Performance', performance[1])
print('Uncrossing lines')
if performance[2] == max(performance):
time_limit = 60
else:
time_limit = 10
print(' Aiming for {} seconds'.format(time_limit))
start_time = perf_counter()
for n in range(1000000):
uncross_lines(points, width, grid_cells, line_cells)
if perf_counter() - start_time > time_limit:
break
time_taken = perf_counter() - start_time
old_length = total_length
total_length = current_total_length(points)
performance[2] = (old_length - total_length) / time_taken
print(' Time taken', time_taken)
print(' Total length', total_length)
print(' Performance', performance[2])
def swap_two_vertices(points, width, grid_cells, line_cells):
'''Attempt to find a pair of vertices that reduce length when swapped.'''
population = len(points)
for n in range(100):
candidates = sample(range(population), 2)
befores = [(candidates[i] - 1) % population
for i in (0,1)]
afters = [(candidates[i] + 1) % population for i in (0,1)]
current_distance = sum((distance(points[befores[i]],
points[candidates[i]]) +
distance(points[candidates[i]],
points[afters[i]]))
for i in (0,1))
(points[candidates[0]],
points[candidates[1]]) = (points[candidates[1]],
points[candidates[0]])
befores = [(candidates[i] - 1) % population
for i in (0,1)]
afters = [(candidates[i] + 1) % population for i in (0,1)]
new_distance = sum((distance(points[befores[i]],
points[candidates[i]]) +
distance(points[candidates[i]],
points[afters[i]]))
for i in (0,1))
if new_distance > current_distance:
(points[candidates[0]],
points[candidates[1]]) = (points[candidates[1]],
points[candidates[0]])
else:
modified_points = tuple(set(befores + candidates))
for k in modified_points:
recalculate_cells(k, width, points, grid_cells, line_cells)
return
def move_a_single_vertex(points, width, grid_cells, line_cells):
'''Attempt to find a vertex that reduces length when moved elsewhere.'''
for n in range(100):
population = len(points)
candidate = randrange(population)
offset = randrange(2, population - 1)
new_location = (candidate + offset) % population
before_candidate = (candidate - 1) % population
after_candidate = (candidate + 1) % population
before_new_location = (new_location - 1) % population
old_distance = (distance(points[before_candidate], points[candidate]) +
distance(points[candidate], points[after_candidate]) +
distance(points[before_new_location],
points[new_location]))
new_distance = (distance(points[before_candidate],
points[after_candidate]) +
distance(points[before_new_location],
points[candidate]) +
distance(points[candidate], points[new_location]))
if new_distance <= old_distance:
if new_location < candidate:
points[:] = (points[:new_location] +
points[candidate:candidate + 1] +
points[new_location:candidate] +
points[candidate + 1:])
for k in range(candidate - 1, new_location, -1):
for m in line_cells[k]:
grid_cells[m].remove(k)
line_cells[k] = line_cells[k - 1]
for m in line_cells[k]:
grid_cells[m].add(k)
for k in ((new_location - 1) % population,
new_location, candidate):
recalculate_cells(k, width, points, grid_cells, line_cells)
else:
points[:] = (points[:candidate] +
points[candidate + 1:new_location] +
points[candidate:candidate + 1] +
points[new_location:])
for k in range(candidate, new_location - 3):
for m in line_cells[k]:
grid_cells[m].remove(k)
line_cells[k] = line_cells[k + 1]
for m in line_cells[k]:
grid_cells[m].add(k)
for k in ((candidate - 1) % population,
new_location - 2, new_location - 1):
recalculate_cells(k, width, points, grid_cells, line_cells)
return
def uncross_lines(points, width, grid_cells, line_cells):
'''Attempt to find lines that are crossed, and reverse path to uncross.'''
population = len(points)
for n in range(100):
i = randrange(population)
start_1 = points[i]
end_1 = points[(i + 1) % population]
if not line_cells[i]:
recalculate_cells(i, width, points, grid_cells, line_cells)
for cell in line_cells[i]:
for j in grid_cells[cell]:
if i != j and i != (j+1)%population and i != (j-1)%population:
start_2 = points[j]
end_2 = points[(j + 1) % population]
if are_crossed(start_1, end_1, start_2, end_2):
if i < j:
points[i + 1:j + 1] = reversed(points[i + 1:j + 1])
for k in range(i, j + 1):
recalculate_cells(k, width, points, grid_cells,
line_cells)
else:
points[j + 1:i + 1] = reversed(points[j + 1:i + 1])
for k in range(j, i + 1):
recalculate_cells(k, width, points, grid_cells,
line_cells)
return
def are_crossed(start_1, end_1, start_2, end_2):
'''Return True if the two lines intersect.'''
if end_1[0]-start_1[0] and end_2[0]-start_2[0]:
gradient_1 = (end_1[1]-start_1[1])/(end_1[0]-start_1[0])
gradient_2 = (end_2[1]-start_2[1])/(end_2[0]-start_2[0])
if gradient_1-gradient_2:
intercept_1 = start_1[1] - gradient_1 * start_1[0]
intercept_2 = start_2[1] - gradient_2 * start_2[0]
x = (intercept_2 - intercept_1) / (gradient_1 - gradient_2)
if (x-start_1[0]) * (end_1[0]-x) > 0 and (x-start_2[0]) * (end_2[0]-x) > 0:
return True
def distance(point_1, point_2):
'''Return the Euclidean distance between the two points.'''
return sum((point_1[i] - point_2[i]) ** 2 for i in (0, 1)) ** 0.5
def save_svg(filename, width, height, points, scale):
'''Save a file containing an SVG path of the points.'''
print('Saving partial solution\n')
with open(filename, 'w') as file:
file.write(content(width, height, points, scale))
def content(width, height, points, scale):
'''Return the full content to be written to the SVG file.'''
return (header(width, height, scale) +
specifics(points, scale) +
footer()
)
def header(width, height,scale):
'''Return the text of the SVG header.'''
return ('<?xml version="1.0"?>\n'
'<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"\n'
' "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">\n'
'\n'
'<svg width="{0}" height="{1}">\n'
'<title>Traveling Salesman Problem</title>\n'
'<desc>An approximate solution to the Traveling Salesman Problem</desc>\n'
).format(scale*width, scale*height)
def specifics(points, scale):
'''Return text for the SVG path command.'''
population = len(points)
x1, y1 = points[-1]
x2, y2 = points[0]
x_mid, y_mid = (x1 + x2) / 2, (y1 + y2) / 2
text = '<path d="M{},{} L{},{} '.format(x1, y1, x2, y2)
for i in range(1, population):
text += 'L{},{} '.format(*points[i])
text += '" stroke="black" fill="none" stroke-linecap="round" transform="scale({0},{0})" vector-effect="non-scaling-stroke" stroke-width="3"/>'.format(scale)
return text
def footer():
'''Return the closing text of the SVG file.'''
return '\n</svg>\n'
if __name__ == '__main__':
import sys
arguments = sys.argv[1:]
if arguments:
make_line_picture(arguments[0])
else:
print('Required argument: image file')
The program uses 3 different approaches to improving the solution, and measures the performance per second for each. The time allocated to each approach is adjusted to give the majority of time to whatever approach is best performing at that time.
I initially tried guessing what proportion of time to allocate to each approach, but it turns out that which approach is most effective varies considerably during the course of the process, so it makes a big difference to keep adjusting automatically.
The three simple approaches are:
- Pick two points at random and swap them if this does not increase the total length.
- Pick one point at random and a random offset along the list of points and move it if the length does not increase.
- Pick a line at random and check whether any other line crosses it, reversing any section of path that causes a cross.
For approach 3 a grid is used, listing all of the lines that pass through a given cell. Rather than have to check every line on the page for intersection, only those that have a grid cell in common are checked.
I got the idea for using the traveling salesman problem from a blog post that I saw before this challenge was posted, but I couldn't track it down when I posted this answer. I believe the image in the challenge was produced using a traveling salesman approach too, combined with some kind of path smoothing to remove the sharp turns.
The TSP implementation here is a hybrid approach which I experimented with for fun for this challenge. I hadn't read the linked papers when I posted this. My approach is painfully slow by comparison. Note that my image here uses less than 10,000 points, and takes many hours to converge enough to have no crossing lines. The example image in the link to the papers uses 100,000 points...
The original work on this:
Java - Recursive Path
I start from a 2x3 closed path. I scan each cell of the path and divide it into a new 3x3 sub-path. I try each time to choose the 3x3 sub-path that "looks like" the original picture. I repeat the above process 4 times.
Here is the code:
package divide;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import javax.imageio.ImageIO;
import snake.Image;
public class Divide {
private final static int MULT = 3;
private final static int ITERATIONS = 4;
public static void main(String[] args) throws IOException {
BufferedImage src = ImageIO.read(Image.class.getClassLoader().getResourceAsStream("input.png"));
BufferedImage dest = new BufferedImage(src.getWidth() * MULT, src.getHeight() * MULT, BufferedImage.TYPE_INT_RGB);
for (int y = 0; y < src.getHeight() * MULT; y++) {
for (int x = 0; x < src.getWidth() * MULT; x++) {
dest.getRaster().setPixel(x, y, new int [] {255, 255, 255});
}
}
List<String> tab = new ArrayList<String>();
tab.add("rg");
tab.add("||");
tab.add("LJ");
for (int k = 1; k <= ITERATIONS; k++) {
boolean choose = k>=ITERATIONS-1;
// multiply size by 3
tab = iterate(src, tab, choose);
// fill in the white space - if needed
expand(src, tab, " r", " L", "r-", "L-", choose);
expand(src, tab, "g ", "J ", "-g", "-J", choose);
expand(src, tab, "LJ", " ", "||", "LJ", choose);
expand(src, tab, " ", "rg", "rg", "||", choose);
expand(src, tab, "L-J", " ", "| |", "L-J", choose);
expand(src, tab, " ", "r-g", "r-g", "| |", choose);
expand(src, tab, "| |", "| |", "Lg|", "rJ|", choose);
expand(src, tab, "--", " ", "gr", "LJ", choose);
expand(src, tab, " ", "--", "rg", "JL", choose);
expand(src, tab, "| ", "| ", "Lg", "rJ", choose);
expand(src, tab, " |", " |", "rJ", "Lg", choose);
for (String s : tab) {
System.out.println(s);
}
System.out.println();
}
for (int j = 0; j < tab.size(); j++) {
String line = tab.get(j);
for (int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
int xleft = i * dest.getWidth() / line.length();
int xright = (i+1) * dest.getWidth() / line.length();
int ytop = j * dest.getHeight() / tab.size();
int ybottom = (j+1) * dest.getHeight() / tab.size();
int x = (xleft + xright) / 2;
int y = (ytop + ybottom) / 2;
if (c == '|') {
drawLine(dest, x, ytop, x, ybottom);
}
if (c == '-') {
drawLine(dest, xleft, y, xright, y);
}
if (c == 'L') {
drawLine(dest, x, y, xright, y);
drawLine(dest, x, y, x, ytop);
}
if (c == 'J') {
drawLine(dest, x, y, xleft, y);
drawLine(dest, x, y, x, ytop);
}
if (c == 'r') {
drawLine(dest, x, y, xright, y);
drawLine(dest, x, y, x, ybottom);
}
if (c == 'g') {
drawLine(dest, x, y, xleft, y);
drawLine(dest, x, y, x, ybottom);
}
}
}
ImageIO.write(dest, "png", new File("output.png"));
}
private static void drawLine(BufferedImage dest, int x1, int y1, int x2, int y2) {
int dist = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
for (int i = 0; i <= dist; i++) {
int x = (x1*(dist - i) + x2 * i) / dist;
int y = (y1*(dist - i) + y2 * i) / dist;
dest.getRaster().setPixel(x, y, new int [] {0, 0, 0});
}
}
private static void expand(BufferedImage src, List<String> tab, String p1, String p2, String r1, String r2, boolean choose) {
for (int k = 0; k < (choose ? 2 : 1); k++) {
while (true) {
boolean again = false;
for (int j = 0; j < tab.size() - 1; j++) {
String line1 = tab.get(j);
String line2 = tab.get(j+1);
int baseScore = evaluateLine(src, j, tab.size(), line1) + evaluateLine(src, j+1, tab.size(), line2);
for (int i = 0; i <= line1.length() - p1.length(); i++) {
if (line1.substring(i, i + p1.length()).equals(p1)
&& line2.substring(i, i + p2.length()).equals(p2)) {
String nline1 = line1.substring(0, i) + r1 + line1.substring(i + p1.length());
String nline2 = line2.substring(0, i) + r2 + line2.substring(i + p2.length());
int nScore = evaluateLine(src, j, tab.size(), nline1) + evaluateLine(src, j+1, tab.size(), nline2);
if (!choose || nScore > baseScore) {
tab.set(j, nline1);
tab.set(j+1, nline2);
again = true;
break;
}
}
}
if (again) break;
}
if (!again) break;
}
String tmp1 = r1;
String tmp2 = r2;
r1 = p1;
r2 = p2;
p1 = tmp1;
p2 = tmp2;
}
}
private static int evaluateLine(BufferedImage src, int j, int tabSize, String line) {
int [] color = {0, 0, 0};
int score = 0;
for (int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
int x = i*src.getWidth() / line.length();
int y = j*src.getHeight() / tabSize;
src.getRaster().getPixel(x, y, color);
if (c == ' ' && color[0] >= 128) score++;
if (c != ' ' && color[0] < 128) score++;
}
return score;
}
private static List<String> iterate(BufferedImage src, List<String> tab, boolean choose) {
int [] color = {0, 0, 0};
List<String> tab2 = new ArrayList<String>();
for (int j = 0; j < tab.size(); j++) {
String line = tab.get(j);
String l1 = "", l2 = "", l3 = "";
for (int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
List<String []> candidates = replace(c);
String [] choice = null;
if (choose) {
int best = 0;
for (String [] candidate : candidates) {
int bright1 = 0;
int bright2 = 0;
for (int j1 = 0; j1<3; j1++) {
int y = j*3+j1;
for (int i1 = 0; i1<3; i1++) {
int x = i*3+i1;
char c2 = candidate[j1].charAt(i1);
src.getRaster().getPixel(x*src.getWidth()/(line.length()*3), y*src.getHeight()/(tab.size()*3), color);
if (c2 != ' ') bright1++;
if (color[0] > 128) bright2++;
}
}
int score = Math.abs(bright1 - bright2);
if (choice == null || score > best) {
best = score;
choice = candidate;
}
}
} else {
choice = candidates.get(0);
}
//String [] r = candidates.get(rand.nextInt(candidates.size()));
String [] r = choice;
l1 += r[0];
l2 += r[1];
l3 += r[2];
}
tab2.add(l1);
tab2.add(l2);
tab2.add(l3);
}
return tab2;
}
private static List<String []> replace(char c) {
if (c == 'r') {
return Arrays.asList(
new String[] {
"r-g",
"| L",
"Lg "},
new String[] {
" ",
" r-",
" | "},
new String[] {
" ",
"r--",
"Lg "},
new String[] {
" rg",
" |L",
" | "},
new String[] {
" ",
" r",
" rJ"});
} else if (c == 'g') {
return Arrays.asList(
new String[] {
"r-g",
"J |",
" rJ"},
new String[] {
" ",
"-g ",
" | "},
new String[] {
" ",
"--g",
" rJ"},
new String[] {
"rg ",
"J| ",
" | "},
new String[] {
" ",
"g ",
"Lg "});
} else if (c == 'L') {
return Arrays.asList(
new String[] {
"rJ ",
"| r",
"L-J"},
new String[] {
" | ",
" L-",
" "},
new String[] {
"rJ ",
"L--",
" "},
new String[] {
" | ",
" |r",
" LJ"},
new String[] {
" Lg",
" L",
" "});
} else if (c == 'J') {
return Arrays.asList(
new String[] {
" Lg",
"g |",
"L-J"},
new String[] {
" | ",
"-J ",
" "},
new String[] {
" Lg",
"--J",
" "},
new String[] {
" | ",
"g| ",
"LJ "},
new String[] {
"rJ ",
"J ",
" "});
} else if (c == '-') {
return Arrays.asList(
new String[] {
" rg",
"g|L",
"LJ "},
new String[] {
"rg ",
"J|r",
" LJ"},
new String[] {
" ",
"---",
" "},
new String[] {
"r-g",
"J L",
" "},
new String[] {
" ",
"g r",
"L-J"},
new String[] {
"rg ",
"JL-",
" "},
new String[] {
" rg",
"-JL",
" "},
new String[] {
" ",
"gr-",
"LJ "},
new String[] {
" ",
"-gr",
" LJ"}
);
} else if (c == '|') {
return Arrays.asList(
new String[] {
" Lg",
"r-J",
"Lg "},
new String[] {
"rJ ",
"L-g",
" rJ"},
new String[] {
" | ",
" | ",
" | "},
new String[] {
" Lg",
" |",
" rJ"},
new String[] {
"rJ ",
"| ",
"Lg "},
new String[] {
" Lg",
" rJ",
" | "},
new String[] {
" | ",
" Lg",
" rJ"},
new String[] {
"rJ ",
"Lg ",
" | "},
new String[] {
" | ",
"rJ ",
"Lg "}
);
} else {
List<String []> ret = new ArrayList<String []>();
ret.add(
new String[] {
" ",
" ",
" "});
return ret;
}
}
}
Java - Oscillations
The program draws a closed path and add oscillations whose amplitude and frequency are based on image brightness. The "corners" of path do not have oscillations to make sure the path does not intersects itself.
package trace;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import snake.Image;
public class Main5 {
private final static int MULT = 3;
private final static int ROWS = 80; // must be an even number
private final static int COLS = 40;
public static void main(String[] args) throws IOException {
BufferedImage src = ImageIO.read(Image.class.getClassLoader().getResourceAsStream("input.png"));
BufferedImage dest = new BufferedImage(src.getWidth()*MULT, src.getHeight()*MULT, BufferedImage.TYPE_INT_RGB);
int [] white = {255, 255, 255};
for (int y = 0; y < dest.getHeight(); y++) {
for (int x = 0; x < dest.getWidth(); x++) {
dest.getRaster().setPixel(x, y, white);
}
}
for (int j = 0; j < ROWS; j++) {
if (j%2 == 0) {
for (int i = j==0 ? 0 : 1; i < COLS-1; i++) {
drawLine(dest, src, (i+.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (i+1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS,
i > 1 && i < COLS-2);
}
drawLine(dest, src, (COLS-.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (COLS-.5)*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
} else {
for (int i = COLS-2; i >= (j == ROWS - 1 ? 0 : 1); i--) {
drawLine(dest, src, (i+.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (i+1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS,
i > 1 && i < COLS-2);
}
if (j < ROWS-1) {
drawLine(dest, src, (1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (1.5)*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
}
}
if (j < ROWS-1) {
drawLine(dest, src, 0.5*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, 0.5*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
}
}
ImageIO.write(dest, "png", new File("output.png"));
}
private static void drawLine(BufferedImage dest, BufferedImage src, double x1, double y1, double x2, double y2, boolean oscillate) {
int [] black = {0, 0, 0};
int col = smoothPixel((int)((x1*.5 + x2*.5) / MULT), (int)((y1*.5+y2*.5) / MULT), src);
int fact = (255 - col) / 32;
if (fact > 5) fact = 5;
double dx = y1 - y2;
double dy = - (x1 - x2);
double dist = 2 * (Math.abs(x1 - x2) + Math.abs(y1 - y2)) * (fact + 1);
for (int i = 0; i <= dist; i++) {
double amp = oscillate ? (1 - Math.cos(fact * i*Math.PI*2/dist)) * 12 : 0;
double x = (x1 * i + x2 * (dist - i)) / dist;
double y = (y1 * i + y2 * (dist - i)) / dist;
x += dx * amp / COLS;
y += dy * amp / ROWS;
dest.getRaster().setPixel((int)x, (int)y, black);
}
}
public static int smoothPixel(int x, int y, BufferedImage src) {
int sum = 0, count = 0;
for (int j = -2; j <= 2; j++) {
for (int i = -2; i <= 2; i++) {
if (x + i >= 0 && x + i < src.getWidth()) {
if (y + j >= 0 && y + j < src.getHeight()) {
sum += src.getRGB(x + i, y + j) & 255;
count++;
}
}
}
}
return sum / count;
}
}
Below a comparable algorithm that is based on a spiral. (I know the path does not close and that it certainly intersects, I just post it for the sake of art :-)
Python: Hilbert curve (373 361)
I decided to draw a Hilbert curve with variable granularity depending on the image intensity:
import pylab as pl
from scipy.misc import imresize, imfilter
import turtle
# load image
img = pl.flipud(pl.imread("face.png"))
# setup turtle
levels = 8
size = 2**levels
turtle.setup(img.shape[1] * 4.2, img.shape[0] * 4.2)
turtle.setworldcoordinates(0, 0, size, -size)
turtle.tracer(1000, 0)
# resize and blur image
img = imfilter(imresize(img, (size, size)), 'blur')
# define recursive hilbert curve
def hilbert(level, angle = 90):
if level == 0:
return
if level == 1 and img[-turtle.pos()[1], turtle.pos()[0]] > 128:
turtle.forward(2**level - 1)
else:
turtle.right(angle)
hilbert(level - 1, -angle)
turtle.forward(1)
turtle.left(angle)
hilbert(level - 1, angle)
turtle.forward(1)
hilbert(level - 1, angle)
turtle.left(angle)
turtle.forward(1)
hilbert(level - 1, -angle)
turtle.right(angle)
# draw hilbert curve
hilbert(levels)
turtle.update()
Actually I planned to make decisions on different levels of detail, like "This spot is so bright, I'll stop the recursion and move to the next block!". But evaluating image intensity locally leading to large movements is very inaccurate and looks ugly. So I ended up with only deciding whether to skip level 1 or to draw another Hilbert loop.
Here is the result on the first test image:
Thanks to @githubphagocyte the rendering is pretty fast (using turtle.tracer). Thus I don't have to wait all night for a result and can go to my well-deserved bed. :)
Some code golf
@flawr: "short program"? You haven't seen the golfed version! ;)
So just for fun:
from pylab import*;from scipy.misc import*;from turtle import*
i=imread("f.p")[::-1];s=256;h=i.shape;i=imfilter(imresize(i,(s,s)),'blur')
setup(h[1]*4.2,h[0]*4.2);setworldcoordinates(0,0,s,-s);f=forward;r=right
def h(l,a=90):
x,y=pos()
if l==1and i[-y,x]>128:f(2**l-1)
else:
if l:l-=1;r(a);h(l,-a);f(1);r(-a);h(l,a);f(1);h(l,a);r(-a);f(1);h(l,-a);r(a)
h(8)
(373 361 characters. But it will take forever since I remove the turte.tracer(...) command!)
Animation by flawr
flawr: My algorithm is slightly modified to what @DenDenDo told me: I had to delete some points in every iteration because the convergence would slow down drastically. That's why the curve will intersect itself.
Java : Dot matrix style
Since nobody has answered the question yet I'll give it a shot. First I wanted to fill a canvas with Hilbert curves, but in the end I've opted for a simpler approach:
Here is the code:
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
public class LineArt extends JPanel {
private BufferedImage ref;
//Images are stored in integers:
int[] images = new int[] {31, 475, 14683, 469339};
int[] brightness = new int[] {200,170,120,0};
public static void main(String[] args) throws Exception {
new LineArt(args[0]);
}
public LineArt(String filename) throws Exception {
ref = ImageIO.read(new File(filename));
JFrame frame = new JFrame();
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(ref.getWidth()*5, ref.getHeight()*5);
this.setPreferredSize(new Dimension((ref.getWidth()*5)+20, (ref.getHeight()*5)+20));
frame.add(new JScrollPane(this));
}
@Override
public void paint(Graphics g) {
Graphics2D g2d = (Graphics2D) g;
g2d.setColor(Color.WHITE);
g2d.fillRect(0, 0, getWidth(), getHeight());
g2d.translate(10, 10);
g2d.setColor(Color.BLACK);
g2d.drawLine(0, 0, 4, 0);
g2d.drawLine(0, 0, 0, ref.getHeight()*5);
for(int y = 0; y<ref.getHeight();y++) {
for(int x = 1; x<ref.getWidth()-1;x++) {
int light = new Color(ref.getRGB(x, y)).getRed();
int offset = 0;
while(brightness[offset]>light) offset++;
for(int i = 0; i<25;i++) {
if((images[offset]&1<<i)>0) {
g2d.drawRect((x*5)+i%5, (y*5)+(i/5), 0,0);
}
}
}
g2d.drawLine(2, (y*5), 4, (y*5));
g2d.drawLine((ref.getWidth()*5)-5, (y*5), (ref.getWidth()*5)-1, (y*5));
if(y%2==0) {
g2d.drawLine((ref.getWidth()*5)-1, (y*5), (ref.getWidth()*5)-1, (y*5)+4);
} else {
g2d.drawLine(2, (y*5), 2, (y*5)+4);
}
}
if(ref.getHeight()%2==0) {
g2d.drawLine(0, ref.getHeight()*5, 2, ref.getHeight()*5);
} else {
g2d.drawLine(0, ref.getHeight()*5, (ref.getWidth()*5)-1, ref.getHeight()*5);
}
}
}
Update: Now it creates a cycle, not just a single line