Friday, December 11, 2015

Drawing Simple Triangular Fractals in SQL Server Management Studio

At first, want to show you the end result. That is something you can draw in your SSMS and even much more:
At second, want to share the script to draw that picture:
001  /*
002  Script which draws very nice Triangle Based Fractals
003  */
004  SET NOCOUNT ON
005  GO
006  IF Exists (
007      SELECT TOP 1 1 FROM tempdb.sys.tables
008      WHERE object_id = OBJECT_ID('tempdb.dbo.#Triangles')
009  ) DROP TABLE #Triangles
010  GO
011  CREATE TABLE #Triangles( Finished BIT NULL
012      , Radius FLOAT NOT NULL
013      , Angle FLOAT NOT NULL
014      , Center_X FLOAT NOT NULL
015      , Center_Y FLOAT NOT NULL
016      , Point1_X FLOAT NOT NULL
017      , Point1_Y FLOAT NOT NULL
018      , Point2_X FLOAT NOT NULL
019      , Point2_Y FLOAT NOT NULL
020      , Point3_X FLOAT NOT NULL
021      , Point3_Y FLOAT NOT NULL
022      , TriangleLevel TINYINT NOT NULL
023      , TriangleID INT IDENTITY(1,1)
024      , Triangle as geometry::STGeomFromText('POLYGON((' +
025          CAST(Point1_X as VARCHAR) + ' ' + CAST(Point1_Y as VARCHAR) + ',' +
026          CAST(Point2_X as VARCHAR) + ' ' + CAST(Point2_Y as VARCHAR) + ',' +
027          CAST(Point3_X as VARCHAR) + ' ' + CAST(Point3_Y as VARCHAR) + ',' +
028          CAST(Point1_X as VARCHAR) + ' ' + CAST(Point1_Y as VARCHAR) + '))', 4326)
029  );
030  GO
031  DECLARE @CenterX FLOAT = 0;            -- Triangle CenterX
032  DECLARE @CenterY FLOAT = 0;            -- Triangle CenterY
033  DECLARE @Radius FLOAT = 1000;        -- Triangle Radius
034  DECLARE @Angle FLOAT = 30;            -- Triangle Orientation Angle
035  DECLARE @MaxLevel TINYINT = 7;
036  DECLARE @CurrLevel TINYINT = 1;
037  DECLARE @Rate FLOAT = 0.825;
038 
039  -- Step 1. Drawing very first Triangle
040  INSERT INTO #Triangles
041  SELECT 0, @Radius, @Angle, @CenterX, @CenterY
042      , COS(RADIANS(@Angle-60))*@Radius + @CenterX
043      , SIN(RADIANS(@Angle-60))*@Radius + @CenterY
044      , COS(RADIANS(@Angle+60))*@Radius + @CenterX
045      , SIN(RADIANS(@Angle+60))*@Radius + @CenterY
046      , COS(RADIANS(@Angle+180))*@Radius + @CenterX
047      , SIN(RADIANS(@Angle+180))*@Radius + @CenterY
048      , @CurrLevel;
049 
050  -- Step 2. Looping through Triangle Levels
051  WHILE @CurrLevel < @MaxLevel
052  BEGIN
053 
054  -- Step 2.1. Generating Next Level Triangles
055      ;WITH NextLevel as (
056          -- This section dictate how many child triangles will be created and where they will be located
057          /*Side Values: 0,1,2 */
058          /*Position Values: -1,1 */
059          SELECT 0 as Side, -1 as Position
060          UNION ALL SELECT 0, 1
061          UNION ALL SELECT 1, 1
062          UNION ALL SELECT 1, -1
063          UNION ALL SELECT 2, 1
064          UNION ALL SELECT 2, -1
065          ),
066      NextTriangle as (
067          -- Extract data for parent triangle
068          SELECT Radius, Angle, Center_X, Center_Y
069          FROM #Triangles WHERE Finished = 0
070      ),
071      Triangles as (
072          -- Calculating position of the new triangle and its dimensions
073          SELECT Radius * @Rate / 2 as Radius, Angle + 60 as Angle
074              , Center_X = COS(RADIANS(Angle + Side*120)) * (Radius / 2 + Radius * @Rate / 4) + Center_X
075              -- Adjustment of the position of new triangle on the edge of the parent
076                  + Position * (SIN(RADIANS(60.)) * (Radius - Radius * @Rate / 2)) * COS(RADIANS(Angle - 90 + Side*120))
077              , Center_Y = SIN(RADIANS(Angle + Side*120)) * (Radius / 2 + Radius * @Rate / 4) + Center_Y
078              -- Adjustment of the position of new triangle on the edge of the parent
079                  + Position * (SIN(RADIANS(60.)) * (Radius - Radius * @Rate / 2)) * SIN(RADIANS(Angle - 90 + Side*120))
080          FROM NextTriangle, NextLevel
081      )
082      -- Finak calculation of new triangle corners.
083      INSERT INTO #Triangles
084      SELECT Null, Radius, Angle, Center_X, Center_Y
085          , COS(RADIANS(Angle-60))*Radius + Center_X
086          , SIN(RADIANS(Angle-60))*Radius + Center_Y
087          , COS(RADIANS(Angle+60))*Radius + Center_X
088          , SIN(RADIANS(Angle+60))*Radius + Center_Y
089          , COS(RADIANS(Angle+180))*Radius + Center_X
090          , SIN(RADIANS(Angle+180))*Radius + Center_Y
091          , @CurrLevel
092      FROM Triangles
093 
094  -- Step 2.2. Finishing (assigning "1") previous level triangles and Initiating (assigning "0") newly created trianles
095      UPDATE #Triangles SET Finished = CASE WHEN Finished = 0 THEN 1 ELSE 0 END
096      WHERE Finished = 0 or Finished is Null
097 
098  -- Step 2.3. Incremant Level
099      SET @CurrLevel += 1
100  END
101 
102  -- Step 3. Extracting Spatial data
103  ;WITH p as (
104      -- Generating Buckets and POLYGON text string for each triangle
105      SELECT TriangleLevel,
106          Bucket = TriangleID % CAST(CEILING((SELECT SQRT(count(*)) FROM #Triangles)) as INT),
107          Polygon = 'POLYGON((' +
108              CAST(Point1_X as VARCHAR) + ' ' + CAST(Point1_Y as VARCHAR) + ',' +
109              CAST(Point2_X as VARCHAR) + ' ' + CAST(Point2_Y as VARCHAR) + ',' +
110              CAST(Point3_X as VARCHAR) + ' ' + CAST(Point3_Y as VARCHAR) + ',' +
111              CAST(Point1_X as VARCHAR) + ' ' + CAST(Point1_Y as VARCHAR) + '))'
112      FROM #Triangles
113  ), Buckets as (SELECT DISTINCT Bucket FROM p)
114  , Collections as (
115      -- Generating GEOMETRYCOLLECTION for each generated Bucket
116      SELECT b.Bucket, Polygon = geometry::STGeomFromText('GEOMETRYCOLLECTION(' +
117          SUBSTRING((
118          SELECT CAST(',' as VARCHAR(MAX)) + CAST(Polygon as VARCHAR(MAX))
119          FROM p WHERE p.Bucket = b.Bucket
120          FOR XML PATH('')),2,2147483647) + ')', 4326)
121      FROM Buckets as b
122  )
123  -- Extracting Spatial Data
124  SELECT Polygon FROM Collections

At third, if you want to learn more about how that script works keep reading.

1. Script Parameters and variables:

- @CenterX & @CenterY - Starting point of the initial triangle. It is set to (0,0), but really does not matter unless you have special requirements.

- @Radius - That is a Radius of Circumscribed circle of the Initial Triangle. It can be any, but do not make it too small because you can loose precision.

- @Angle - An Angle you want your Initial Triangle to be turned. It really does not matter, you just have ability to rotate Fractal on the screen. Try to use value "15" for better effect visibility.

- @MaxLevel - Specifies how many levels deep you want to draw your Fractal. That value can't be big. With Max Level value "9" I've got almost 2 millions of objects. So, you can try more if you want to wait. However SSMS will not be able to show you so many objects. The maximum Number I've got was little bit lower than 250K.

- @CurrLevel - Just a variable to track current Level of Fractal's Triangles

- @Rate - Rate with which triangles will be decreasing in size. With Rate = "1" child triangle's Radius of Circumscribed circle will be twice as less Radius of the Parent's triangle. You can play with that value, but pictures might be not so nice.

2. Temporary Table

 It contains all parameters of created triangles such as
- Center point;
- Coordinates of all Corners of a triangle;
- Radius of Circumscribed circle;
- Triangle Inclination Angle;
- Level of the triangle (1 is the highest);
- Processing Bit Indicator. Set to 1 if triangle already has children;
- ID Identity field;
- Calculated Spatial field. It allows you to see graphical results by just simple selecting that field from the table.

3. Triangle construction.

There is no sacred magic in the original triangle construction, so, will start from the child generation level in Step 2.1.
3.1. Lines 59-64. Here we direct how many child triangles will have each side of a parent. To demonstrate that change value of variable "@MaxLevel = 2" and replace that section with the following and run the whole script:
        SELECT 0 as Side, 0 as Position
        UNION ALL SELECT 1, 1
        UNION ALL SELECT 1, -1
        UNION ALL SELECT 2, 1
        UNION ALL SELECT 2, 0
        UNION ALL SELECT 2, -1
As the result you have to have something like this:
First side has only one child in the center, second have two children near corners and third one has all places filled. You can specify only one side by replacing what section by just "SELECT 0 as Side, 1 as Position" and changing variable "@Rate = 1.5097. Then you can get something like this:

3.2. Lines 68-69 - Simple extraction of Parent triangle parameters.
3.3. Lines 73-80 - Radius, Angles and center points of child triangles. Lines 76 & 79 are necessary to construct non-central children.
3.4. Lines 83-92 - Generation of corners of children triangles.
3.5. Lines 95-96 - Marking filled parent triangles and new children.
3.6. Line 99 - Moving to the next cycle level.

4. Triangle presentation

That is most difficult operation. At first, SSMS can't show more than 5000 separate objects at the same time. In order to show more we have to construct "MULTIPOLYGON" or "GEOMETRYCOLLECTION". That only the way to fit more objects into SSMS screen. However it is still limited.
In order to combine triangles in a single object we divide them in buckets (Line 106).
In this example I just making number of buckets approximately equal to a number of objects within each bucket. Making lower number of buckets will increase processing speed, but produce less colors. All objects in one collection will have the same color.
Also, I wrapped the last query in extra CTE to have more flexibility on results formation.

5. Playing with results

As I mentioned in #4, you can change Line 124 to produce slightly different results.
For instance you can replace it with that:
"SELECT Polygon.STBoundary() FROM Collections"
That will show ONLY the boundaries of all triangles and you might see something like this:

You also can play with number of buckets in Line 106, replacing it by following:
"Bucket = TriangleID % 5000"

6. Playing with configuration.

Besides of changing an inclination angle the biggest change is number of children triangles.
Do the following:
- Replace Lines 59-64 by following:
SELECT 0 as Side, 0 as Position
UNION ALL SELECT 1, 0
UNION ALL SELECT 2, 0
- Change "@Rate = 1.1"
- Change"@MaxLevel = 9"

You might have something like this:
If you try to explore these structures deeper and zoom it you can find beauty like this:



I understand that those fractals are not "Classical", but it is something to start with. You've got an idea and that is most important.

2 comments: