Penrose Tiler (Python recipe) by James Coliins

ActiveState Code (http://code.activestate.com/recipes/577405/)

# This progam creates a non periodic tiling of the plane using 'Penrose tiles',
# wich were invented by Roger Penrose.
# Each time it runs it will generate a new random pattern.
# There are an infinite number of them.
# Unlike a periodic tesselation the assembly requires forward planning and
# hence the program searches through various combinations of parts, often
# comming to a dead end and having to backtrack.
# The program has three phases, the first generating the initial layout with
# a simple sharks tooth design
# The second fills in the tiles completely
# The third phase reveals an inner fractal pattern by the process of deflation
# then deflating again over and over
# You must close the progam to stop it.
from __future__ import division
from Tkinter import * 
from math import cos, sin, atan2, sqrt, pi
from random import random, shuffle, seed
from numpy import array, dot, transpose
from copy import deepcopy
from sys import getrecursionlimit, setrecursionlimit

nW = 800.0 # change these to make the screen bigger or smaller
nH = 600.0
canvas = Canvas( width = nW, height = nH, bg = 'darkred')
canvas.pack(expand = YES, fill = BOTH)

# setrecursionlimit(10000)
nRecLim = getrecursionlimit()
nScale = 30.0 # sqrt(nW * nH / nRecLim) / nFib #25.0 # change this to make the tile bigger or smaller
nFib   = (1.0 + sqrt(5.0))/2.0 # Fibonacci's golden ratio
nSmall = 5 # the smallest possible gap should be 18`
n36    = 36.0 * pi / 180.0
nSin36 = sin(n36)
nCos36 = cos(n36)
n72    = 72.0 * pi / 180.0
nSin72 = sin(n72)
nCos72 = cos(n72)
nSelfX = nScale * nFib * nSin36
nSelfY = nScale * nFib * nCos36
nW2 = nW / 2
nH2 = nH / 2
nTag = 0
nRatioSmall = nScale * nFib / (nFib + 1)
nRatioBig   = nScale * nFib**2 / (nFib + 1)
lAlternate = False    
def NewTag():
    global nTag
    nTag += 1
    return "TAG%d" %(nTag)

def Scalar(midx, midy, nR, x0, y0):
    midx -= x0
    midy -= y0
    midR = sqrt(midx**2 + midy**2)
    if midR == 0:
        return [x0, y0]
    midx *= nR / midR
    midy *= nR / midR
    midx += x0
    midy += y0
    return [midx,midy]

def MidArc(p1, p2, p0, nR):
    x0 = p0[0]
    y0 = p0[1]
    x1 = p1[0] 
    y1 = p1[1] 
    x2 = p2[0] 
    y2 = p2[1] 
    midx = (x1 + x2) / 2
    midy = (y1 + y2) / 2
    return Scalar(midx, midy, nR, x0, y0)

def Perimeter(aP, lComplete = False):
    points = [] 
    for i in aP:
        points += (i[0], i[1])
    if lComplete:
        points += (aP[0][0], aP[0][1])
    return points    

def linearTranslation(a1, points, r, a2):
    nL = len(points)
    p1 = array([a1] * nL, 'f')
    q = points - p1
    q = transpose(q)
    q = dot(r, q)
    q = transpose( q)
    p2 = array([a2] * nL, 'f')
    q = q + p2
    return q
       
class shape:
    def GetPoints(self):
        pass
    def __init__(self, cTag = None):
        if cTag == None:
            cTag = NewTag()
        self.length = [2,1,1,2]
        self.GetPoints()
        self.points   = array(self.points, 'f')
        self.vertices = self.points
        self.tag = cTag
    def draw(self):
        v = Perimeter(self.vertices)
        v.append(v[0])
        v.append(v[1])
        canvas.create_line(v, fill = 'orange', tag = self.tag, width = 1)
    def drawOutline(self, x, y, n0, nC):
        cosTheta = cos(n0)
        sinTheta = sin(n0)
        r     = array([[cosTheta, -sinTheta],[sinTheta,cosTheta]], 'f')
        q     = linearTranslation(self.points[nC], self.points, r, [x, y])
        self.vertices = q
        self.draw()
    def drawFill(self):
        points = Perimeter(self.vertices) 
        canvas.create_polygon(points, fill = self.colour, tag = self.tag)
    def drawComplete(self):
        self.drawFill()
        self.redArc()
        self.blueArc()
    def alignWith(self, nodeobj, nCnr2):
        p1 = nodeobj.p1 
        p2 = nodeobj.p2 
        dx1 = p2[0] - p1[0]
        dy1 = p2[1] - p1[1]
        nTheta2 = atan2(dy1,dx1)
        q1 = self.vertices[nCnr2]
        q2 = self.vertices[(nCnr2 - 1)%4]
        dx2 = q2[0] - q1[0]
        dy2 = q2[1] - q1[1]
        nTheta1 = atan2(dy2,dx2)
        self.drawOutline(p1[0], p1[1], nTheta2 - nTheta1,nCnr2)

class kite(shape):
    def GetPoints(self, cColour = 'brown'):
       self.points  = [[0,0]
                      ,[nSelfX,nSelfY]
                      ,[0,nScale * nFib]
                      ,[-nSelfX,nSelfY]]
       self.colour = cColour
       self.angles = [72,72,144,72]
       self.type   = 'kite'
        # shape, corner
       self.viable = [[[dart,1],[kite, 0]]
                     ,[[dart,2],[kite, 3]]
                     ,[[dart,3],[kite, 2]]
                     ,[[dart,0],[kite, 1]]]
    def draw(self):
        pass
    def redArc(self):
        nR = nRatioBig
        p0 = self.vertices[0]
        p1 = Scalar(self.vertices[3][0],self.vertices[3][1], nR, p0[0],p0[1])
        p5 = Scalar(self.vertices[1][0],self.vertices[1][1], nR, p0[0],p0[1])
        p3 = MidArc(p1,p5,p0,nR)
        p2 = MidArc(p1,p3,p0,nR)
        p4 = MidArc(p3,p5,p0,nR)
        aR = Perimeter([p1,p2,p3,p4,p5])
        canvas.create_line(aR, fill = 'darkgrey', tag = self.tag, width = 1)        
    def blueArc(self):
        nR = 1 / (1 / nFib + 1) * nScale
        p0 = self.vertices[2]
        p1 = Scalar(self.vertices[3][0],self.vertices[3][1], nR, p0[0],p0[1])
        p9 = Scalar(self.vertices[1][0],self.vertices[1][1], nR, p0[0],p0[1])
        p5 = MidArc(p1,p9,p0,nR)
        p3 = MidArc(p1,p5,p0,nR)
        p7 = MidArc(p5,p9,p0,nR)
        p2 = MidArc(p1,p3,p0,nR)
        p4 = MidArc(p3,p5,p0,nR)
        p6 = MidArc(p5,p7,p0,nR)
        p8 = MidArc(p7,p9,p0,nR)
        aR = Perimeter([p1,p2,p3,p4,p5,p6,p7,p8,p9])
        canvas.create_line(aR, fill = 'cyan', tag = self.tag, width = 1)
    def subShapes(self):
        subs = []
        p0 = list(self.vertices[0])
        p1 = list(self.vertices[1])
        p2 = list(self.vertices[2])
        p3 = list(self.vertices[3])
        p4 = Scalar(p3[0],p3[1], nRatioSmall, p0[0],p0[1])
        p5 = Scalar(p1[0],p1[1], nRatioSmall, p0[0],p0[1])
        p6 = Scalar(p2[0],p2[1], nRatioBig  , p0[0],p0[1])
        subs.append(SubKiteRight(p3,p6,p2))
        subs.append(SubKiteLeft(p3,p6,p4))
        subs.append(SubKiteRight(p1,p6,p5))
        subs.append(SubKiteLeft(p1,p6,p2))
        subs.append(SubDartRight(p6,p0,p5))
        subs.append(SubDartLeft(p6,p0,p4))
        return subs
    
class dart(shape):
    def GetPoints(self, cColour = 'darkgreen'):
        self.points = [[0,0]
               ,[nSelfX,nSelfY]
               ,[0,nScale] 
               ,[-nSelfX,nSelfY]]
        self.angles = [72,36,216,36]
        self.type   = 'dart'
        self.viable = [[[dart, 0],[kite, 1]]
                     ,[[kite, 2]]
                     ,[[kite, 3]]
                     ,[[dart, 1],[kite, 0]]] 
        self.colour = cColour
    def redArc(self):
        nR = nRatioSmall
        p0 = self.vertices[0]
        p1 = Scalar(self.vertices[3][0],self.vertices[3][1], nR, p0[0],p0[1])
        p5 = Scalar(self.vertices[1][0],self.vertices[1][1], nR, p0[0],p0[1])
        p3 = MidArc(p1,p5,p0,nR)
        p2 = MidArc(p1,p3,p0,nR)
        p4 = MidArc(p3,p5,p0,nR)
        aR = Perimeter([p1,p2,p3,p4,p5])
        canvas.create_line(aR, fill = 'darkgrey', tag = self.tag, width = 1)        
    def blueArc(self):
        nR = 1 / nFib / (1 / nFib + 1) * nScale
        p0 = self.vertices[2]
        p1 = Scalar(self.vertices[3][0],self.vertices[3][1], nR, p0[0],p0[1])
        p9 = Scalar(self.vertices[1][0],self.vertices[1][1], nR, p0[0],p0[1])
        p5 = MidArc(p1,p9,p0,nR)
        p5[0] = 2 * p0[0] - p5[0] # great arc
        p5[1] = 2 * p0[1] - p5[1] # great arc
        p3 = MidArc(p1,p5,p0,nR)
        p7 = MidArc(p5,p9,p0,nR)
        p2 = MidArc(p1,p3,p0,nR)
        p4 = MidArc(p3,p5,p0,nR)
        p6 = MidArc(p5,p7,p0,nR)
        p8 = MidArc(p7,p9,p0,nR)
        aR = Perimeter([p1,p2,p3,p4,p5,p6,p7,p8,p9])
        canvas.create_line(aR, fill = 'cyan', tag = self.tag, width = 1)        
    def subShapes(self):
        subs = []
        p0 = list(self.vertices[0])
        p1 = list(self.vertices[1])
        p2 = list(self.vertices[2])
        p3 = list(self.vertices[3])
        p4 = Scalar(p3[0],p3[1], nRatioBig, p0[0],p0[1])
        p5 = Scalar(p1[0],p1[1], nRatioBig, p0[0],p0[1])
        subs.append(SubKiteRight(p0,p2,p4))
        subs.append(SubKiteLeft(p0,p2,p5))
        subs.append(SubDartRight(p2,p3,p4))
        subs.append(SubDartLeft(p2,p1,p5))
        return subs

def AlterBorder(aBorder, temp, nNook, nAligned, nDel, nIns):
    cnr1 = nNook
    cnr2 = nAligned
    if nDel < 3:
        # replacement
        ang1 = aBorder[cnr1].angle    
        aBorder[cnr1]= NodeObject(temp, cnr2)
        aBorder[cnr1].angle = ang1
        aBorder[cnr1].prioritise()
    if cnr1 == len(aBorder) - 1:
        lClocked = True
    else:
        lClocked = False
    # deletion
    cnr3 =(cnr1 + 1) % len(aBorder)
    nAdjust = 1
    for z in range(nDel):
        if cnr3 < len(aBorder) - 1:
           aBorder = aBorder[:cnr3] + aBorder[cnr3 + 1:]
        elif cnr3 == len(aBorder): # delete first element
           aBorder = aBorder[1:]  
        else: # around the clock
           aBorder = aBorder[:cnr3]
    # insertion
    for nD in range(nIns):
        cnr4 = (cnr1 + nD + nAdjust) % len(aBorder)
        if lClocked:
            cnr4 = nD
        node = NodeObject(temp, (cnr2 + nD + 1) % 4)
        aBorder.insert(cnr4, node)
    return aBorder    

def FitsBorder(aBorder, nNook, aV, temp):
    nAligned = aV[1]
    nL = len(aBorder)
    for nBack in range(4):
        btest = aBorder[(nNook - nBack) % nL]
        angle1 = temp.angles[(nAligned + nBack) % 4]
        t = btest.angle - angle1
        if t < -nSmall: # conflict
            return False
        elif t > nSmall: # still room
            break
        # tight angle fit, test lengths
        nTestBorder = (nNook - nBack - 1) % nL
        nTestShape  = (nAligned + nBack) % 4
        btest       = aBorder[nTestBorder]
        if btest.length <> temp.length[nTestShape]: # length mismatch
            return False
    for nForward in range(4):
        btest = aBorder[(nNook + nForward + 1) % nL]
        angle1 = temp.angles[(nAligned - nForward - 1) % 4]
        t = btest.angle - angle1
        if t < -nSmall: # conflict
            return False
        elif t > nSmall: # still room
            break
        # tight angle fit, test lengths
        nTestBorder = (nNook + nForward + 1) % nL
        nTestShape  = (nAligned - nForward - 2) % 4
        btest       = aBorder[nTestBorder]
        if btest.length <> temp.length[nTestShape]: # length mismatch
            return False
    aBorder[nNook].nBack    = nBack
    aBorder[nNook].nForward = nForward
    return True



def addToBorder(aBorder, nNook, node, aV, AddTile):
    nAligned = aV[1]
    nL = len(aBorder)
    AddTile.alignWith(node, nAligned)
    nBack    = aBorder[ nNook].nBack
    nForward = aBorder[ nNook].nForward
    del aBorder[ nNook].nBack
    del aBorder[ nNook].nForward
    nTest    = (nNook - nBack) % nL
    btest    = aBorder[ nTest]
    nAlign   = (nAligned + nBack) % 4
    angle1   = AddTile.angles[nAlign]
    btest.angle -= angle1
    btest.prioritise() 
    btest       = aBorder[(nNook + nForward + 1) % nL]
    angle1      = AddTile.angles[(nAligned - nForward - 1) % 4]
    btest.angle -= angle1
    btest.prioritise()
    nDel = min(nForward + nBack, 3)
    nIns = max(2 - nDel, 0)
    aBorder = AlterBorder(aBorder, AddTile, nTest, nAlign, nDel, nIns)
    return aBorder


class NodeObject:
    def __init__(self, shape, edge):
        self.angle  = 360 - shape.angles[edge]
        self.length = shape.length[edge]
        self.p1     = shape.vertices[edge]
        self.p2     = shape.vertices[(edge + 1) % 4]
        self.edge   = edge
        self.x      = shape.vertices[edge][0]
        self.y      = shape.vertices[edge][1]
        self.dist   = sqrt((nW2 - self.x)**2 + (nH2 -self.y)**2)
        self.viable = shape.viable[edge]
        self.prioritise()
        self.shape = shape
    def prioritise(self):
        self.priority = self.angle + self.dist / nW 

def PauseMessage(cText):
    global lFinished
    lFinished = True
    canvas.create_text(nW/2,20,text = cText,fill = 'white', tag = 'pause')
    raw_input()
    canvas.delete('pause')    
               
def FillPlane(aBorder, level):
    # a small delay allows the screen to show
    print level, ' of ', nRecLim # when level gets too high the stack will overload
    if level >= nRecLim - 50:
        print 'The stack has maxed out!'
        PauseMessage('The initial pattern is complete, press ENTER to advance.')
        return {}
    aBorderCopy = deepcopy(aBorder)
    nMin = 10000
    k    = 'all filled'
    j    = k
    for i in aBorderCopy:
        if i.x <  nW * 0.05 or i.x > nW * 0.95: # dont go off the screen
            continue
        elif  i.y <  nH * 0.1 or i.y > nH * 0.9:
            continue
        elif i.priority < nMin:
            j = i
            nMin = i.priority
    aAdded = []
    # by choosing the most sensible place to add to
    # there is not such a need for conflict testing.
    if  j == k: # no more space to fill
        print 'complete'
        PauseMessage('The initial pattern is complete, press ENTER to advance.')
        return {}
    b = j
    i = aBorderCopy.index(b)
    viable = b.viable
    shuffle(viable)
    while len(viable) > 0:
        v = viable[0]
        viable = viable[1:]
        attempt = v[0]()
        if FitsBorder(aBorderCopy, i, v, attempt):
            aAdded.append(attempt.tag)
            aBorderCopy = addToBorder(aBorderCopy, i, b, v, attempt)
            oShapesDict = FillPlane(aBorderCopy, level + 1)
            for idtag in aAdded:
                canvas.delete(idtag)
            if lFinished:
                for n in aBorder:
                    oShapesDict[n.shape.tag] = n.shape
                return oShapesDict
            # it might be more efficient to do some sort of clean up
            # but this is eaisier
            aBorderCopy = deepcopy(aBorder)

class SubShape:
    def draw(self):    
        points = Perimeter(self.vertices) 
        canvas.create_polygon(points, fill = self.colour, tag = cDefTag)

class SubKiteRight(SubShape):
    def __init__(self,p0,p1,p2):
        self.vertices = deepcopy([p0,p1,p2])
        self.colour = 'beige'
    def subShapes(self):
        subs = []
        p0 = self.vertices[0]
        p1 = self.vertices[1]
        p2 = self.vertices[2]
        p3 = Scalar(p2[0],p2[1], nRatioSmall, p0[0],p0[1])
        p4 = Scalar(p1[0],p1[1], nRatioBig  , p0[0],p0[1])
        subs.append(SubKiteRight(p2,p4,p1))
        subs.append(SubKiteLeft(p2,p4,p3))
        subs.append(SubDartLeft(p4,p0,p3))
        return subs
        
class SubKiteLeft(SubShape):
    global lAlternate
    def __init__(self,p0,p1,p2):
        self.vertices = deepcopy([p0,p1,p2])
        self.colour = 'tan'            

    def subShapes(self):        
        subs = []
        p0 = self.vertices[0]
        p1 = self.vertices[1]
        p2 = self.vertices[2]
        p3 = Scalar(p2[0],p2[1], nRatioSmall, p0[0],p0[1])
        p4 = Scalar(p1[0],p1[1], nRatioBig  , p0[0],p0[1])
        subs.append(SubKiteRight(p2,p4,p3))
        subs.append(SubKiteLeft(p2,p4,p1))
        subs.append(SubDartRight(p4,p0,p3))
        return subs

class SubDartRight(SubShape):
    def __init__(self,p0,p1,p2):
        self.vertices = deepcopy([p0,p1,p2])
        self.colour = 'darkgrey'            
        
    def subShapes(self):
        subs = []
        p0 = self.vertices[0]
        p1 = self.vertices[1]
        p2 = self.vertices[2]
        p3 = Scalar(p1[0],p1[1], nRatioSmall, p0[0],p0[1])
        subs.append(SubKiteRight(p1,p2,p3))
        subs.append(SubDartRight(p2,p0,p3))
        return subs
class SubDartLeft(SubShape):        
    def __init__(self,p0,p1,p2):
        self.vertices = deepcopy([p0,p1,p2])
        self.colour = 'grey'
        
    def subShapes(self):
        subs = []
        p0 = self.vertices[0]
        p1 = self.vertices[1]
        p2 = self.vertices[2]
        p3 = Scalar(p1[0],p1[1], nRatioSmall, p0[0],p0[1])
        subs.append(SubKiteLeft(p1,p2,p3))
        subs.append(SubDartLeft(p2,p0,p3))
        return subs

seed()
aBorder = []
lFinished = False
if random() > 0.5:
   temp = kite('first')
else:
   temp = dart('first')
temp.drawOutline(nW2, nH2, 0, 0)
for i in range(4):
    aBorder.append(NodeObject(temp, i))
oShapesDict = FillPlane(aBorder, 1)
canvas.delete('first')
cDefTag = NewTag()
aSubShapes  = []
for s in oShapesDict:
    print '#'
    oShape = oShapesDict[s]
    oShape.drawComplete()
    aSubShapes += oShape.subShapes()

while True:
    nRatioSmall *= nFib / (nFib + 1)
    nRatioBig   *= nFib / (nFib + 1)
    PauseMessage('press ENTER again to "DEFLATE" the pattern.')
    cLastTag = cDefTag
    cDefTag  = NewTag()
    aNewSubs = []
    for s in aSubShapes:
        s.draw()
        print '#'
        t = s.subShapes()
        aNewSubs += t
    canvas.delete(cLastTag)        
    lAlternate = True    
    aSubShapes = deepcopy(aNewSubs)