Kevin Ryde > Math-PlanePath > Math::PlanePath::SierpinskiCurveStair

Download:
Math-PlanePath-117.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

Open  1
View/Report Bugs
Module Version: 117   Source  

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 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: