User:Watchduck/bin2svg

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