Skip to content

Instantly share code, notes, and snippets.

@waterskier2007
Created January 14, 2021 04:25
Show Gist options
  • Save waterskier2007/4584bdd4c0b2f3f90e765b9a50747e48 to your computer and use it in GitHub Desktop.
Save waterskier2007/4584bdd4c0b2f3f90e765b9a50747e48 to your computer and use it in GitHub Desktop.
A swift implementation of Penrose tiling
//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
}
}
@sabiland
Copy link

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

@waterskier2007
Copy link
Author

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

@sabiland
Copy link

sabiland commented Jan 14, 2021

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 ?

@waterskier2007
Copy link
Author

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

@sabiland
Copy link

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?

@waterskier2007
Copy link
Author

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

@laclouis5
Copy link

laclouis5 commented Jan 24, 2021

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

@sabiland
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment