Kevin Ryde > Math-PlanePath > Math::PlanePath::SierpinskiCurve

Download:
Math-PlanePath-116.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

Open  2
View/Report Bugs
Module Version: 116   Source  

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, 2014 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/>.

syntax highlighting: