Create a Sierpinski Carpet with Python
The Sierpinski carpet is a mathematical set in 2-dimensional space. It is has a few interesting properties. Among them are:
- it is a compact set contained in a square (usually, the unit square [0,1]x[0,1] is taken for it)
- it has a Lebesgue measure of zero and its border has an infinite length
- its number of points is uncountably infinite
- it is a fractal with a dimension ln(8)/ln(3) (= 1.8928…)
- it is a relative of the Cantor set and the Menger sponge
This article shows how to create a nice PNG image of the Sierpinski carpet with a 25 non-comments line Python program in 1 second (6 iteration levels). Because it’s Python and the awesome PDF- and graphics library fitz (= PyMuPDF) runs on many platforms like Windows and Linux, you will probably be able to use it.
And this is the output of the program after less than 1 second of run time (4 GHz machine) when a picture width of 729 (= 3**6) is chosen:
Here is another program version. This one is recursive, which has the following advantages:
- It is a lot faster, because no pixel is turned to black more than once. A square side length of 729 pixels only needs about 0.5 seconds on my machine.
- Processing time only grows by a factor of 8 (and not 3*3 = 9) when the square side is increased by a factor of 3.This is because „almost nothing“ happens for the middle square – it only gets painted black. The other 8 receive a recursive treatment.
- It is a lot more readable … 🙂
import fitz, time
def punch(pm, x0, y0, x1, y1): # pixmap and top-left, bottom-right coords
if (x1-x0) < 3: # granularity below 1 pixel?
return # yes, done
step = (x1 - x0) / 3
# define short names for square corner coordinates
x00 = x0
x01 = x00 + step
x02 = x01 + step
x03 = x02 + step
y00 = y0
y01 = y00 + step
y02 = y01 + step
y03 = y02 + step
# we clear the middle square and invoke us again for the other 8
punch(pm, x00, y00, x01, y01) # top left
punch(pm, x01, y00, x02, y01) # top middle
punch(pm, x02, y00, x03, y01) # top right
punch(pm, x00, y01, x01, y02) # middle left
pm.clearWith(0, fitz.IRect(x01, y01, x02, y02)) # clear center
punch(pm, x02, y01, x03, y02) # middle right
punch(pm, x00, y02, x01, y02) # bottom left
punch(pm, x01, y02, x02, y03) # bottom middle
punch(pm, x02, y02, x03, y03) # bottom right
return
#==============================================================================
# main program
#==============================================================================
d = 729 # 729 = 3**6, stick to powers of 3 here
# create a quadratic pixmap with origin (0,0), where width = height = d should
# be a power of 3
t0 = time.clock()
pm = fitz.Pixmap(fitz.Colorspace(fitz.CS_RGB), fitz.IRect(0, 0, d, d))
# fill image area with "white" and then tint and gamma it
pm.clearWith(255)
pm.tintWith(0, 50, 255) # tint it with some sort of blue
pm.gammaWith(0.2) # turn to a lighter blue
# now punch holes into it, down to 1 pixel granularity
punch(pm, 0, 0, d, d)
t1 = time.clock()
pm.writePNG("sierpinski.png")
t2 = time.clock()
print t1-t0, "sec to create fitz img"
print t2-t1, "sec to save fitz img"
TechDosadi 
Antworten