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

NAME

       Math::PlanePath::SierpinskiCurve -- Sierpinski curve

SYNOPSIS

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

DESCRIPTION

       This is an integer version of the self-similar curve by Waclaw Sierpinski traversing the
       plane by right triangles.  The default is a single arm of the curve in an eighth of the
       plane.

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

       The tiling it represents is

                           /
                          /|\
                         / | \
                        /  |  \
                       /  7| 8 \
                      / \  |  / \
                     /   \ | /   \
                    /  6  \|/  9  \
                   /-------|-------\
                  /|\  5  /|\ 10  /|\
                 / | \   / | \   / | \
                /  |  \ /  |  \ /  |  \
               /  1| 2 X 4 |11 X 13|14 \
              / \  |  / \  |  / \  |  / \ ...
             /   \ | /   \ | /   \ | /   \
            /  0  \|/  3  \|/  12 \|/  15 \
           ----------------------------------

       The points are on a square grid with integer X,Y.  4 points are used in each 3x3 block.
       In general a point is used if

           X%3==1 or Y%3==1 but not both

           which means
           ((X%3)+(Y%3)) % 2 == 1

       The X axis N=0,3,12,15,48,etc are all the integers which use only digits 0 and 3 in base
       4.  For example N=51 is 303 base4.  Or equivalently the values all have doubled bits in
       binary, for example N=48 is 110000 binary.  (Compare the "CornerReplicate" which also has
       these values along the X axis.)

   Level Ranges
       Counting the N=0 to N=3 as level=1, N=0 to N=15 as level 2, etc, the end of each level,
       back at the X axis, is

           Nlevel = 4^level - 1
           Xlevel = 3*2^level - 2
           Ylevel = 0

       For example level=2 is Nend = 2^(2*2)-1 = 15 at X=3*2^2-2 = 10.

       The top of each level is half way along,

           Ntop = (4^level)/2 - 1
           Xtop = 3*2^(level-1) - 1
           Ytop = 3*2^(level-1) - 2

       For example level=3 is Ntop = 2^(2*3-1)-1 = 31 at X=3*2^(3-1)-1 = 11 and Y=3*2^(3-1)-2 =
       10.

       The factor of 3 arises from the three steps which make up the N=0,1,2,3 section.  The
       Xlevel width grows as

           Xlevel(1) = 3
           Xlevel(level+1) = 2*Xwidth(level) + 3

       which dividing out the factor of 3 is 2*w+1, given 2^k-1 (in binary a left shift and bring
       in a new 1 bit, giving 2^k-1).

       Notice too the Nlevel points as a fraction of the triangular area Xlevel*(Xlevel-1)/2
       gives the 4 out of 9 points filled,

           FillFrac = Nlevel / (Xlevel*(Xlevel-1)/2)
                   -> 4/9

   Arms
       The optional "arms" parameter can draw multiple curves, each advancing successively.  For
       example "arms => 2",

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

            ^
           X=0 1  2  3  4  5  6  7  8  9 10 11

       The N=0 point is at X=1,Y=0 (in all arms forms) so that the second arm is within the first
       quadrant.

       1 to 8 arms can be done this way.  "arms=>8" is as follows.

                  ...                       ...           6
                   |                          |
                  58       34       33       57           5
                    \     /  \     /  \     /
           ...-59    50-42    26 25    41-49    56-...    4
                 \           /     \           /
                  51       18       17       48           3
                   |        |        |        |
                  43       10        9       40           2
                 /           \     /           \
               35    19-11     2  1     8-16    32        1
                 \  /     \           /     \  /
                  27        3     .  0       24       <- Y=0

                  28        4        7       31          -1
                 /  \     /           \     /  \
               36    20-12     5  6    15-23    39       -2
                 \           /     \           /
                  44       13       14       47          -3
                   |        |        |        |
                  52       21       22       55          -4
                 /           \     /           \
           ...-60    53-45    29 30    46-54    63-...   -5
                    /     \  /     \  /     \
                  61       37       38       62          -6
                   |                          |
                  ...                       ...          -7

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

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

   Spacing
       The optional "diagonal_spacing" and "straight_spacing" can increase the space between
       points diagonally or vertically+horizontally.  The default for each is 1.

           straight_spacing => 2
           diagonal_spacing => 1

                               7 ----- 8
                            /           \
                           6               9
                           |               |
                           |               |
                           |               |
                           5              10              ...
                            \           /                   \
               1 ----- 2       4      11      13 ---- 14      16
            /           \   /           \   /           \   /
           0               3              12              15

          X=0  1   2   3   4   5   6   7   8   9  10  11  12  13 ...

       The effect is only to spread the points.  In the level formulas above the "3" factor
       becomes 2*d+s, effectively being the N=0 to N=3 section sized as d+s+d.

           d = diagonal_spacing
           s = straight_spacing

           Xlevel = (2d+s)*(2^level - 1)  + 1

           Xtop = (2d+s)*2^(level-1) - d - s + 1
           Ytop = (2d+s)*2^(level-1) - d - s

   Closed Curve
       Sierpinski's original conception was a closed curve filling a unit square by ever greater
       self-similar detail,

           /\_/\ /\_/\ /\_/\ /\_/\
           \   / \   / \   / \   /
            | |   | |   | |   | |
           / _ \_/ _ \ / _ \_/ _ \
           \/ \   / \/ \/ \   / \/
              |  |         | |
           /\_/ _ \_/\ /\_/ _ \_/\
           \   / \   / \   / \   /
            | |   | |   | |   | |
           / _ \ / _ \_/ _ \ / _ \
           \/ \/ \/ \   / \/ \/ \/
                     | |
           /\_/\ /\_/ _ \_/\ /\_/\
           \   / \   / \   / \   /
            | |   | |   | |   | |
           / _ \_/ _ \ / _ \_/ _ \
           \/ \   / \/ \/ \   / \/
              |  |         | |
           /\_/ _ \_/\ /\_/ _ \_/\
           \   / \   / \   / \   /
            | |   | |   | |   | |
           / _ \ / _ \ / _ \ / _ \
           \/ \/ \/ \/ \/ \/ \/ \/

       The code here might be pressed into use for this by drawing a mirror image of the curve
       N=0 through Nlevel (above).  Or using the "arms=>2" form N=0 to N=4^level, inclusive, and
       joining up the ends.

       The curve is also usually conceived as scaling down by quarters.  This can be had with
       "straight_spacing => 2" and then an offset to X+1,Y+1 to centre in a 4*2^level square

   Koch Curve
       The replicating structure is the same as the Koch curve (Math::PlanePath::KochCurve), in
       that the curve repeats four times to make the next level,

           Koch Curve           Sierpinski Curve
                                 (mirror image)

                                      | |
                / \                   | |
               /   \                  | |
           ---       ---           ---   ---

       The turns in the Sierpinski curve are by 90 degrees and 180 degrees, done in two steps
       45+45=90 when turning right or 90+90=180 when turning left.

       The turn sequence left or right is the same as the Koch curve ("N to Turn" in
       Math::PlanePath::KochCurve) except the Sierpinski curve makes each turn in two steps, and
       mirrored to swap L<->R.  For example the Koch curve starts with Left at N=1 which for the
       Sierpinski curve becomes two turns Right,Right at N=1,N=2.

                  N=1    2    3    4    5     6      7      8
           Koch     L    R    L    L    L     R      L      R     ...

                  N=1,2  3,4  5,6  7,8  9,10  11,12  13,14  15,16
           Sierp    R R  L L  R R  R R  R R   L  L   R  R   L  L  ...

