CTEs with Multiple Recursive Members, Part 2

When people write recursive common table expressions (CTEs) in T-SQL, they mostly use a single recursive member (the inner query with the reference to the CTE name). In Part 1 of this article ("CTEs with Multiple Recursive Members"), I covered more complex types of recursive CTEs that involve multiple recursive members. I demonstrated two practical use cases involving genealogy queries and the nested sets model for graphs. In this article, I demonstrate a third use case that isn't practical -- but I had a lot of fun working on it! I explain how to use a recursive CTE with multiple recursive members to draw a Koch snowflake. First, I describe what a Koch snowflake is. Next, I provide solutions to generate a Koch snowflake with T-SQL. For more information about Koch snowflakes, see the Wikipedia "Koch snowflake" entry.

Koch Snowflake

A Koch snowflake is a certain kind of fractal. You start with an equilateral triangle, as Figure 1 shows.

Figure 1: Starting Step for Koch Snowflake

To generate the next step of the fractal, you apply the following for each line segment from the previous step:

1. Draw a line made of one third of the line from the previous step (call the length L/3).
2. Turn 60 degrees outward and draw a line with a length L/3.
3. Turn 120 degrees inward and draw a line with a length L/3.
4. Turn 60 degrees outward and draw a line with a length L/3.

Figure 2 shows the transition of a line segment from one step to the next.

Figure 2: Transition to Next Step 

You can apply this logic recursively for any number of iterations to generate a Koch snowflake with varying levels of detail. As an example, Figure 3 demonstrates the fractals generated in each of five iterations of this recursive algorithm.

Figure 3: Koch Snowflake Iterations 

Next, I'll demonstrate how you can generate a Koch snowflake with T-SQL using a recursive CTE.

Koch Snowflake Table Function

In this section, I'll show you how to draw a Koch snowflake using a recursive CTE and the GEOMETRY spatial datatype. The solution relies on a helper inline table-valued function called GetEndPoint. The function accepts as inputs the x and y coordinates of a starting point of a line, an angle (in degrees) and distance, and it returns the x and y coordinates of the end point of the line. Run the code in Listing 1 to create the function in a database of your choice.

IF OBJECT_ID('dbo.GetEndPoint') IS NOT NULL
  DROP FUNCTION dbo.GetEndPoint;
GO

CREATE FUNCTION dbo.GetEndPoint
(
  @x     AS FLOAT,
  @y     AS FLOAT,
  @dist  AS FLOAT,
  @angle AS FLOAT
) RETURNS TABLE
AS
RETURN
  SELECT @x + @dist * COS(PI()*@angle/180) AS x, @y + @dist * SIN(PI()*@angle/180) AS y;
GO

The function uses the following expressions to compute the end point's x and y coordinates:

End point x = @x + @dist * COS(PI()*@angle/180)
End point y = @y + @dist * SIN(PI()*@angle/180) 

Since the COS and SIN functions in T-SQL accept the angle in radians, the code converts the input angle in degrees to radians using the expression PI()*@angle/180.

I implemented a solution that draws a Koch snowflake using an inline table function called KochSnowflakeColored. Run the code in Listing 2 to create the function. This function accepts as input the number of iterations that you want the function to apply. It returns the snowflake generated by the last iteration as a set of GEOMETRY typed values representing the line segments of the snowflake.

IF OBJECT_ID('dbo.KochSnowflakeColored') IS NOT NULL
  DROP FUNCTION dbo.KochSnowflakeColored;
GO

