User:Watchduck/bin2svg

Hadamard code

Sierpinski triangle drawn with bin2svg — The red squares form one contiguous area with only one edge, so the path contains only one M.

bin2svg is a small program that takes a binary matrix and returns the corresponding SVG path of the area covered by ones.

It was initially written in Matlab and later translated to Python. The code is shown below.

Files created with this program are marked with {{Created with bin2svg}} and sorted into the hidden category Created with bin2svg.

Example

>>> from numpy import array
>>> from bin2svg import bin2svg
>>> mat = array([[0, 0, 0, 1], [1, 1, 1, 0], [1, 0, 1, 0], [1, 1, 1, 0]])
>>> mat
array([[0, 0, 0, 1],
       [1, 1, 1, 0],
       [1, 0, 1, 0],
       [1, 1, 1, 0]])
>>> bin2svg(mat)
'M3,0h1v1h-1M0,1h3v3h-3M1,2v1h1v-1'

If the function gets the binary matrix ${\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&0&1&0\\1&1&1&0\end{bmatrix}}$ it will create the intermediate matrix ${\begin{bmatrix}0&0&0&1&2\\1&0&0&24&3\\0&5&8&0&0\\0&6&7&0&0\\4&0&0&3&0\end{bmatrix}}$ which shows that there are three cycles of corners:
Two on the outside of an area of ones (with clockwise numbers 1...4) and one hole (with anticlockwise numbers 5...8). (The 24 is a 2 and a 4 in the same place.)
The outside cycles give the paths M3,0 h1 v1 h-1 and M0,1 h3 v3 h-3, and the hole gives M1,2 v1 h1 v-1.
So the output of the function is M3,0h1v1h-1M0,1h3v3h-3M1,2v1h1v-1.

In the following SVG code the result produces the image shown on the right:

<?xml version = "1.0" encoding = "UTF-8" ?>
<svg xmlns="http://www.w3.org/2000/svg" width="100" height="100" viewBox="-.5 -.5 5 5">
    <path fill="#fff" d="m0,0h4v4H0"/> <!-- white background -->
    <path fill="#f00" d="M3,0h1v1h-1M0,1h3v3h-3M1,2v1h1v-1"/> <!-- red entries -->
    <g stroke="#000">
        <path stroke-width="4" stroke-dasharray=".05,.95" d="M0,2h5M2,0v5"/> <!-- 0.5px black lines -->
        <rect stroke-width=".1" fill="none" x="0" y="0" width="4" height="4"/> <!-- 1px black square -->
    </g>
</svg>

another example

There are points that are part of two outside cycles — 13 and the 24 in the intermediate matrix — but no similar points that are part of two holes. If the function gets the binary matrix ${\begin{bmatrix}1&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&1\end{bmatrix}}$ it will create the intermediate matrix ${\begin{bmatrix}1&0&0&0&2\\0&5&8&0&0\\0&6&24&8&0\\0&0&6&7&0\\4&0&0&0&3\end{bmatrix}}$. The outside cycle gives the path M0,0 h4 v4 h-4. In the following path it can be seen, that what looks like two holes is actually handled as one: M1,1 v1 h1 v1 h1 v-1 h-1 v-1 (M1,1 v1 h1 v-1 M2,2 v1 h1 v-1 would look the same, but will not be generated by this function.)

Python code

See also: http://pastebin.com/y8rY5Vj4

bin2svg

