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