CREATE FUNCTION dbo.KochSnowflakeColored
(
  @iterations AS INT
) RETURNS TABLE
AS
RETURN
  WITH Koch(iteration, length, angle, x0, y0, x1, y1) AS
  (

  -- anchor members

  -- side b
  SELECT
    1 AS iteration, 100E0 as length, 60E0 AS angle,
    0E0 AS x0, 0E0 AS y0, x as x1, y as y1
  FROM dbo.GetEndPoint(0E0, 0E0, 100E0, 60E0) AS P

  UNION ALL

  -- side a
  SELECT
    1 AS iteration, 100E0 as length, 300E0 AS angle,
    x AS x0, y AS y0, 100E0 AS x1, 0E0 AS y1
  FROM dbo.GetEndPoint(0E0, 0E0, 100E0, 60E0) AS P

  UNION ALL

  -- side c
  SELECT
    1 AS iteration, 100E0 as length, 180E0 AS angle,
    100E0 AS x0, 0E0 AS y0, 0E0 AS x1, 0E0 AS y1

  UNION ALL

  -- recursive members

  -- segment 1
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    P.x0, P.y0, A2.x AS x1, A2.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length, P.angle AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length, A1.angle) AS A2
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 2
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A2.x AS x0, A2.y AS y0, A3.x AS x1, A3.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length,
          P.angle - CAST(P.angle AS INT) + CAST(P.angle + 60E0 AS INT) % 360 AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length, P.angle) AS A2
    CROSS APPLY dbo.GetEndPoint(A2.x, A2.y, A1.length, A1.angle) AS A3
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 3
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A3.x AS x0, A3.y AS y0, A2.x AS x1, A2.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length,
          P.angle - CAST(P.angle AS INT) + CAST(P.angle + 300E0 AS INT) % 360 AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length * 2, P.angle) AS A2
    CROSS APPLY dbo.GetEndPoint(A2.x, A2.y, A1.length, A1.angle + 180E0) AS A3
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 4
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A2.x AS x0, A2.y AS y0, P.x1, P.y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length, P.angle AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length * 2, A1.angle) AS A2
  WHERE P.iteration < @iterations
  )
  SELECT
    GEOMETRY::STLineFromText('LINESTRING('
  + STR(x0, 12, 9) + ' '
  + STR(y0, 12, 9) + ','
  + STR(x1, 12, 9) + ' '
  + STR(y1, 12, 9) + ' '
  + ')', 0) AS line
  FROM Koch
  WHERE iteration = @iterations;
GO

The CTE body defines three anchor members, generating the three sides of the triangle representing the first step, or iteration, of the snowflake. As an example, the following anchor member implements side b of the triangle (see Figure 1):

SELECT
  1 AS iteration, 100E0 as length, 60E0 AS angle,
  0E0 AS x0, 0E0 AS y0, x as x1, y as y1
FROM dbo.GetEndPoint(0E0, 0E0, 100E0, 60E0) AS P

I chose an arbitrary length of 100 for the lines in the first iteration and an arbitrary starting point with coordinates x = 0 and y = 0. SQL Server Management Studio (SSMS) will adapt to the coordinates and proportions of the snowflake when presenting it in the Spatial results tab. So this query returns the following information for side b of the triangle: Length = 100; starting point (x, y) = (0, 0); angle = 60 degrees (with respect to x axis, anticlockwise). The line end point's coordinates are computed by the GetEndPoint function. In a similar way, two additional anchor members generate the information for sides a and c of the triangle.

Next, the CTE body defines four recursive members that create, from each line segment from the previous iteration, four new line segments based on the logic described earlier and illustrated in Figure 2. As an example, the following recursive member generates the first line segment in the new step (from left to right in Figure 2):

SELECT
  P.iteration + 1 AS iteration, A1.length, A1.angle,
  P.x0, P.y0, A2.x AS x1, A2.y AS y1
FROM Koch AS P
  CROSS APPLY (SELECT P.length / 3 AS length, P.angle AS angle) AS A1
  CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length, A1.angle) AS A2
WHERE P.iteration < @iterations 

The recursive reference to Koch (aliased as P) represents the line segments from the previous round. The first APPLY operator in the code uses a table expression to compute the length of the new line as a third of the length of the previous line, and the angle as the same one for the previous line. The starting point of the new line is the same as the starting point for the old line. The ending point is computed with a second APPLY operator using the GetEndPoint function.

In a similar way, three additional recursive members are used to generate the remaining three line segments. All recursive queries have the filter WHERE P.iteration < @iterations. This filter allows recursion to continue as long as the requested number of iterations hasn't been reached yet. After the requested number of iterations is processed, in the next round, all recursive members will return an empty set and recursion will stop.

The outer query filters only the line segments generated in the last round. It constructs the individual lines using the STLineFromText static method of the GEOMETRY type, providing as input to the method a string made of the LINESTRING option with the coordinates of the line. Each line is considered a separate GEOMETRY object, and for different objects SSMS uses different colors. That's why I named the function KochSnowflakeColored.

Use the following code to test the function with 5 iterations:

SELECT * FROM dbo.KochSnowflakeColored(5);

You'll get the output shown in the fifth iteration in Figure 3.

Koch Snowflake Scalar Function

The solution provided in Listing 2 is implemented as an inline table function, returning a row with a GEOMETRY object for each line segment in the resulting fractal. SSMS limits the number of spatial objects it presents graphically in the Spatial results tab. Try generating a fractal with 7 iterations by running the following code:

