Ternary Sierpinski Triangle ( http://www.keithschwarz.com/interesting/code/ternary-sierpinski/js/ternary-sierpinski.js )

gistfile1.js

/*************************************************************************
 * File: ternary-sierpinski.js
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * An implementation of the ternary Sierpinski triangle algorithm for
 * drawing approximations of the Sierpinski triangle.
 *
 * This algorithm works by subdividing the triangle into three smaller
 * triangles, one in each corner.  These are labeled 0, 1, and 2 according
 * to some consistent ordering.  We then write out the numbers 0, 1, 2, 
 * 3, ..., 3^n - 1 in ternary.  The digits of these numbers then can be
 * read off to determine which of the small, upward-facing triangles in
 * the Sierpinski triangle should be drawn.  For example, if we want to 
 * get an order-2 Sierpinski triangle, we would write out the first nine
 * ternary numbers:
 *
 *    00 01 02 10 11 12 20 21 22
 *
 * We can then map these digits to different pieces of the triangle.  The
 * number 00 corresponds to the small 0 triangle of the 0 subtriangle,
 * while the number 12 corresponds to the 2 triangle of the 1 subtriangle.
 * If we have 0 be the lower-left triangle, 1 be the lower-right triangle,
 * and 2 be the upper triangle, the above numbers would give us the
 * following drawing:
 *
 *               22
 *             20  21
 *           02      12
 *         00  01  10  11
 *
 * If we did this with three digits, we'd get the following:
 *
 *                      222
 *                   220  221
 *                202       212
 *             200  201  210  211
 *          022                 122
 *       020  021            120  121
 *    002       012       102       112
 * 000  001  010  012  100   101  110 111
 *
 * The beauty of this algorithm is that we can draw each triangle
 * independently of the others.  In fact, given any number, we can map it
 * to which of the smaller triangles it belongs in.
 *
 * For simplicity in the implementation, we read off the digits of the
 * numbers in reverse by stripping off the last digit of the number at
 * each step.  This allows us to use modulus and division to extract
 * digits rather than using harder math.
 */
 
/* Constant: kDirectionVectors
 * -----------------------------------------------------------------------
 * Vectors representing the direction to move from the 0 triangle to
 * get to the 1 triangle or 2 triangle.  We use these constants in order
 * to easily navigate between subtriangles based on the current digit.
 * Each vector is scaled assuming that the main triangle has width one.
 */
kDirectionVectors = [ 
  /* 0 subtriangle is at distance 0 from itself. */
  [ 0.0, 0.0 ],
  
  /* 1 subtriangle is halfway across from the 0 subtriangle. */
  [ 0.5, 0.0 ],
  
  /* 2 subtriangle is translated by 0.5 distance at a 60 degree angle.  Since
   * the coordinate system is inverted, we have to flip the Y coordinate.
   */
  [ 0.5 * Math.cos(Math.PI / 3), -0.5 * Math.sin(Math.PI / 3)]
];

/* Function: drawSingleTriangle(context, number, numDigits, size);
 * Usage: drawSingleTriangle(myCanvas.getContext("2d"), 137, 6, 100);
 * -----------------------------------------------------------------------
 * Given an index of a triangle to draw, the number of digits of precision
 * used to draw the triangle, and a canvas's 2D context, draws that
 * specific triangle in the Sierpinski approximation.
 */
function drawSingleTriangle(context, number, numDigits, size) {
  /* Helper function that draws a single equilateral triangle of the given
	 * size, given the coordinate of its lower-left corner and its size.
	 */
	function drawTriangle(context, x, y, size) {
		context.moveTo(x, y);
		context.beginPath();
		context.lineTo(x + size, y);
		context.lineTo(x + size * Math.cos(Math.PI / 3),
		               y - size * Math.sin(Math.PI / 3));
		context.lineTo(x, y);
		context.closePath();
		context.fill();
	}

	/* Helper function that actually does the drawing.  It stores as extra
	 * information the current size of the triangle, along with the
	 * current location.
	 */
	function recDrawTriangle(context, number, numDigits, x, y, size) {
		/* If we've gone through all the digits, just draw the triangle
		 * where we are.
		 */
		if (numDigits === 0) {
			drawTriangle(context, x, y, size);
		}
		/* Otherwise, recurse into the proper subtriangle. */
		else {
			/* Strip the last digit off the number. */
			var digit = number % 3;
			
			/* Recursively descend into the proper triangle. */
			recDrawTriangle(context,                // Same context
			                Math.floor(number / 3), // Strip trailing digit
			                numDigits - 1,          // One fewer digit
			                x + kDirectionVectors[digit][0] * size, // Next triangle
			                y + kDirectionVectors[digit][1] * size,
			                size / 2);              // Smaller triangle
		}
	}
	
	/* Fire off the recursive call, starting in the bottom-left corner. */
	recDrawTriangle(context, number, numDigits,
	                0, context.canvas.height,
	                size); 
}