EXPLAIN EXTENDED

In one of my previous New Year's posts we drew snowflakes in PostgreSQL.

The algorithm we used to create the snowflakes is an implementation of an L-system, which is an example of a fractal. There are many more beautiful objects we can see in the winter: frozen trees, frost patterns on windows, cracks on ice etc., all of them being fractals.

Today we will be constructing escape-time fractals. To build such a fractal, one would need to run a certain function for each point on the plane iteratively and see how many iterations does it take for the function to overflow: the more it takes, the brighter is the point's color.

I won't go deep into fractal theory now, just show that they can be constructed with SQL relatively easily. For instance, Mandelbrot set, one of the best known escape-time fractals, is almost a one-liner in PostgreSQL:

WITH    RECURSIVE
        q (r, i, rx, ix, g) AS
        (
        SELECT  r::DOUBLE PRECISION * 0.02, i::DOUBLE PRECISION * 0.02, .0::DOUBLE PRECISION, .0::DOUBLE PRECISION, 0
        FROM    generate_series(-60, 20) r, generate_series(-50, 50) i
        UNION ALL
        SELECT  r, i, CASE WHEN ABS(rx * rx + ix * ix) <= 2 THEN rx * rx - ix * ix END + r, CASE WHEN ABS(rx * rx + ix * ix) <= 2 THEN 2 * rx * ix END + i, g + 1
        FROM    q
        WHERE   rx IS NOT NULL
                AND g < 99
        )
SELECT  ARRAY_TO_STRING(ARRAY_AGG(s ORDER BY r), '')
FROM    (
        SELECT  i, r, SUBSTRING(' .:-=+*#%@', MAX(g) / 10 + 1, 1) s
        FROM    q
        GROUP BY
                i, r
        ) q
GROUP BY
        i
ORDER BY
        i

Its closest relative, the Burning Ship, is also simple:

WITH    RECURSIVE
        q (r, i, rx, ix, g) AS
        (
        SELECT  r::DOUBLE PRECISION * 0.04, i::DOUBLE PRECISION * 0.04, .0::DOUBLE PRECISION, .0::DOUBLE PRECISION, 0
        FROM    generate_series(-40, 20) r, generate_series(-40, 20) i
        UNION ALL
        SELECT  r, i, CASE WHEN ABS(rx * rx + ix * ix) <= 1E8 THEN rx * rx - ix * ix END + r, CASE WHEN ABS(rx * rx + ix * ix) <= 2 THEN ABS(2 * rx * ix) END + i, g + 1
        FROM    q
        WHERE   rx IS NOT NULL
                AND g < 99
        )
SELECT  ARRAY_TO_STRING(ARRAY_AGG(s ORDER BY r), '')
FROM    (
        SELECT  i, r, SUBSTRING(' .:-=+*#%@', MAX(g) / 10 + 1, 1) s
        FROM    q
        GROUP BY
                i, r
        ) q
GROUP BY
        i
ORDER BY
        i

Now let's build something more wintery and New Year-y. For instance, this Julia set looks quite similar to cracks on ice:

WITH    RECURSIVE
        q (r, i, rx, ix, g) AS
        (
        SELECT  r::DOUBLE PRECISION * 0.000001, i::DOUBLE PRECISION * 0.000001,
                r::DOUBLE PRECISION * 0.000001, i::DOUBLE PRECISION * 0.000001,
                0
        FROM    generate_series(-40, 40) r, generate_series(-50, 50) i
        UNION ALL
        SELECT  r, i,
                CASE WHEN ABS(rx * rx + ix * ix) < 1E8 THEN rx * rx - ix * ix END + 0,
                CASE WHEN ABS(rx * rx + ix * ix) < 1E8 THEN 2 * rx * ix END + 1,
                g + 1
        FROM    q
        WHERE   rx IS NOT NULL
                AND g < 99
        )
SELECT  ARRAY_TO_STRING(ARRAY_AGG(s ORDER BY r), '')
FROM    (
        SELECT  i, r, SUBSTRING(' .:-=+*#%@', MAX(g) / 10 + 1, 1) s
        FROM    q
        GROUP BY
                i, r
        ) q
GROUP BY
        i
ORDER BY
        i

And this one resembles frost patterns on windows:

WITH    RECURSIVE
        q (r, i, rx, ix, g) AS
        (
        SELECT  r::DOUBLE PRECISION * 0.0002, i::DOUBLE PRECISION * 0.0002,
                r::DOUBLE PRECISION * 0.0002, i::DOUBLE PRECISION * 0.0002,
                0
        FROM    generate_series(-200, -120) r, generate_series(0, 100) i
        UNION ALL
        SELECT  r, i,
                CASE WHEN ABS(rx * rx + ix * ix) < 1E8 THEN rx * rx - ix * ix END - 0.70176,
                CASE WHEN ABS(rx * rx + ix * ix) < 1E8 THEN 2 * rx * ix END + 0.3842,
                g + 1
        FROM    q
        WHERE   rx IS NOT NULL
                AND g < 99
        )
SELECT  ARRAY_TO_STRING(ARRAY_AGG(s ORDER BY r), '')
FROM    (
        SELECT  i, r, SUBSTRING(' .:-=+*#%@', MAX(g) / 10 + 1, 1) s
        FROM    q
        GROUP BY
                i, r
        ) q
GROUP BY
        i
ORDER BY
        i

Finally, this beautiful Julia set (known as Glynn set) looks like a snow-covered tree:

WITH    RECURSIVE
        q (r, i, rx, ix, g) AS
        (
        SELECT  x + r::DOUBLE PRECISION * step, y + i::DOUBLE PRECISION * step,
                x + r::DOUBLE PRECISION * step, y + i::DOUBLE PRECISION * step,
                0
        FROM    (
                SELECT  0.25 x, -0.55 y, 0.002 step, r, i
                FROM    generate_series(-40, 40) r
                CROSS JOIN
                        generate_series(-40, 40) i
                ) q
        UNION ALL
        SELECT  r, i,
                CASE WHEN (rx * rx + ix * ix) < 1E8 THEN (rx * rx + ix * ix) ^ 0.75 * COS(1.5 * ATAN2(ix, rx)) END - 0.2,
                CASE WHEN (rx * rx + ix * ix) < 1E8 THEN (rx * rx + ix * ix) ^ 0.75 * SIN(1.5 * ATAN2(ix, rx)) END,
                g + 1
        FROM    q
        WHERE   rx IS NOT NULL
                AND g < 99
        )
SELECT  ARRAY_TO_STRING(ARRAY_AGG(s ORDER BY r), '')
FROM    (
        SELECT  i, r, SUBSTRING(' .:-=+*#%@', MAX(g) / 10 + 1, 1) s
        FROM    q
        GROUP BY
                i, r
        ) q
GROUP BY
        i
ORDER BY
        i

You can run the queries live on http://sqlfiddle.com (don't forget to select Plaintext Output in the drop-down menu next to Run SQL):

• Mandelbrot set
• Burning Ship
• Cracks in the ice
• Frost patterns
• Snow covered tree

Previous New Year posts:

• Happy New 2010 Year!
• Happy New 2011 Year!
• Happy New 2012 Year!
• Happy New 2013 Year!