SELECT * FROM dbo.KochSnowflakeColored(7);

Then click the Spatial results tab, and you'll get the following error message:

Too many spatial objects to display -- displaying the first 5000 objects.   Please refine your query.

If you want to be able to display more detailed fractals, you can use the STMLineFromText static method of the GEOMETRY type with the option MULTILINESTRING as input, with one multi-line string object instead of many individual-line string objects. With this option, you can implement the solution as a scalar function that returns one multi-line string GEOMETRY object for the whole fractal. You can use the FOR XML PATH option to concatenate the coordinates of the different line segments into one string. Use the code in Listing 3 to create the KochSnowflake scalar function.

IF OBJECT_ID('dbo.KochSnowflake') IS NOT NULL
  DROP FUNCTION dbo.KochSnowflake;
GO

CREATE FUNCTION dbo.KochSnowflake
(
  @iterations AS INT
) RETURNS GEOMETRY
AS
BEGIN

  DECLARE
    @length AS FLOAT = 100E0,
    @result AS GEOMETRY;

  WITH Koch(iteration, length, angle, x0, y0, x1, y1) AS
  (

  -- anchor members

  -- side b 
  SELECT
    1 AS iteration, @length as length, 60E0 AS angle,
    0E0 AS x0, 0E0 AS y0, x as x1, y as y1
  FROM dbo.GetEndPoint(0E0, 0E0, @length, 60E0) AS P

  UNION ALL

  -- side a
  SELECT
    1 AS iteration, @length as length, 300E0 AS angle,
    x AS x0, y AS y0, @length AS x1, 0E0 AS y1
  FROM dbo.GetEndPoint(0E0, 0E0, @length, 60E0) AS P

  UNION ALL

  -- side c
  SELECT
    1 AS iteration, @length as length, 180E0 AS angle,
    @length AS x0, 0E0 AS y0, 0E0 AS x1, 0E0 AS y1

  UNION ALL

  -- recursive members

  -- segment 1
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    P.x0, P.y0, A2.x AS x1, A2.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length, P.angle AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length, A1.angle) AS A2
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 2
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A2.x AS x0, A2.y AS y0, A3.x AS x1, A3.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length,
          P.angle - CAST(P.angle AS INT) + CAST(P.angle + 60E0 AS INT) % 360 AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length, P.angle) AS A2
    CROSS APPLY dbo.GetEndPoint(A2.x, A2.y, A1.length, A1.angle) AS A3
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 3
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A3.x AS x0, A3.y AS y0, A2.x AS x1, A2.y AS y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length,
          P.angle - CAST(P.angle AS INT) + CAST(P.angle + 300E0 AS INT) % 360 AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length * 2, P.angle) AS A2
    CROSS APPLY dbo.GetEndPoint(A2.x, A2.y, A1.length, A1.angle + 180E0) AS A3
  WHERE P.iteration < @iterations

  UNION ALL

  -- segment 4
  SELECT
    P.iteration + 1 AS iteration, A1.length, A1.angle,
    A2.x AS x0, A2.y AS y0, P.x1, P.y1
  FROM Koch AS P
    CROSS APPLY (SELECT P.length / 3 AS length, P.angle AS angle) AS A1
    CROSS APPLY dbo.GetEndPoint(P.x0, P.y0, A1.length * 2, A1.angle) AS A2
  WHERE P.iteration < @iterations
  )
  SELECT @result = GEOMETRY::STMLineFromText
  ('MULTILINESTRING (' +
    STUFF(
  (SELECT
       ',('
     + STR(x0, 12, 9) + ' '
     + STR(y0, 12, 9) + ','
     + STR(x1, 12, 9) + ' '
     + STR(y1, 12, 9) + ')'
   FROM Koch
   WHERE iteration = @iterations
   FOR XML PATH('')), 1, 1, '') + ')', 0
  );

  RETURN @result;
END
GO

Run the following code to test the function with five iterations:

SELECT dbo.KochSnowflake(5);

Now you can create fractals with up to eight iterations. With nine iterations, the spatial object is too large to display.

Saved the Best for Last

In my previous article and this article, I covered recursive CTEs with multiple anchor and recursive members. Last month, I showed implementations related to genealogy queries and to the nested sets model for graphs. This month, I showed an implementation that draws a Koch snowflake. All the examples were interesting for me to work on -- and I hope you enjoyed them also -- but the one I enjoyed the most was the Koch snowflake.