Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by vi.sualize.us

Goal

The input is a grayscale image and the output is a black and white image. The output image consists of just one closed curve (loop) that is not allowed to intersect with itself or touch itself. The width of the line shall be constant throughout the whole image. The challenge here is finding an algorithm for doing so. The output just has to represent the input image, but with any artistic freedom. The resolution is not so important but the aspect ratio should stay about the same.

Example

enter image description here enter image description here

More test images

loch ness sky scraper einstein checker

share|improve this question
1  
You might want to put some restriction on the relative resolutions. Otherwise one could just increase the resolution considerably (say a factor of 32 or something), and then replace each pixel with a 32x32 block of appropriate average intensity. It should be easy enough to make the blocks all connect and them arrange them in such a way that everything connects to a single loop. –  Martin Büttner Aug 18 at 18:21
1  
If the line can't touch itself, no dark areas, the darker shade will be a 50% gray –  edc65 Aug 18 at 19:26
1  
@Martin The width of the line shall be constant throughout the whole image. But still a useful hint –  edc65 Aug 18 at 20:40
1  
@edc65 Yes constant, but you can still make it wider than a pixel (constantly) in which case you can have two parts of the line separated by one pixel and then that area will be darker than 50% average intensity. –  Martin Büttner Aug 18 at 20:47
2  
@githubphagocyte Primarly the image should be in black and white, but it does not matter if it contains anti aliasing effects. And you should try to avoid this situation of diagonally touching pixels, but again, if this happens only a few times in the image it will be ok, as long as you do not use it systematically. Thank you for the input. @ edc65: Yes I am aware of that, the goal is that the viewer can still identify one distinct line on the image (when zooming in). –  flawr Aug 19 at 7:34

6 Answers 6

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:

dot matrix style mona lisa

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

share|improve this answer
2  
Very nice and simple solution, I didn't imagine that way of solving it but it looks great! –  flawr Aug 19 at 7:45
    
@DenDenDo suggested plotting a curve shortening flow animation. It would be great if you could provide a textfile (csv or whatever you want) with the coordinates of all conrner points that you used in the right order. I made a matlab script for calculating the animation - but of course you are also free to do it yourself=) –  flawr Aug 19 at 17:48

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:

result

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.

enter image description here

share|improve this answer
1  
Nicely done! If you want faster running, try screen.tracer(0) instead of turtle.speed(0). You might need to instantiate screen at the start, but if it's the only instance of screen all your turtles will automatically be assigned to it. Then just screen.update() at the end to display the results. I was amazed at the speed difference when I first discovered this... –  githubphagocyte Aug 18 at 22:16
    
I was really surprised that you were able to do it in such a short program! But anyway, congrats! fractals ftw=) –  flawr Aug 19 at 7:43
    
@DenDenDo suggested plotting a curve shortening flow animation. It would be great if you could provide a textfile (csv or whatever you want) with the coordinates of all conrner points that you used in the right order. I made a matlab script for calculating the animation - but of course you are also free to do it yourself=) –  flawr Aug 19 at 17:50
    
@flawr: Here we go. –  Falko Aug 19 at 18:09
    
So here's the code: pastebin.com/wTcwb0nm –  flawr Aug 19 at 19:56

Python 3.4 - Traveling Salesman Problem

The program creates a dithered image from the original:

enter image description here enter image description here

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:

enter image description here

enter image description here

'''
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:

  1. Pick two points at random and swap them if this does not increase the total length.
  2. Pick one point at random and a random offset along the list of points and move it if the length does not increase.
  3. 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.

share|improve this answer
    
Wow, thats really nice=) (If you want me to do a curve shortening flow animation too just provide a csv or something similar with an ordered list of the point coordinates.) –  flawr Aug 30 at 17:43
    
@flawr thank you! As for the ordered list of point coordinates, it's almost 10,000 points for the mona lisa face. It would be nearer 100,000 points for the bigger images. That's why I haven't posted the SVG text here... :) –  githubphagocyte Aug 30 at 19:09
    
Well you could use pastebin.com or something similar, but I do not want to force you, it's your decision (I am not good at Python=) –  flawr Aug 30 at 19:27
    
@flawr I wouldn't want you to have to wait hours and hours for the program to run. I won't be adding a flow animation to my answer but if you want the points for yourself let me know and I can find somewhere to post them... –  githubphagocyte Aug 30 at 20:56

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.

enter image description here

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 :-)

enter image description here

share|improve this answer
    
I particularly like the visual effect of the spiral! –  Will Aug 20 at 5:36
    
Me too, thanks for sharing! (If you want you can also make a an ordered list of path points and I'll see whether I can do an animation with this one too=) –  flawr Aug 20 at 7:11
    
@github Thanks for your constructive comments. –  Super Chafouin Aug 24 at 5:14
1  
+1 from me - it fits the rules perfectly now, and I love the smooth transitions that the changing frequency gives. –  githubphagocyte Aug 24 at 8:54

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.

enter image description here

enter image description here

enter image description here

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;
        }

    }
}
share|improve this answer
2  
This looks like one of the most innovative solutions so far! +1 for Batman=) –  flawr Aug 24 at 14:36
    
I love this one. –  githubphagocyte Aug 25 at 14:02

Mathematica FindShortestTour

After a demonstration by Charles Pooh

sketch[img_]:=
Module[{image=ColorQuantize[ColorConvert[img,"Grayscale"],2],positions,res},
positions=PixelValuePositions[ImageAdjust[image],0];
res=FindShortestTour[positions];
Graphics[Line[positions[[res[[2]]]]]]]

mona


How it works

ColorConvert[img,"Grayscale"] converts the image to grayscale. (It wasn't necessary in this instance, because the photo was already in grayscale; I included it in case someone wanted to try it with a color image.)

ColorQuantize[%],2] binarizes the image, that is, reduces it to black and white. (% refers to the result from the last operation.)

positions=PixelValuePositions[ImageAdjust[%],0] returns the positions of the black pixels.

FindShortestTour[positions]treats the positions as if they were locations of cities that a traveling salesman wished to visit in the most efficient (shortest) possible route. To me, it's nothing short of amazing that the route can be quickly found.


share|improve this answer
    
Looks great, even tough it looks as if the cuve intersects/touches itself at this resolution of the image. Can you explain somewhat how it works? –  flawr Sep 25 at 11:35
1  
the path intersects itself –  proud haskeller Sep 25 at 12:49
    
It's quick because it stops short of finding a non-intersecting path. If you can find a setting to make the path shorter, it will remove the intersections (if the path crosses then there exists a shorter path). –  githubphagocyte Nov 26 at 12:27
    
I also found that a travelling salesman path with cities offset by small random amounts tends to have fewer intersections than when the cities are aligned to a grid. Your code is amazingly short so there's plenty of room to try things like this... –  githubphagocyte Nov 26 at 12:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.