import numpy as np def bin2svg(tosvg): """ :param tosvg: numpy array with binary entries, e.g. `np.array([[1, 0], [0, 1]])` :return: string describing an SVG path, e.g. 'M0,0h1v1h-1M1,1h1v1h-1' see also: https://en.wikiversity.org/wiki/User:Watchduck/bin2svg """ def bin2corners(tocorners): """ :param tocorners: binary m×n matrix; areas of 1s to be interpreted as areas of squares with no internal corners :return: m+1 × n+1 matrix; 0 for no corner; 1, 2, 3, 4 for corner; 13, 24 for double corner """ if type(tocorners) is not np.ndarray: # if input is plain array tocorners = np.array(tocorners) # convert to numpy array (high, wide) = tocorners.shape hpad = np.zeros((1, wide+2), np.int8) vpad = np.zeros((high, 1), np.int8) tocorners = np.vstack(( hpad, np.hstack((vpad, tocorners, vpad)), hpad )) corners = np.zeros((high+1, wide+1), np.int8) for m in range(high+1): for n in range(wide+1): sub = tocorners[m:m+2, n:n+2] if np.array_equal(sub, np.array([[0, 0], [0, 1]])): corners[m, n] = 1 elif np.array_equal(sub, np.array([[0, 0], [1, 0]])): corners[m, n] = 2 elif np.array_equal(sub, np.array([[1, 0], [0, 0]])): corners[m, n] = 3 elif np.array_equal(sub, np.array([[0, 1], [0, 0]])): corners[m, n] = 4 elif np.array_equal(sub, np.array([[1, 1], [1, 0]])): corners[m, n] = 5 elif np.array_equal(sub, np.array([[1, 0], [1, 1]])): corners[m, n] = 6 elif np.array_equal(sub, np.array([[0, 1], [1, 1]])): corners[m, n] = 7 elif np.array_equal(sub, np.array([[1, 1], [0, 1]])): corners[m, n] = 8 elif np.array_equal(sub, np.array([[1, 0], [0, 1]])): corners[m, n] = 13 elif np.array_equal(sub, np.array([[0, 1], [1, 0]])): corners[m, n] = 24 return corners def cornerfinder(corners, look): """ Searches corner matrix from last position for non zero entries. :param corners: current corner matrix :param look: position where to begin searching :return: {'pos': [m, n], 'val': k} where [m, n] is the first position found and k the entry at this position """ (high, wide) = corners.shape found = 0 while found == 0: found = corners[tuple(look)] if found == 0: if look[1] < wide-1: look[1] += 1 elif look[1] == wide-1 and look[0] < high-1: look = [look[0]+1, 0] else: return 'reached end' else: return {'pos': look, 'val': found} def step(corners, cornerfound): """ :param corners: current corner matrix :param cornerfound: last position and value found by `cornerfinder` :return: {'corners': corners, 'svgpath': svgpath} with `corners` sparser and `svgpath` extended """ startpos = cornerfound['pos'] pos = startpos[:] val = cornerfound['val'] svgpath = 'M' + str(pos[1]) + ',' + str(pos[0]) while True: if val in range(1, 9): # 1 <= val <= 8 corners[tuple(pos)] = 0 elif val == 13 and (oldval in [4, 7]): # 13 as 1 , leave 3 val = 1 corners[tuple(pos)] = 3 elif val == 13 and (oldval in [2, 5]): # 13 as 3 , leave 1 val = 3 corners[tuple(pos)] = 1 elif val == 24 and (oldval in [1, 6]): # 24 as 2 , leave 4 val = 2 corners[tuple(pos)] = 4 elif val == 24 and (oldval in [3, 8]): # 24 as 4 , leave 2 val = 4 corners[tuple(pos)] = 2 oldpos = pos[:] creeper = 0 if val in [1, 6]: while creeper == 0: pos[1] += 1 if pos == startpos: break creeper = corners[tuple(pos)] elif val in [2, 5]: while creeper == 0: pos[0] += 1 if pos == startpos: break creeper = corners[tuple(pos)] elif val in [3, 8]: while creeper == 0: pos[1] -= 1 if pos == startpos: break creeper = corners[tuple(pos)] elif val in [4, 7]: while creeper == 0: pos[0] -= 1 if pos == startpos: break creeper = corners[tuple(pos)] oldval = val val = creeper if pos[0] == oldpos[0]: append_to_svgpath = 'h' + str(pos[1]-oldpos[1]) else: append_to_svgpath = 'v' + str(pos[0]-oldpos[0]) if pos == startpos: break svgpath += append_to_svgpath return {'corners': corners, 'svgpath': svgpath} corners = bin2corners(tosvg) startpos = [0, 0] svgpath = '' while True: cornerfound = cornerfinder(corners, startpos) if cornerfound == 'reached end': break startpos = cornerfound['pos'] thisstep = step(corners, cornerfound) corners = thisstep['corners'] svgpath += thisstep['svgpath'] return svgpath

Matlab code

subfunction bin2corners

function [y] = bin2corners(x) % Turns the binary matrix in a bigger matrix with key numbers. high = size(x,1) ; long = size(x,2) ; X = [ zeros(1,long+2) ; zeros(high,1) x zeros(high,1) ; zeros(1,long+2) ] ; Y = zeros(high+1,long+1) ; for m=1:high+1 for n=1:long+1 A = X(m:m+1,n:n+1) ; if A == [ 0 0 ; 0 1 ] Y(m,n) = 1 ; elseif A == [ 0 0 ; 1 0 ] Y(m,n) = 2 ; elseif A == [ 1 0 ; 0 0 ] Y(m,n) = 3 ; elseif A == [ 0 1 ; 0 0 ] Y(m,n) = 4 ; elseif A == [ 1 1 ; 1 0 ] Y(m,n) = 5 ; elseif A == [ 1 0 ; 1 1 ] Y(m,n) = 6 ; elseif A == [ 0 1 ; 1 1 ] Y(m,n) = 7 ; elseif A == [ 1 1 ; 0 1 ] Y(m,n) = 8 ; elseif A == [ 1 0 ; 0 1 ] Y(m,n) = 13 ; elseif A == [ 0 1 ; 1 0 ] Y(m,n) = 24 ; end end end y = Y ; end Example: >> binmat = [ 0 0 0 1 1 1 1 0 1 0 1 0 1 1 1 0 ] ; >> cornermat = bin2corners(binmat) cornermat = 0 0 0 1 2 1 0 0 24 3 0 5 8 0 0 0 6 7 0 0 4 0 0 3 0

