Tag Archives: Sierpinski

Bonus Friday Post “Fractal Valentines Day!”

Many of you have probably seen this old XKCD comic:

sierpinski_valentine

But it takes a special brand of geek to see that drawing as a challenge. Here’s my first attempt and its axiom:

heartLSysFirstStage

heartLSys_lq

Unfortunately, L-Systems aren’t really designed well for curves. You can draw them, but you’ve got to do something like “move forward small amount, turn 1 degree, repeat 180 times”. In L-System code this looks like this:

“DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DF”

DF = Move D forward, E+ = Turn 1 degree

But this is Valentine’s Day, and Valentine’s day should be a little hard. So here’s attempt 2:

heart2LSysFirstStage

heart2LSys_lq

 

As you can see a little closer to the mark, but we’ve got some overlap and the heart is kind of pointy at the curve transition. For attempt three I did a trick I used to do with cakes. Take a square, and add two-halves of a circle to two sides:

heart3LSysFirstStage

heart3LSys_lq

And then because it’s me, I thought, “can we make the heart just a tidge taller”:

heart4LSysFirstStage

heart4LSys_lq

Now most people would stop there, but I played around with a couple of other variants:

heart5LSysFirstStage

heart5LSys_lq

heart6LSysFirstStage

heart6LSys_lq

And then I thought, well now that I have this heart object, what else can I do with it?

heart4CloverLSys_lq

heart6CloverLSys_lq

heart12CloverLSys_lq

Here’s the code for “Heart 3” my first successful attempt, which works with the programs in Chapter 4 of my book:

<?xml version="1.0">
<lSystemSpec>
 <imageAttr prefix="heart3LSys" lvl="6" scaling="0.5"></imageAttr>
 <ruleMappings turnAngle="15" length="250">
 <rule cmd="forward" char="F"></rule>
 <rule cmd="right" char="+"></rule>
 <rule cmd="left" char="-"></rule>
 <rule cmd="begRecr" char="["></rule>
 <rule cmd="endRecr" char="]"></rule>
 <rule cmd="move" char="fg"></rule>
 </ruleMappings>
 <transformations axiom="Cg[X]BgA-TfRS-[X]S-RTfA-Bg[X]">
 <replace char="X" replStr="Cg[X]BgA-TfRS-[X]S-RTfA-Bg[X]"></replace>
 <replace char="f" replStr="F"></replace>
 <replace char="R" replStr="DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DFE+DF"></replace>
 </transformations>
 <variables>
 <var char="A" value="9"></var>
 <var char="B" value="4.25"></var>
 <var char="C" value="-4.25"></var>
 <var char="D" value="0.034906585039886591538473815369772"></var>
 <var char="E" value="0.066666666666666666666666666666667"></var>
 <var char="S" value="3"></var>
 <var char="T" value="4"></var>
 </variables>
</lSystemSpec>

Technically the “R’s” should be replaced with the whole long string and you can get rid of the R replacement rule, but I left it this way for readability. High-quality versions of the image are available by clicking on the image.

Happy Valentine’s Day, especially to you, the little red-haired girl 😉

2 Comments

Filed under Uncategorized

Fractal Friday (Or Sierpinski Saturday)

The Sierpinski triangle (or gasket as his friends call him) is everywhere. It’s hiding in the rows of Pascal’s triangle, emerging from the Chaos Game, or being drawn by turtles in all sorts of imaginative ways. I hear from a reliable source that my EPP teacher from 6th grade might be introducing his class to this ubiquitous fractal. So, for today’s Fractal Friday, I thought I’d show you just a few of the places that gasket likes to show up:

The Chaos Game

SierpinskiChaosGame

1. Choose 3 vertices of a triangle.

2. Pick a point inside that triangle.

3. Each time we draw a new point, we roll a die to determine which vertex we’re moving toward.

4. Draw a point halfway between your current point, and the vertex you rolled.

5. Repeat 1000s of times.

(Read here for more details, or Chapter 1 of Fractals: A Programmer’s Approach)

Affine Transformations

SierpinskiAffineColor

Similar to the Chaos Game, but this time using transformation equations. The basic form of an affine transformation is:

x' = ax+by+e
y' = cx+dy+f

With x and y being your current position, and x’ and y’ being your new point. The constants a-f determine where your next point will go.

For the Sierpinski Triangle we use three sets of equations:

1) x' = 0.5*x + 0.0*y + 0.0
   y' = 0.0*x + 0.5*y + 0.0
2) x' = 0.5*x + 0.0*y + 0.5
   y' = 0.0*x + 0.5*y + 0.0
3) x' = 0.5*x + 0.0*y + 0.25
   y' = 0.0*x + 0.5*y + 0.5

(For more details check out Chapter 2 of Fractals: A Programmer’s Approach)

Turtle Graphics

SierpinskiTurtle

Drawn using a series of commands for drawing a line forward or turning to the right or left. The name “turtle graphics” comes from the imaginary turtle representing the current position of the draw cursor. By giving the turtle a series of commands to draw a line forward, or turn, we can create all sorts of images including the one above. The pseudo-code for drawing the Sierpinski Gasket can be found in Abelson and diSessa’s Turtle Geometry (page 88):

TO NESTED.TRIANGLE SIZE
   IF SIZE < 10 THEN RETURN
   REPEAT 3
      NESTED.TRIANGLE SIZE/2
      FORWARD SIZE
      RIGHT 120

(For more details check out Chapter 3 of Fractals: A Programmer’s Approach or Turtle Geometry by Abelson and diSessa)

L-Systems

SierpinskiGasketLSys

L-Systems (named for Aristid Lindenmayer who created them) are a different way of describing the commands we give to our metaphorical turtle. We use a sequence of characters to give the turtle commands; typically F for forward, + for turn right, and – for turn left. Sometimes we use another character like G or f to move forward without drawing a line.

We start with a string (sentence) of characters called the Axiom. For a triangle this is often F++F++F (each turn is 60 degrees). We go through this string a character at a time and replace certain characters according to our replacement rules. After doing this a number of times, we go through the string of characters again, but this time just execute the commands they represent to draw the final shape. There are a number of L-Systems for drawing the Sierpinski triangle. Here are a few of my favorites:

Classic Gasket

Forward = “F”, Right = “+”, Left = “-“, Move = “G”
Axiom = “F--F--F”
Replacement rules = {F --> F--F--F--GG, G --> GG}

Sierpinski Arrowhead

SierpinskiArrowheadLSys

Forward = "A and B", Right = "+", Left = "-"
Axiom = “A”
Rules = {A --> B-A-B, B --> A+B+A}

Sierpinski Maze

SierpinskiMazeLSys

Forward = “F”, Right = “+”, Left = “-“
Beg recursion = “[“, End recursion = “]”, Move = “f”
Axiom = “F”, Variables {A = 3}
Replacement rules = {F -> [fF][+fA-F][f+f+F], f -> ff}

(For more details look here, or check out Chapter 4 of Fractals: A Programmer’s Approach)

Pascal’s Triangle

pascal-overlay-mod2

Image Source (Math Research, Tips and Trickshttp://malsmath.blogspot.com/2006/12/pascals-triangle-and-prime-numbers.html)

Pascal’s triangle, each row created by adding the numbers of the row above it, contains the Sierpinski triangle (and a number of other interesting patterns), depending on how you shade in the numbers. If you shade all odd numbers, there’s that gasket.

So that’s … seven methods for drawing the Sierpinski triangle. Know any others?

1 Comment

Filed under Writing