pythondsSierpinskiTriangle.ptx

<section xml:id="recursion_sierpinski-triangle">
        <title>Sierpinski Triangle</title>
        <p>Another fractal that exhibits the property of self-similarity is the
            Sierpinski triangle. An example is shown in <xref ref="fig-sierpinski"/>. The
            Sierpinski triangle illustrates a three-way recursive algorithm. The
            procedure for drawing a Sierpinski triangle by hand is simple. Start
            with a single large triangle. Divide this large triangle into three new
            triangles by connecting the midpoint of each side. Ignoring the middle
            triangle that you just created, apply the same procedure to each of the
            three corner triangles. Each time you create a new set of triangles, you
            recursively apply this procedure to the three smaller corner triangles.
            You can continue to apply this procedure indefinitely if you have a
            sharp enough pencil. Before you continue reading, you may want to try
            drawing the Sierpinski triangle yourself, using the method described.</p>
        
        <figure align="center" xml:id="fig-sierpinski">
            <caption>The Sierpinski Triangle.</caption>
                <image source="Recursion/sierpinski.png" width="50%">
                <description><p>Image of the Sierpinski Triangle, a fractal composed of colored triangles. 
                    The main triangle is outlined with progressively smaller triangles in
                    alternating colors of red, green, and white, forming a pattern that repeats at smaller scales.
                    The center of the triangle features a large inverted blue triangle, emphasizing the fractal's
                    characteristic self-similarity.</p></description>
                </image>
            </figure>


        <p>Since we can continue to apply the algorithm indefinitely, what is the
            base case? We will see that the base case is set arbitrarily as the
            number of times we want to divide the triangle into pieces. Sometimes we
            call this number the <q>degree</q> of the fractal. Each time we make a
            recursive call, we subtract 1 from the degree until we reach 0. When we
            reach a degree of 0, we stop making recursive calls. The code that
            generated the Sierpinski Triangle in <xref ref="fig-sierpinski"/> is shown in
            <xref ref="lst-st-cpp"/>.</p>
        <exploration xml:id="expl-lst-st-cpp">
            <title>Darawing the Sierpinski Triangle</title>
            <task xml:id="lst-st-cpp" label="lst-st-cpp">
                <title>C++ Implementation</title>
                <statement><program xml:id="first_csierpinksi_tri" interactive="activecode" language="cpp" label="first_csierpinksi_tri-prog"><input>
#include &lt;CTurtle.hpp&gt;

namespace ct = cturtle;

void draw_triangle(ct::Point a, ct::Point b, ct::Point c, ct::Color color, ct::Turtle&amp; myTurtle){
    myTurtle.fillcolor(color);
    myTurtle.penup();
    myTurtle.goTo(a);
    myTurtle.pendown();
    myTurtle.begin_fill();
    myTurtle.goTo(c);
    myTurtle.goTo(b);
    myTurtle.goTo(a);
    myTurtle.end_fill();
}

//getMid already defined as "middle" function in C-Turtle namespace :)

void sierpinski(ct::Point a, ct::Point b, ct::Point c, int degree, ct::Turtle&amp; myTurtle){
    const std::string colormap[] = {"blue", "red", "green", "white", "yellow", "violet", "orange"};
    draw_triangle(a,b,c, {colormap[degree]}, myTurtle);
    if(degree &gt; 0){
        sierpinski(a, ct::middle(a, b), ct::middle(a, c), degree - 1, myTurtle);
        sierpinski(b, ct::middle(a, b), ct::middle(b, c), degree - 1, myTurtle);
        sierpinski(c, ct::middle(c, b), ct::middle(a, c), degree - 1, myTurtle);
    }
}

int main() {
    ct::TurtleScreen screen;
    screen.tracer(3);//Draw faster.
    ct::Turtle turtle(screen);

    ct::Point myPoints[] = {
        {-100, -50},
        {0, 100},
        {100, -50}
    };

    sierpinski(myPoints[0], myPoints[1], myPoints[2], 3, turtle);

    screen.bye();
    return 0;
}
                </input></program></statement>
            </task>
            <task xml:id="lst-st-py" label="lst-st-py">
                <title>Python Implementation</title>
                <statement><program xml:id="lst_st" interactive="activecode" language="python" label="lst_st-prog"><input>
