Math::PlanePath::SierpinskiCurve -- Sierpinski curve
use Math::PlanePath::SierpinskiCurve; my $path = Math::PlanePath::SierpinskiCurve->new (arms => 2); my ($x, $y) = $path->n_to_xy (123);
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 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.)
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
The optional arms parameter can draw multiple curves, each advancing successively. For example arms => 2,
arms
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.
Anywhere between 1 and 8 arms can be done this way. arms=>8 is as follows.
arms=>8
... ... 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 as X+0.5,Y+0.5 if desired.
The optional diagonal_spacing and straight_spacing can increase the space between points diagonally or vertically/horizontally. The default for each is 1.
diagonal_spacing
straight_spacing
$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 - s
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.
arms=>2
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
straight_spacing => 2
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 $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.
$n
$n < 0
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.
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 1
A039963 is numbered starting n=0 for the first turn, which is at the point N=1 in the path here.
Math::PlanePath, Math::PlanePath::SierpinskiCurveStair, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::KochCurve
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.