Code Along – Circles

A code-along is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you shouldnot cut-and-paste.

In this code-along, we will look at two different ways to build a circle using brick functions and traversals. The basic idea in both programs is to use the standard formula for a circle in the xz-plane. In the formula shown below, (a,b) denotes the center of the circle in the xz-plane, and r denotes the radius of the circle.

The approach in both programs is to traverse an appropriate set of points in the xz-plane. For each point (x,y,z) encountered we plug-in the values of (x,z) into the equation (x-a)² + (z-b)². The resulting value is the square of a candidate radius. If this candidate radius is less than or equal to our desired radius, then we place a brick at the point (x,y,z); otherwise we leave the point empty.

Code-along Program 1

In this program, our circle function takes two parameters: (1) the desired radius of the circle to be created, and (2) a point in 3D space denoting the center of the circle. The body of the functioncircle consists of a let-block in which a function called brickFn is declared. This function converts the standard formula for a circle into an inequality that asks whether the point under consideration falls inside or outside of the circle. The function brickFn is then passed as a parameter to the function traverseWithin which traverses the entire virtual space.

Due to the discrete nature of Bricklayer, the circle created has a diameter of 2*radius + 1. Also note that in the body of brickFn, the expression radius*radius is evaluated anew for every point to which brickFn is applied.

open Level_5; 

fun circle radius (xCenter,yCenter,zCenter) =
  let
    fun brickFn (x,y,z) = 
      let
         val x1 = x - xCenter;
         val z1 = z - zCenter;
                                               
         val inCircle = radius*radius >= x1*x1 + z1*z1;
      in
         if inCircle then BLUE else EMPTY
      end
  in
    traverseWithin (0,0,0) (21,0,21) brickFn
  end;

build(22,1,22);

circle 10 (11,0,11);

show "circle";

Code-along Program 2

The program in this example is a slightly improved version of the previous program. Specifically, three improvements have been made. First, the evaluation of radius*radius has been moved out of the body of brickFn and assigned to the variable r2. This way radius*radius is evaluated only one time. Second, the region traversed is defined in terms of the center of the circle and its radius. As a result a circle function can now have its center anywhere within the virtual space. And third, for points lying outside the circle, brickFn will return the IDENTITY brick. This has the effect of leaving undisturbed points within the traversal region but outside the circle.

One problem with the current implementation is that the circle four “pointy” parts. Specifically, the parts of the circle having smallest/largest values of x and z consist of a single brick. It would be nice to smooth out this part of the circle.

open Level_5; 

fun circle radius (xCenter,yCenter,zCenter) =
    let
        val r2 = radius*radius
        fun brickFn (x,y,z) = 
            let
                 val x1 = x - xCenter;
                 val z1 = z - zCenter;
                                               
                 val inCircle = r2 >= x1*x1 + z1*z1;
            in
                if inCircle then BLUE else IDENTITY
            end;
        val xLo = xCenter - radius; 
        val xHi = xCenter + radius; 
        val zLo = zCenter - radius; 
        val zHi = zCenter + radius;        
    in
        traverseWithin (xLo, yCenter, zLo) 
                       (xHi, yCenter, zHi) 
                       brickFn
    end;

build(22,1,22);

circle 10 (11,0,11);

show "circle";

Code-along Program 3

The problem with the previous implementations is that the radius comparison involve calculations that were strictly integer-based. In the program below, integer points are converted to real numbers and the radius comparison expression involves a square root calculation whose result is then rounded to the nearest integer value. It is this rounding of the square root which smooths out the circle.

open Level_5; 

fun circle radius (xCenter,yCenter,zCenter) =
  let
    fun brickFn (x,y,z) = 
      let
         val x1 = Real.fromInt x - Real.fromInt xCenter;
         val z1 = Real.fromInt z - Real.fromInt zCenter;
          
         val r = Math.sqrt( x1*x1 + z1*z1 );                             
         val inCircle = radius >= Real.round( r );
      in
         if inCircle then BLUE else IDENTITY
      end;
    val xLo = xCenter - radius; 
    val xHi = xCenter + radius; 
    val zLo = zCenter - radius; 
    val zHi = zCenter + radius;               
  in
    traverseWithin (xLo, yCenter, zLo) 
                   (xHi, yCenter, zHi) 
                   brickFn 
  end;

build(22,1,22);

circle 10 (11,0,11);

show "circle";