FUNCTIONS

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

       "$path = Math::PlanePath::SierpinskiCurve->new ()"
       "$path = Math::PlanePath::SierpinskiCurve->new (arms => $integer, diagonal_spacing =>
       $integer, straight_spacing => $integer)"
           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.

FORMULAS

   N to dX,dY
       The curve direction at an even N can be calculated from the base-4 digits of N/2 in a
       fashion similar to the Koch curve ("N to Direction" in Math::PlanePath::KochCurve).
       Counting direction in eighths so 0=east, 1=north-east, 2=north, etc,

           digit     direction
           -----     ---------
             0           0
             1          -2
             2           2
             3           0

           direction = 1 + sum direction[base-4 digits of N/2]

       For example the direction at N=10 has N/2=5 which is "11" in base-4, so direction =
       1+(-2)+(-2) = -3 = south-west.

       The 1 in 1+sum is direction north-east for N=0, then -2 or +2 for the digits follow the
       curve.  For an odd arm the curve is mirrored and the sign of each digit direction is
       flipped, so a subtract instead of add,

           direction
           mirrored  = 1 - sum direction[base-4 digits of N/2]

       For odd N=2k+1 the direction at N=2k is calculated and then also the turn which is made
       from N=2k to N=2(k+1).  This is similar to the Koch curve next turn ("N to Next Turn" in
       Math::PlanePath::KochCurve).

          lowest non-3     next turn
          digit of N/2   (at N=2k+1,N=2k+2)
          ------------   ----------------
               0           -1 (right)
               1           +2 (left)
               2           -1 (right)

       Again the turn is in eighths, so -1 means -45 degrees (to the right).  For example at N=14
       has N/2=7 which is "13" in base-4 so lowest non-3 is "1" which is turn +2, so at N=15 and
       N=16 turn by 90 degrees left.

          N=2k or 2k+1

          direction = 1 + sum direction[base-4 digits of k]
                        + if N odd then nextturn[low-non-3 of k]

          dX,dY = direction to 1,0 1,1 0,1 etc

       For fractional N the same nextturn is applied to calculate the direction of the next
       segment, and combined with the integer dX,dY as per "N to dX,dY -- Fractional" in
       Math::PlanePath.

          N=2k or 2k+1 + frac

          direction = 1 + sum direction[base-4 digits of k]

          if (frac != 0 or N odd)
            turn = nextturn[low-non-3 of k]

          if N odd then direction += turn
          dX,dY = direction to 1,0 1,1 0,1 etc

          if frac!=0 then
            direction += turn
            next_dX,next_dY = direction to 1,0 1,1 0,1 etc

            dX += frac*(next_dX - dX)
            dY += frac*(next_dY - dY)

       For the "straight_spacing" and "diagonal_spacing" options the dX,dY values are not units
       like dX=1,dY=0 but instead are the spacing amount, either straight or diagonal so

           direction      delta with spacing
           ---------    -------------------------
               0        dX=straight_spacing, dY=0
               1        dX=diagonal_spacing, dY=diagonal_spacing
               2        dX=0, dY=straight_spacing
               3        dX=-diagonal_spacing, dY=diagonal_spacing
              etc

       As an alternative, it's possible to take just base-4 digits of N, without separate
       handling for the low-bit of N, but it requires an adjustment for on the low base-4 digit,
       and the next turn calculation for fractional N becomes hairier.  A little state table
       could no doubt encode the cumulative and lowest whatever if desired, to take N by base-4
       digits high to low, or equivalently by bits high to low with an initial state based on
       high bit at an odd or even bit position.

OEIS

       The Sierpinski curve is in Sloane's Online Encyclopedia of Integer Sequences as,

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

           A039963   turn 1=right,0=left, doubling the KochCurve turns
           A081706   N-1 of left turn positions
                      (first values 2,3 whereas N=3,4 here)
           A127254   abs(dY), so 0=horizontal, 1=vertical or diagonal,
                       except extra initial 1
           A081026   X at N=2^k, being successively 3*2^j-1, 3*2^j

       A039963 is numbered starting n=0 for the first turn, which is at the point N=1 in the path
       here.

SEE ALSO

       Math::PlanePath, Math::PlanePath::SierpinskiCurveStair,
       Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::KochCurve

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013 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/>.