Provided by: libmath-planepath-perl_129-1_all bug

NAME

       Math::PlanePath::SierpinskiCurveStair -- Sierpinski curve with stair-step diagonals

SYNOPSIS

        use Math::PlanePath::SierpinskiCurveStair;
        my $path = Math::PlanePath::SierpinskiCurveStair->new (arms => 2);
        my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

       This is a variation on the "SierpinskiCurve" with stair-step diagonal parts.

           10  |                                  52-53
               |                                   |  |
            9  |                               50-51 54-55
               |                                |        |
            8  |                               49-48 57-56
               |                                   |  |
            7  |                         42-43 46-47 58-59 62-63
               |                          |  |  |        |  |  |
            6  |                      40-41 44-45       60-61 64-65
               |                       |                          |
            5  |                      39-38 35-34       71-70 67-66
               |                          |  |  |        |  |  |
            4  |                12-13    37-36 33-32 73-72 69-68    92-93
               |                 |  |              |  |              |  |
            3  |             10-11 14-15       30-31 74-75       90-91 94-95
               |              |        |        |        |        |        |
            2  |              9--8 17-16       29-28 77-76       89-88 97-96
               |                 |  |              |  |              |  |
            1  |        2--3  6--7 18-19 22-23 26-27 78-79 82-83 86-87 98-99
               |        |  |  |        |  |  |  |        |  |  |  |        |
           Y=0 |     0--1  4--5       20-21 24-25       80-81 84-85       ...
               |
               +-------------------------------------------------------------
                  ^
                 X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

       The tiling is the same as the "SierpinskiCurve", but each diagonal is a stair step
       horizontal and vertical.  The correspondence is

           SierpinskiCurve        SierpinskiCurveStair

                       7--                   12--
                     /                        |
                    6                     10-11
                    |                      |
                    5                      9--8
                     \                        |
              1--2     4             2--3  6--7
            /     \  /               |  |  |
           0        3             0--1  4--5

       The "SierpinskiCurve" N=0 to N=3 corresponds to N=0 to N=5 here.  N=7 to N=12 which is a
       copy of the N=0 to N=5 base.  Point N=6 is an extra in between the parts.  The next such
       extra is N=19.

   Diagonal Length
       The "diagonal_length" option can make longer diagonals, still in stair-step style.  For
       example

                    diagonal_length => 4
           10  |                                 36-37
               |                                  |  |
            9  |                              34-35 38-39
               |                               |        |
            8  |                           32-33       40-41
               |                            |              |
            7  |                        30-31             42-43
               |                         |                    |
            6  |                     28-29                   44-45
               |                      |                          |
            5  |                     27-26                   47-46
               |                         |                    |
            4  |                8--9    25-24             49-48    ...
               |                |  |        |              |        |
            3  |             6--7 10-11    23-22       51-50    62-63
               |             |        |        |        |        |
            2  |          4--5       12-13    21-20 53-52    60-61
               |          |              |        |  |        |
            1  |       2--3             14-15 18-19 54-55 58-59
               |       |                    |  |        |  |
           Y=0 |    0--1                   16-17       56-57
               |
               +------------------------------------------------------
                 ^
                X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17

       The length is reckoned from N=0 to the end of the first side N=8, which is X=1 to X=5 for
       length 4 units.

   Arms
       The optional "arms" parameter can give up to eight copies of the curve, each advancing
       successively.  For example

           arms => 8

              98-90 66-58       57-65 89-97            5
                  |  |  |        |  |  |
           99    82-74 50-42 41-49 73-81    96         4
            |              |  |              |
           91-83       26-34 33-25       80-88         3
               |        |        |        |
           67-75       18-10  9-17       72-64         2
            |              |  |              |
           59-51 27-19     2  1    16-24 48-56         1
               |  |  |              |  |  |
              43-35 11--3     .  0--8 32-40       <- Y=0

              44-36 12--4        7-15 39-47           -1
               |  |  |              |  |  |
           60-52 28-20     5  6    23-31 55-63        -2
            |              |  |              |
           68-76       21-13 14-22       79-71        -3
               |        |        |        |
           92-84       29-37 38-30       87-95        -4
                           |  |
                 85-77 53-45 46-54 78-86              -5
                  |  |  |        |  |  |
                 93 69-61       62-70 94              -6

                              ^
           -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6

       The multiples of 8 (or however many arms) N=0,8,16,etc is the original curve, and the
       further mod 8 parts are the copies.

       The middle "." shown is the origin X=0,Y=0.  It would be more symmetrical to have the
       origin the middle of the eight arms, which would be X=-0.5,Y=-0.5 in the above, but that
       would give fractional X,Y values.  Apply an offset X+0.5,Y+0.5 to centre if desired.

   Level Ranges
       The N=0 point is reckoned as level=0, then N=0 to N=5 inclusive is level=1, etc.  Each
       level is 4 copies of the previous and an extra 2 points between.

           LevelPoints[k] = 4*LevelPoints[k-1] + 2   starting LevelPoints[0]=1
                          = 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + 1*4^k
                          = (5*4^k - 2)/3

           Nlevel[k] = LevelPoints[k] - 1         since starting at N=0
                     = 5*(4^k - 1)/3
                     = 0, 5, 25, 105, 425, 1705, 6825, 27305, ...    (A146882)

       The width along the X axis of a level doubles each time, plus an extra distance 3 between.

           LevelWidth[k] = 2*LevelWidth[k-1] + 3     starting LevelWidth[0]=0
                         = 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + 0*2^k
                         = 3*(2^k - 1)

           Xlevel[k] = 1 + LevelWidth[k]
                     = 3*2^k - 2
                     = 1, 4, 10, 22, 46, 94, 190, 382, ...           (A033484)

   Level Ranges with Diagonal Length
       With "diagonal_length" = L, level=0 is reckoned as having L many points instead of just 1.

           LevelPoints[k] = 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + L*4^k
                          = ( (3L+2)*4^k - 2 )/3

           Nlevel[k] = LevelPoints[k] - 1
                     = ( (3L+2)*4^k - 5 )/3

       The width of level=0 becomes L-1 instead of 0.

           LevelWidth[k] = 2*LevelWidth[k-1] + 3     starting LevelWidth[0]=L-1
                         = 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + (L-1)*2^k
                         = (L+2)*2^k - 3

           Xlevel[k] = 1 + LevelWidth[k]
                     = (L+2)*2^k - 2

       Level=0 as L many points can be thought of as a little block which is replicated in mirror
       image to make level=1.  For example the diagonal 4 example above becomes

                       8  9            diagonal_length => 4
                       |  |
                    6--7 10-11
                    |        |
                 .  5       12  .

              2--3             14-15
              |                    |
           0--1                   16-17

       The spacing between the parts is had in the tiling by taking a margin of 1/2 at the base
       and 1 horizontally left and right.

   Level Fill
       The curve doesn't visit all the points in the eighth of the plane below the X=Y diagonal.
       In general Nlevel+1 many points of the triangular area Xlevel^2/4 are visited, for a
       filled fraction which approaches a constant

                         Nlevel          4*(3L+2)
           FillFrac = ------------   ->  ---------
                      Xlevel^2 / 4       3*(L+2)^2

       For example the default L=1 has FillFrac=20/27=0.74.  Or L=2 FillFrac=2/3=0.66.  As the
       diagonal length increases the fraction decreases due to the growing holes in the pattern.

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

       "$path = Math::PlanePath::SierpinskiCurveStair->new ()"
       "$path = Math::PlanePath::SierpinskiCurveStair->new (diagonal_length => $L, arms => $A)"
           Create and return a new path object.

       "($x,$y) = $path->n_to_xy ($n)"
           Return the X,Y coordinates of point number $n on the path.  Points begin at 0 and if
           "$n < 0" then the return is an empty list.

           Fractional positions give an X,Y position along a straight line between the integer
           positions.

       "$n = $path->n_start()"
           Return 0, the first N in the path.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, ((3*$diagonal_length +2) * 4**$level - 5)/3" as per "Level Ranges with
           Diagonal Length" above.

OEIS

       Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

           <http://oeis.org/A146882> (etc)

           A146882   Nlevel, for level=1 up
           A033484   Xmax and Ymax in level, being 3*2^n - 2

SEE ALSO

       Math::PlanePath, Math::PlanePath::SierpinskiCurve

HOME PAGE

       <http://user42.tuxfamily.org/math-planepath/index.html>

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

       Math-PlanePath is free software; you can redistribute it and/or modify it under the terms
       of the GNU General Public License as published by the Free Software Foundation; either
       version 3, or (at your option) any later version.

       Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY
       WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
       PURPOSE.  See the GNU General Public License for more details.

       You should have received a copy of the GNU General Public License along with Math-
       PlanePath.  If not, see <http://www.gnu.org/licenses/>.