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 16The 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 == 1The 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 base 4. 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 = 0For 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) - 2For 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) + 3which 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/9Arms
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 11The N=0 point is at X=1,Y=0 (in all arms forms) so that the second arm is within the first quadrant.
Anywhere between 1 and 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 6The 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 as X+0.5,Y+0.5 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.
$path = Math::PlanePath::SierpinskiCurve->new
(straight_spacing => 2,
(diagonal_spacing => 1)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 being 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 - sClosed 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 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
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::SierpinskiCurve->new ()$path = Math::PlanePath::SierpinskiCurve->new (arms => 8)-
Create and return a new path object.
($x,$y) = $path->n_to_xy ($n)-
Return the X,Y coordinates of point number
$non the path. Points begin at 0 and if$n < 0then 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.
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
A127254 abs(dY), so 0=horizontal 1=diagonal or vertical,
except extra initial 1A039963 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 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/>.