Math::PlanePath::SierpinskiCurveStair -- Sierpinski curve with stair-step diagonals
use Math::PlanePath::SierpinskiCurveStair; my $path = Math::PlanePath::SierpinskiCurveStair->new (arms => 2); my ($x, $y) = $path->n_to_xy (123);
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.
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.
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.
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)
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.
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.
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.
($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.
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
Math::PlanePath, Math::PlanePath::SierpinskiCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012, 2013, 2014, 2015 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/>.