De Bruijin Grid

debruijgrid.py

# Emanuele Ruffaldi line pattern generator using De Bruij sequences 2016
#
# Supports arithmetic, geometric and custom alphabet
# Supports also basic uniform for comparison
from PIL import Image, ImageDraw

def colorparse(s):
    try:
        x, y, z = map(int, s.split(','))
        return x, y, z
    except:
        raise argparse.ArgumentTypeError("Colors must be x,y,z")

def sizeparse(s):
    try:
        x, y = map(int, s.split(','))
        return x, y
    except:
        raise argparse.ArgumentTypeError("Size\ must be x,y")

#here https://en.wikipedia.org/wiki/De_Bruijn_sequence
def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    try:
        # let's see if k can be cast to an integer;
        # if so, make our alphabet a list
        _ = int(k)
        alphabet = list(map(str, range(k)))

    except (ValueError, TypeError):
        alphabet = k
        k = len(k)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1:p + 1])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence,alphabet

if __name__ == '__main__':
    import argparse

    ProgressionTypes = ["ari", "geo"] #TODO auto , "prime"]


    parser = argparse.ArgumentParser(description='De Bruijn Grid generator - Emanuele Ruffaldi 2016 SSSA')
    parser.add_argument('-k',help="k factor",default=5)
    parser.add_argument('-n',help="n factor",default=3)
    parser.add_argument('--out',help="output file",default="out.png")
    parser.add_argument('--width',help="image width",default=1400)
    parser.add_argument('--height',help="image height",default=1050)
    parser.add_argument('-s','--size',type=sizeparse, help="image size: w,h alternative to --width --height",default=None)
    parser.add_argument('-a','--alphabet',help="specify alphabet. E.g. -a 2 3 5 7 11 for a prime based",type=int,nargs="+")
    parser.add_argument('--overflow', dest='overflow', action='store_true',help="cover all image, but grid will overflow")
    parser.add_argument('--no-overflow', dest='overflow', action='store_false',help="do not cover all image, but grid will overflow")
    parser.add_argument('--colorh', type=colorparse,default=(255,0,0),help="horizontal lines color, use e.g. 255,0,0 for red")
    parser.add_argument('--colorv', type=colorparse,default=(0,0,255),help="vertical lines color, use e.g. 0,0,255 for blue")
    parser.add_argument('--uniform',type=sizeparse,help="spacing for uniform mode: w,h as spacing in pixels")
    parser.add_argument('--progression',default="geo",help="type of sequence: ari 1,2,3... geo 1,2,4,8,...", choices=ProgressionTypes)
    parser.set_defaults(overflow=True)

    args = parser.parse_args()

    k=args.k
    n=args.n
    if args.size:
        s = args.size
    else:
        s = (args.width,args.height)
    img = Image.new("RGB", s, color=0)
    draw = ImageDraw.Draw(img)

    if not args.uniform:
        if args.alphabet:
            kk = args.alphabet
            k = len(kk)
        elif args.progression == "ari":
            kk = range(1,k+1) # I want a 1..k range and not 0..k-1 as default
        elif args.progression == "geo":
            kk = [2**x for x in range(1,k+1)]
        #elif args.progression == "prime":
        #    pass
        else:
            raise "Unknown progression",args.progression
        seq,alpha = de_bruijn(kk,n)

        extent = sum([alpha[i] for i in seq])
        # need to rescale the alphabet to be there
        if args.overflow:
            print "Apply Overflow",args.overflow
            sx = (s[0]+extent-1)/extent
            sy = (s[1]+extent-1)/extent
        else:
            sx = s[0]/extent
            sy = s[1]/extent
        alphax = [i*sx for i in alpha]
        alphay = [i*sy for i in alpha]

        print "original extent was",extent
        print "scaling",(sx,sy)
        print "new extent is",(sum([alphax[i] for i in seq]),sum([alphay[i] for i in seq])),"vs",s
        
        #horizontal
        cy = 0
        for bs in [alphay[i] for i in seq]:
            draw.line((0, cy, s[0], cy),fill=args.colorh)
            cy += bs

        #vertical
        cx = 0
        for bs in [alphax[i] for i in seq]:
            draw.line((cx, 0, cx,s[1]),fill=args.colorv)
            cx += bs    
    else:
        dx,dy = args.uniform
        
        #horizontal
        for cy in range(dy,s[1],dy):
            draw.line((0, cy, s[0], cy),fill=args.colorh)

        #vertical
        for cx in range(dx,s[0],dx):
            draw.line((cx, 0, cx,s[1]),fill=args.colorv)
            
    img.save(open(args.out,"wb"), "PNG")