Square recursive fractal

[Der_sed]

What would be the psuedo code to :

recursively draws squares. The picture shown below depicts squares drawn recursively on each of the 4 corners of a square.
• The base case is draw nothing for n = 0.
• The reduction step is to draw, on each corner of a square, another square which is halved in size.
(The ratio of the sizes of the squares is 2, that is length of the sides of the square is halved at each level)

Im using the Stroustrup GUI library for FLTK.

[sirdanman10]

Here is what I came up with. You just need to supply the code to draw the boxes, and adjust the constants at the top.

I will post an explaination in a separate post right after this.

const int startSize = 256;
const int centerX = 300;
const int centerY = 300;

unsigned int extract(long num, int n, int base)
// Find the "n"th digit of "num" in base "base".
// Pretend we are using base 10 and we have a number like 12345,
// if n=2, we would get the number 4 because that is the second digit back.
// In this application, we are using base 4 to pack numbers representing
// corners of squares.  In base 4, we would count 0, 1, 2, 3, 10, 11, 12, 13
// so effectively we are pulling a digit and the digit will be from 0-3
// and we can use a simple iteration in decimal to go through all the
// combinations of corners.
{
int level=1;
long exp=base;
unsigned int ext;

//Start by finding how many digits are in the number.
//level will represent the number of digits, exp will be the base value
//of that digit.  (for example, in base 10, 3 digits would be 100.)
while ((exp*base) <= num) {level++;exp=exp*base;}

//Now iterate through the digits and extract the digit we need.
for (int idx=level; idx>=0; idx--)
    {
    if (idx == (n-1)) {ext = (num / exp);} //Found the digit, take it
    num = num - (num / exp) * exp; //reduce down by a digit
    exp=exp/base; //reduce the base value as well since we are on a new digit.
    }

return ext;
}

void squareFractal(int n)
{
    unsigned int idx;  //index for iterating through layers
    signed int dx, dy;  //direction vectors to specify corner
    unsigned int cx, cy;  //center of box to draw
    unsigned int size;  //size of box to draw  (it is a square so height & width = size)
    unsigned long int exp1, exp2;  //exponents.
    unsigned int sq, ly;  //loops: sq = individual square, ly = layer
    unsigned int ps;  //position: corner to calculate from

    exp1=1;  //how many boxes to draw for the current layer.
    for (idx=1;idx<=n;idx++) //iterate through all the layers
        {
        if (idx>1) exp1 = exp1 * 4;  //increment number of squares on this layer
        for (sq=1;sq<=exp1;sq++)  //iterate through each square on the layer
            {
            //initially start in the very center with the biggest square
            //then work backward, halving the size each time and moving
            //from corner to corner back through the layers
            cx=centerX; cy=centerY; size=startSize; exp2=1;
            for (ly=2;ly<=idx;ly++) //for each square, loop backward through layers.
                                    //if we are on layer 1, we already have the position
                                    //and size, so we don't loop.  Therefore, we start
                                    //with layer 2.
                {
                size/=2; //halve the size
                ps=extract(sq,ly-1,4); //using base 4, figure out which corner we are going
                                       //to for this layer.  See explination under Extract.
                                       //Returns a number from 0-3 representing the corner.
                switch (ps){
                case 0: //upper-left corner
                    dx=-1; dy=-1;
                    break;
                case 1: //upper-right corner
                    dx=1; dy=-1;
                    break;
                case 2: //lower-left corner
                    dx=-1; dy=1;
                    break;
                case 3: //lower-right corner
                    dx=1; dy=1;
                    break;
                }
                
                //update positions by moving backward or forward by factor of size
                cx=cx+(dx*size);
                cy=cy+(dy*size);
            }
    
            /******************************************************
            Draw box here - corner is (cx-(size/2), cy-(size-2))
            other corner is (cx+(size/2), cy+(size/2))
            height is size, width is size.
            *****************************************************/
        }
    }
}

[sirdanman10]

Here is how it works:

You start with one square at a base size and a center location. In this case, I am going to start with a size of 256x256, because that is 2^8, which means we can halve eight times and keep it a whole number.