#Recursive example of the Sierpinski Triangle.

import turtle

def drawTriangle(points,color,myTurtle):
#Draws a triangle using the diven points and color.
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.down()
    myTurtle.begin_fill()
    myTurtle.goto(points[1][0],points[1][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.end_fill()

def getMid(p1,p2):
    return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)

def sierpinski(points,degree,myTurtle):
    colormap = ['blue','red','green','white','yellow',
                'violet','orange']
    drawTriangle(points,colormap[degree],myTurtle)
    if degree &gt; 0:
        sierpinski([points[0],
                        getMid(points[0], points[1]),
                        getMid(points[0], points[2])],
                degree-1, myTurtle) #Recursive call
        sierpinski([points[1],
                        getMid(points[0], points[1]),
                        getMid(points[1], points[2])],
                degree-1, myTurtle) #Recursive call
        sierpinski([points[2],
                        getMid(points[2], points[1]),
                        getMid(points[0], points[2])],
                degree-1, myTurtle) #Recursive call

def main():
    myTurtle = turtle.Turtle()
    myWin = turtle.Screen()
    myPoints = [[-100,-50],[0,100],[100,-50]]
    sierpinski(myPoints,3,myTurtle)
    myWin.exitonclick()

main()
                </input></program></statement>
            </task>
        </exploration>
        <p>The program in <xref ref="lst-st-cpp"/> follows the ideas outlined above. The
            first thing <c>sierpinski</c> does is draw the outer triangle. Next, there
            are three recursive calls, one for each of the new corner triangles we
            get when we connect the midpoints. Once again we make use of the
            standard turtle module that comes with Python. You can learn all the
            details of the methods available in the turtle module by using
            <c>help('turtle')</c> from the Python prompt.</p>
        <p>Look at the code and think about the order in which the triangles will
            be drawn. While the exact order of the corners depends upon how the
            initial set is specified, let's assume that the corners are ordered
            lower left, top, lower right. Because of the way the <c>sierpinski</c>
            function calls itself, <c>sierpinski</c> works its way to the smallest
            allowed triangle in the lower-left corner, and then begins to fill out
            the rest of the triangles working back. Then it fills in the triangles
            in the top corner by working toward the smallest, topmost triangle.
            Finally, it fills in the lower-right corner, working its way toward the
            smallest triangle in the lower right.</p>
        <p>Sometimes it is helpful to think of a recursive algorithm in terms of a
            diagram of function calls. <xref ref="fig-stcalltree"/> shows that the recursive
            calls are always made going to the left. The active functions are
            outlined in black, and the inactive function calls are in gray. The
            farther you go toward the bottom of <xref ref="fig-stcalltree"/>, the smaller the
            triangles. The function finishes drawing one level at a time; once it is
            finished with the bottom left it moves to the bottom middle, and so on.</p>
        
        <figure align="center" xml:id="fig-stcalltree">
            <caption>Building a Sierpinski Triangle.</caption>
                <image source="Recursion/stCallTree.png" width="50%">
                <description><p>Diagram showing the recursive construction of a Sierpinski Triangle using a tree structure. The diagram starts with a single top circle labeled 'top', branching out into three interconnected circles labeled 'left', 'top', and 'right'. Each of these circles further branches out in a similar pattern, with the process repeating for several iterations. The circles decrease in size from top to bottom, representing the fractal's recursive nature. The grayscale shading of the circles suggests depth or iteration levels.</p></description>
                </image>
            </figure>

        <p>The <c>sierpinski</c> function relies heavily on the <c>middle</c> function.
            <c>middle</c> takes as arguments two endpoints and returns the point
            halfway between them. In addition, <xref ref="lst-st-cpp"/> has a function that
            draws a filled triangle using the <c>begin_fill</c> and <c>end_fill</c> turtle
            methods.</p>
        <p>The above sierpinski triangle visualization utilizes C-Turtle, a C++ equivalent of
            Python's <c>turtle</c> library, and can be found on GitHub here: <url href="https://github.com/walkerje/C-Turtle/" visual="https://github.com/walkerje/C-Turtle/">https://github.com/walkerje/C-Turtle/</url></p>
            <conclusion><p>
                <!-- extra space before the progress bar -->            
            </p></conclusion>
    </section>