Using Pascal's triangle to draw fractals

Triangles are a particular matrix type. Each line contains exactly as many nonzero elements as the line index in the matrix. Here is a sample triangle depicted as a vector of vectors in Clojure:

[[1 0 0 0 0 0 0]
 [1 1 0 0 0 0 0]
 [1 1 1 0 0 0 0]
 [1 1 1 1 0 0 0]
 [1 1 1 1 1 0 0]
 [1 1 1 1 1 1 0]
 [1 1 1 1 1 1 1]]

Now, we can simply omit the zeros altogether and get a real triangle, graphically speaking:

[[1]
 [1 1]
 [1 1 1]
 [1 1 1 1]
 [1 1 1 1 1]
 [1 1 1 1 1 1]
 [1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1]]

Pascal's triangle is a matrix whose elements are computed as the sum of the elements that are directly above it and the element to the left of the elements that are directly above it. The very first element is 1. This matrix was devised by Pascal as a means of computing the powers of binomials. Here's a Pascal's triangle for up to seven lines:

[[1]
 [1 1]
 [1 2 1]
 [1 3 3 1]
 [1 4 6 4 1]
 [1 5 10 10 5 1]
 [1 6 15 20 15 6 1]]

If we look at this Pascal's triangle, then a binomial, let's say (a+b), elevated to the power 4 is computed by extracting the coefficient from the row with index 4 (first row is having index 0. The resulting polynomial is: a4b+4a3b+6a2b2+4ab3+ab4.

Now, it happens that plotting odd elements from a Pascal's triangle yields a fractal, that is, an image that infinitely repeats itself.

Note

Such a fractal derived from plotting the odd elements of a Pascal's triangle is known as the Sierpinski triangle.

If you closely watch the triangle's structure, you'll notice that each line is symmetrical. As such, for the sake of efficiency, you only have to compute half of a line at a time and append it to its own mirrored copy to get the whole line.

Besides, as our main purpose is to draw fractals, we'll have to generate a huge Pascal's triangle, in order to have a proper image. Doing so will make us soon hit number limitations and we'll have to circumvent this. Luckily, summing the remainder of a division of two by two numbers leads to the same even properties, as if you've summed those very numbers. Then, our implementation will rely on this to come up with sufficiently big images; we'll create Pascal's triangles with the sums of the remainder of the division by two.

How to do it...

1. First of all we'll need to import, along with our ns declaration, some Java facilities to help us build the fractal and write it to a file:

   (ns recipe2.core
     (:import (java.awt image.BufferedImage Color) 
   ;=> so we can plot.
              (javax.imageio ImageIO) 
              (java.io File)))       ;=> so we can write to a file.

2. Let's write a function to compute a particular row in a Pascal's triangle, As we've discussed, in a Pascal's triangle you compute a row of a particular index based on the one located directly above it (of the preceding index), that's why this function takes one row as input. Here we pass a yield function, permitting it to compute an element out of its immediately preceding neighbor and the element to the left of the preceding neighbor. Each time, we compute half a line and append it to its reverse:

   (defn pascal-row-step
     [yield pascal-row]                                   
   ;=> pascal-row is the one above the row we're computing
     {:pre [(> (get  pascal-row 0) 0)]}  ;=> We can only start from [1]!
     (let [cnt-elts (count pascal-row)
           half-row (subvec pascal-row 0
                            (inc (double (/ cnt-elts 2)))) 
   ;;=> We compute half the above row
           padded-half-row (into [0] half-row)
   ;;=> and add a 0 to the beginning, as we'll use it in computation
           half-step (vec  (map (comp (partial apply yield)
                                      vec)
                                (partition 2 1
                                           padded-half-row)))
   ;;=> we compute the first half, summing the above element 
   ;;      and the element at the left of the above one.
           other-half-step (vec  (if (even? cnt-elts)
                                   (-> half-step
                                       butlast
                                       reverse)
                                   (-> half-step
                                       reverse)))]
   ;;=> the mirror of the half we computed. If count elements is
   ;; even, we omit the last element from half-step.
       (into half-step other-half-step)))
   ;;=> we return half to which we append the mirror copy.

3. Now, we'll build the whole Pascal's triangle parameterized with the yield function:

   (defn pascal-rows
     [yield row-number]
     (loop [nb 0
            result []
            latest-result [1]]     
   ;=> We'll loop using pascal-row-step,
   ;;=> keeping track of the last                                ;;computed line at each step of the recursion.
             
           (if (<= nb row-number)         
   ;;=> the counter did not still reach the end
         (recur (inc nb)
                (conj result latest-result) 
                (pascal-row-step yield latest-result))
   ;;=> We recur incrementing the counter, feeding the new line to
   ;; result and keeping track of the last computed line.
         result)))
   ;;=> end of the recursion, emitting result.

4. We will also prepare a yield function to compute the remainder of the sum of two numbers:

   (defn even-odd-yield
     [n1 n2]  
     (mod (+ n1 n2) 2))

5. We will prepare a helper function to generate the fractals:

   (def gr-triangles (partial pascal-rows even-odd-yield))

6. Now we can just launch the following to have our graphical 0-1 fractal representation:

   (gr-triangles 10)

7. With gr-triangles under our belt, we have to plot points at the positions that hold 1. For this, we'll consider the cords of such positions to be the index of line and the index of elements in the vector held by this line that have the value 1:

   (defn draw [size] 
     (let [img (BufferedImage. size size BufferedImage/TYPE_INT_ARGB)
   ;;=> Creating img as a Buffered Image
           plot-rows (gr-triangles size)
   ;;=> computing the triangle of 0 and 1
           plots (for [x (range 0 size)
                       y (range 0 x)]
                   (if (= 1 (get
                                (get plot-rows x) y))
                     [x y])) 
   ;;=> we save the positions holding 1 in vectors. As the structure ;; is triangular;
   ;; the first counter, "x" goes up to "size", and the second one, ;; "y", 
   ;;    goes up to "x"
           gfx (.getGraphics img)] 
   ;;=> we get the graphics component, where to draw from the Java 
   ;; Object.
       (.setColor gfx Color/WHITE)
       (.fillRect gfx 0 0 size size ) 
   ;;=> we set a white background for the image.
       (.setColor gfx Color/BLACK)      
   ;;=> We set the pen color to black again
       (doseq [p (filter (comp not nil?)  plots)]
         (.drawLine gfx 
                (get p 0)
                    (get p 1)
                    (get p 0)
                    (get p 1))) 
   ;;=> We plot, by drawing a line from and to the same point.
    (ImageIO/write img "png"
                      (File. "/your/location/result.png"))))
   ;;=> and we save the image as a png in this location. 
   ;; Be sure to set a correct one when running on your machine !

Here is a zoomed-out image generated by this function of the size 10,000:

Here is a zoomed-in view of some parts of it:

Here, the same triangles appear over and over again as you zoom in on the image.