For the center, I start at 512x512. I know I will have to scroll to see the whole thing, because that would mean the screen would have to be 1024x1024, which most screens don't have a resolution that can contain that. But this is just and example and so I don't have to deal with rounding. I calculated the center as 8!, or 2^8+2^7+2^6+2^5+2^4+2^3+2^2+2^1.

But since I was testing, I made the center 300x300 and only tested with five layers and it did fine and that is what you have above you here. (Sorry, I realized the first part of the code is not consistent with what I just explained here but I was past my half hour edit limit so I just explain here.)

For the center box, there are no dependent boxes, so I will just draw the box. Going outward gets a little trickier.

There are a few formulas:

If n is which layer we are on (1 being the center, 2 being the edges of the center, 3 being the edges of layer 2, etc.),

size = baseSize / (2 ^ (n-1)) \\ size of one box

NumSq= 4 ^ (n-1) \\ number of boxes on that layer

I am avoiding exponents in this program because C doesn't provide an exponential operator and I don't want to include <cmath.h> just for one function that I can avoid. So in the code, I am keeping a running power of 2 and power of 4 by having a variable and multiplying by 2 or multiplying by 4 on each loop.

Now, here is where the recursive part comes in:

Let's say I am working on layer 3.

We can use the size formula above to see how big one box would be, but the positioning is the real trick.

Let's say just working with the top-leftmost boxes, we know the box for layer three is the top-leftmost position of the the top-leftmost box in layer 2, which is the top-leftmost position of the box in layer 1.

We don't have to keep track of the positions of the boxes because we can derive the positions from a formula. We just have to recursively call each layer prior to find the position of the square we are hanging the new squares on.

Once we grab the position of a box from the layer before, we can draw four boxes (one on each corner).

Now this would be relatively easy if we only drew one corner... say just the top-left corner of each box, to make some sort of a line of descending thickness. To get the position of a box, we start in the center and figure out the position of the next box, then the next box, then the next box, until we get to the box we wish to draw.

But we wish to go in all four directions. The logic is the same but we need a way to tell the computer the pathway to get to the box. Because we have to go in varying paths to get to each box, we need a way to tell the system what path. For example, we want to go up-left, then up-right, then down-right, then up-right...

I could label the corners A,B,C,D and use some sort of string method to build strings like "ABACDA" or something, but that is more complicated than it needs to be.

So I label the corners of the boxes from 0 - 3, 0 being the top-left, 1 being the top-right, 2 being the bottom-left, 3 being the bottom-right. (I suppose you can swap 2 and 3 if you want to go clockwise.)

I use base 4 so each digit can only be from 0-3, and I iterate between all the numbers:

Decimal: 0 Base 4: 0

Decimal: 1 Base 4: 1

Decimal: 2 Base 4: 2

Decimal: 3 Base 4: 3

Decimal: 4 Base 4: 10

Decimal: 5 Base 4: 11
.
.
.

So now I just have to loop from 1 to how many boxes I am drawing on that layer, and call the base 4 decoder to change the number to base 4 (thus creating digits that are only 0 - 3 and conveniently cycling through all the possible pathway configurations). Since the decoder is figuring out all the digits of the base 4 number, I made the routine be able to extract one specified digit... so I can cycle through layers and take which digit I want.

So, let's say I am on layer 4 (there is already the center box plus two layers and I am building a fourth layer). I want three-digit numbers that each digit is only from 0-3. I loop from 1 to 16 (there are 16 boxes on layer 3) and send that through the extractor... then for each number (or physical box we are centering our new 4 boxes around), I get each layer one at a time, so I can follow the path and get to the box I need. Then I have my center so I calculate the positions of the boxes I am drawing and I go on to find the next box to draw around.

It seems complicated but if you really look at it, it isn't too bad.

I don't use true recursion in the form of a function calling itself... it isn't necessary, I find that for loops are sufficient.

-Dan

[sirdanman10]

By the way, to call this function, call squareFractal(n), where N is the number of layers you want. (I believe that is what you were describing N as being.)