A swift implementation of Penrose tiling

penrose.swift

//MARK: - Playground code

//: A UIKit based Playground for presenting user interface
  
import UIKit
import PlaygroundSupport

class MyViewController : UIViewController {
    override func loadView() {
        let view = PenroseView(frame: CGRect(x: 0, y: 0, width: 1000, height: 800))
        view.backgroundColor = .white
        self.view = view
    }
}

class PenroseView: UIView {
    
    let penrose: PenroseTiling
    
    override init(frame: CGRect) {
        self.penrose = PenroseTiling(width: frame.width, height: frame.height)
        super.init(frame: frame)
    }
    
    required init?(coder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
    
    override func draw(_ rect: CGRect) {
        guard let graphics = UIGraphicsGetCurrentContext() else {
            return
        }
        graphics.setStrokeColor(UIColor.darkGray.cgColor)
        let dist: [[CGFloat]] = [
            [PenroseTiling.goldenRatio, PenroseTiling.goldenRatio, PenroseTiling.goldenRatio],
            [-1.0 * PenroseTiling.goldenRatio, -1, -1.0 * PenroseTiling.goldenRatio]
        ]
        
        for tile in penrose.tiles {
            var angle = tile.angle - PenroseTiling.theta
            let path = CGMutablePath()
            
            path.move(to: CGPoint(x: tile.x, y: tile.y))
            
            let ord = tile.type.rawValue
            for i in stride(from: 0, to: 3, by: 1) {
                let x = tile.x + dist[ord][i] * tile.size * cos(angle)
                let y = tile.y - dist[ord][i] * tile.size * sin(angle)
                path.addLine(to: CGPoint(x: x, y: y))
                angle += PenroseTiling.theta
            }
            
            path.closeSubpath()
            
            graphics.addPath(path)
            
            graphics.setFillColor(ord == 0 ? UIColor.orange.cgColor : UIColor.yellow.cgColor)
            graphics.drawPath(using: .fillStroke)
        }
    }
    
}

// Present the view controller in the Live View window
PlaygroundPage.current.liveView = MyViewController()


//MARK: - Penrose code

import Foundation
import CoreGraphics

public struct PenroseTiling {
    
    public static let goldenRatio: CGFloat = (1.0 + sqrt(5.0)) / 2.0
    public static let theta: CGFloat = 36.degreesToRadians
    
    public let tiles: [Tile]
    
    public init(width: CGFloat, height: CGFloat) {
        tiles = PenroseTiling.deflateTiles(tiles: PenroseTiling.setupPrototiles(width: width, height: height), generation: 5)
    }
    
    private static func setupPrototiles(width: CGFloat, height: CGFloat) -> [Tile] {
        var proto = [Tile]()
        
        for i in stride(from: CGFloat.pi / 2.0 + theta, to: CGFloat.pi * 3.0, by: 2.0 * theta) {
            proto.append(Tile(t: .kite, x: width / 2.0, y: height / 2.0, a: i, s: width / 2.5))
        }
        
        return proto
    }
    
    private static func deflateTiles(tiles: [Tile], generation: Int) -> [Tile] {
        guard generation > 0 else {
            return tiles
        }
        
        var next = [Tile]()
        
        for tile in tiles {
            let x = tile.x
            let y = tile.y
            let a = tile.angle
            let size = tile.size / goldenRatio
            
            switch tile.type {
            case .dart:
                next.append(Tile(t: .kite, x: x, y: y, a: a + 5.0 * theta, s: size))
                var sign: CGFloat = 1.0
                for _ in stride(from: 0, to: 2, by: 1) {
                    let nx = x + cos(a - 4.0 * theta * sign) * goldenRatio * tile.size
                    let ny = y - sin(a - 4.0 * theta * sign) * goldenRatio * tile.size
                    next.append(Tile(t: .dart, x: nx, y: ny, a: a - 4 * theta * sign, s: size))
                    sign *= -1
                }
            case .kite:
                var sign: CGFloat = 1.0
                for _ in stride(from: 0, to: 2, by: 1) {
                    next.append(Tile(t: .dart, x: x, y: y, a: a - 4.0 * theta * sign, s: size))
                    
                    let nx = x + cos(a - theta * sign) * goldenRatio * tile.size
                    let ny = y - sin(a - theta * sign) * goldenRatio * tile.size
                    
                    next.append(Tile(t: .kite, x: nx, y: ny, a: a + 3 * theta * sign, s: size))
                    
                    sign *= -1
                }
            }
        }
        
        //remove duplicates
        let dedup = next.distinct()
        
        return deflateTiles(tiles: dedup, generation: generation - 1)
    }
    
}

public struct Tile: Equatable {
    
    public enum TileType: Int {
        case kite
        case dart
    }
    
    public let x, y, angle, size: CGFloat
    public let type: TileType
    
    init(t: TileType, x: CGFloat, y: CGFloat, a: CGFloat, s: CGFloat) {
        self.type = t
        self.x = x
        self.y = y
        self.angle = a
        self.size = s
    }
    
    public static func ==(lhs: Tile, rhs: Tile) -> Bool {
        return lhs.type == rhs.type
            && lhs.x == rhs.x
            && lhs.y == rhs.y
            && lhs.angle == rhs.angle
    }
    
}

extension BinaryInteger {
    var degreesToRadians: CGFloat { CGFloat(self) * .pi / 180 }
}

extension FloatingPoint {
    var degreesToRadians: Self { self * .pi / 180 }
    var radiansToDegrees: Self { self * 180 / .pi }
}

extension Array where Element: Equatable {
    func distinct() -> Self {
        var unique = [Element]()

        for item in self
        {
            if !unique.contains(item)
            {
                unique.append(item)
            }
        }
        return unique
    }
}

Nice work man, have tried it and it works ! 👍

Thanks! Performance leaves a bit to be desired when generation > 5, which is likely due to the distinct() function. Will work on that.

Very cool, will monitor your gist. Any suggestion which parameters as min-max can be used as random input - so the performance does not suffer ?

It seemed to run fine when I used width of 700, height of 450, and a generation of 5 (which is what the original Java source used).

Yes, for generation == 6 it becomes too slow. I will have random between 1-5. I've tried to randomize goldenRatio & theta, but then the pattern gets broken. Do you think you can tweak algorithm to allow random goldenRation and theta? But I think this would be hard to do without more math knowledge about Penrose tiling?

The golden ratio is a standard value and theta is a critical angle for the penrose tiling to work.

Nice work!

It is not clear why you are using stride(from: 0, to: 2, by: 1) instead of just computing the fixed number of tiles (the Python implementation here is much more simple).

Is is also weird that you need to deduplicate, this should not be necessary. If it is required you can use a far more efficient implementation (make Tile conform to Hashable):

extension Array where Element: Hashable {
    func distinct() -> Self {
        Array(Set(self))
    }
}

If the order of Tiles does not matter you can even replace the array of Tiles with a Set of Tiles in you code for faster speed.

Also, using complex number would clarify a lot the code, you can use the library swift-numerics for this (official implementation approved by Swift Core Dev Team).

Cool comments @laclouis5. Waterskier, will you try to improve performance?