subfunction cornerfinder

function [y] = cornerfinder(x1,x2) % Searches matrix x1 from position x2 for non zero entries. % Output is vector [m n k] where [m n] is the first position found and k the entry at this position. high = size(x1,1) ; wide = size(x1,2) ; look = x2 ; found = 0 ; while found == 0 found = x1( look(1) , look(2) ) ; if found == 0 if look(2) < wide look(2) = look(2) + 1 ; elseif look(2)==wide && look(1)<high look = [ look(1)+1 1 ] ; else look = [-1 -1] ; % reached end, signal to stop for other function break end else break end end y = [ look found ] ; end Example: >> mnk = cornerfinder( cornermat , [1 1] ) mnk = 1 4 1

subfunction bin2svg_step

function [y] = bin2svg_step(mat,x2) % x1 is the key number matrix, x2 is the output of cornerfinder. pos = x2(1:2) ; coordinates = [ 'M' num2str(pos(2)-1) ',' num2str(pos(1)-1) ] ; entry = x2(3) ; while 1 if entry>=1 && entry<=8 mat(pos(1),pos(2)) = 0 ; elseif entry==13 && ( entrybefore==4 || entrybefore==7 ) % 13 as 1 , leave 3 mat(pos(1),pos(2)) = 3 ; entry = 1 ; elseif entry==13 && ( entrybefore==2 || entrybefore==5 ) % 13 as 3 , leave 1 mat(pos(1),pos(2)) = 1 ; entry = 3 ; elseif entry==24 && ( entrybefore==1 || entrybefore==6 ) % 24 as 2 , leave 4 mat(pos(1),pos(2)) = 4 ; entry = 2 ; elseif entry==24 && ( entrybefore==3 || entrybefore==8 ) % 24 as 4 , leave 2 mat(pos(1),pos(2)) = 2 ; entry = 4 ; end posbefore = pos ; creeper = 0 ; if entry==1 || entry==6 while creeper == 0 pos(2) = pos(2)+1 ; if pos == x2(1:2) break end creeper = mat( pos(1) , pos(2) ) ; end elseif entry==2 || entry==5 while creeper == 0 pos(1) = pos(1)+1 ; if pos == x2(1:2) break end creeper = mat( pos(1) , pos(2) ) ; end elseif entry==3 || entry==8 while creeper == 0 pos(2) = pos(2)-1 ; if pos == x2(1:2) break end creeper = mat( pos(1) , pos(2) ) ; end elseif entry==4 || entry==7 while creeper == 0 pos(1) = pos(1)-1 ; if pos == x2(1:2) break end creeper = mat( pos(1) , pos(2) ) ; end end entrybefore = entry ; entry = creeper ; if pos(1)==posbefore(1) d = [ 'h' num2str( pos(2)-posbefore(2) ) ] ; else d = [ 'v' num2str( pos(1)-posbefore(1) ) ] ; end if pos == x2(1:2) break end coordinates = [ coordinates d ] ; end Y = cell(1,2); Y{1} = mat ; Y{2} = coordinates ; y = Y ; end Example: >> coordinatecell = bin2svg_step( cornermat , mnk ) coordinatecell = [5x5 double] 'M3,0h1v1h-1' >> >> coordinatecell{1} ans = 0 0 0 0 0 1 0 0 2 0 0 5 8 0 0 0 6 7 0 0 4 0 0 3 0

bin2svg

function [y] = bin2svg(x) % Binary matrix to SVG path. A = bin2corners(x) ; startpos = [1 1] ; coordinates = repmat(' ',1,0) ; while 1 B = cornerfinder(A,startpos) ; if B == [-1 -1 0] break end startpos = B(1:2) ; C = bin2svg_step(A,B) ; A = C{1} ; coordinates = [ coordinates C{2} ] ; end y = coordinates ; end Example: >> binmat binmat = 0 0 0 1 1 1 1 0 1 0 1 0 1 1 1 0 >> bin2svg(binmat) ans = M3,0h1v1h-1M0,1h3v3h-3M1,2v1h1v-1

Examples

This Inkscape file was filled with a dark gray and two red bin2svg paths. (The latter by merging matrices, e.g the four 16×16 into one 16×73 with gaps of width 3 between them.)	This file shows bin2svg paths of four matrices, which are red, green, blue and gray — the latter in the same position as the blue one. (There are also two columns and two rows scaled to be thin hints next to the matrices.)	three paths to highlight sets of entries in a matrix
simple file with four areas and corresponding grids