Level Ranges

Counting the N=0,1,2 part as level 1, each replication level goes from

    Nstart = 0
    Nlevel = 3^level - 1     inclusive

For example level 2 from N=0 to N=3^2-1=9. Each level doubles in size,

                 0  <= Y <= 2^level - 1
    - (2^level - 1) <= X <= 2^level - 1

The Nlevel position is alternately on the right or left,

    Xlevel = /  2^level - 1      if level even
             \  - 2^level + 1    if level odd

The Y axis ie. X=0, is crossed just after N=1,5,17,etc which is is 2/3 through the level, which is after two replications of the previous level,

    Ncross = 2/3 * 3^level - 1
           = 2 * 3^(level-1) - 1

Align Parameter

An optional "align" parameter controls how the points are arranged relative to the Y axis. The default shown above is "triangular". The choices are the same as for the "SierpinskiTriangle" path.

"right" means points to the right of the axis, packed next to each other and so using an eighth of the plane.

    align => "right"
        |   |
     7  |  26-25 19-18-17 15-14-13     
        |    /    |     |/     /       
     6  |  24    20    16    12        
        |   |   /           /          
     5  |  23 21       10-11           
        |   |/          |              
     4  |  22           9              
        |             /                
     3  |   4--5--6  8                 
        |   |     |/                   
     2  |   3     7                    
        |   |                          
     1  |   2--1                       
        |    /                         
    Y=0 |   0                          
        +--------------------------
           X=0 1  2  3  4  5  6  7

"left" is similar but skewed to the left of the Y axis, ie. into negative X.

    align => "left"
    \                         |
     26-25 19-18-17 15-14-13  |  7 
         |   \     \ |     |  |    
        24    20    16    12  |  6 
          \    |           |  |    
           23 21       10-11  |  5 
             \ |         \    |    
              22           9  |  4 
                           |  |    
                  4--5--6  8  |  3 
                   \     \ |  |    
                     3     7  |  2 
                      \       |    
                        2--1  |  1 
                           |  |    
                           0  | Y=0
    --------------------------+
     -7 -6 -5 -4 -3 -2 -1 X=0

"diagonal" puts rows on diagonals down from the Y axis to the X axis. This uses the whole of the first quadrant, with gaps.

    align => "diagonal"
        |   |                     
     7  |  26                     
        |    \                    
     6  |  24-25                  
        |   |                     
     5  |  23    19               
        |   |     |\              
     4  |  22-21-20 18            
        |             \           
     3  |   4          17         
        |   |\          |         
     2  |   3  5       16-15      
        |   |   \           \     
     1  |   2     6    10    14   
        |    \    |     |\     \  
    Y=0 |   0--1  7--8--9 11-12-13
        +--------------------------
           X=0 1  2  3  4  5  6  7

These diagonals visit all points X,Y where X and Y written in binary have no 1-bits in the same places, ie. where X bitand Y = 0. This is the same as the "SierpinskiTriangle" with align=diagonal.

Level Methods

"($n_lo, $n_hi) = $path->level_to_n_range($level)"

Return "(0, 3**$level - 1)".

N to X,Y

The align="diagonal" style is the most convenient to calculate. Each ternary digit of N becomes a bit of X and Y.

    ternary digits of N, high to low
        xbit = state_to_xbit[state+digit]
        ybit = state_to_ybit[state+digit]
        state = next_state[state+digit]

There's a total of 6 states which are the permutations of 0,1,2 in the three triangular parts. The states are in pairs as forward and reverse, but that has no particular significance. Numbering the states by "3"s allows the digit 0,1,2 to be added to make an index into tables for X,Y bit and next state.

    state=0     state=3      
    +---------+ +---------+  
    |^ 2 |    | |\ 0 |    |  
    | \  |    | | \  |    |  
    |  \ |    | |  v |    |  
    |----+----| |----+----|  
    |    |^   | |    ||   |  
    | 0  || 1 | | 0  || 1 |  
    |--->||   | |<---|v   |  
    +---------+ +---------+  
    state=6      state=9     
    +---------+  +---------+ 
    |    |    |  |    |    | 
    | 1  |    |  | 1  |    | 
    |--->|    |  |<---|    | 
    |----+----|  |----+----| 
    |^   |\ 2 |  ||   |^   | 
    ||0  | \  |  || 2 | \0 | 
    ||   |  v |  |v   |  \ | 
    +---------+  +---------+ 
    state=12     state=15    
    +---------+  +---------+ 
    || 0 |    |  |^   |    | 
    ||   |    |  || 2 |    | 
    |v   |    |  ||   |    | 
    |----+----|  |----+----| 
    |\ 1 |    |  |^ 1 |    | 
    | \  | 2  |  | \  |  0 | 
    |  v |--->|  |  \ |<---| 
    +---------+  +---------+

The initial state is 0 if an even number of ternary digits, or 6 if odd. In the samples above it can be seen for example that N=0 to N=8 goes upwards as per state 0, whereas N=0 to N=2 goes across as per state 6.

Having calculated an X,Y in align="diagonal" style it can be mapped to the other alignments by

    align        coordinates from diagonal X,Y
    -----        -----------------------------
    triangular      X-Y, X+Y
    right           X, X+Y
    left            -Y, X+Y

N to dX,dY

For fractional N the direction of the curve towards the N+1 point can be found from the least significant digit 0 or 1 (ie. a non-2 digit) and the state at that point.

This works because if the least significant ternary digit of N is a 2 then the direction of the curve is determined by the next level up, and so on for all trailing 2s until reaching a non-2 digit.

If N is all 2s then the direction should be reckoned from an initial 0 digit above them, which means the opposite 6 or 0 of the initial state.

Rectangle to N Range

An easy over-estimate of the range can be had from inverting the Nlevel formulas in "Level Ranges" above.

    level = floor(log2(Ymax)) + 1
    Nmax = 3^level - 1

For example Y=5, level=floor(log2(11))+1=3, so Nmax=3^3-1=26, which is the left end of the Y=7 row, ie. rounded up to the end of the Y=4 to Y=7 replication.