1Math::PlanePath::SierpiUnssekriCCuornvterSitbauitre(d3M)Paetrhl::DPolcaunmeePnattaht:i:oSnierpinskiCurveStair(3)
2
6 Math::PlanePath::SierpinskiCurveStair -- Sierpinski curve with
7 stair-step diagonals
8
10 use Math::PlanePath::SierpinskiCurveStair;
11 my $path = Math::PlanePath::SierpinskiCurveStair->new (arms => 2);
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This is a variation on the "SierpinskiCurve" with stair-step diagonal
16 parts.
17 10 | 52-53
19 | | |
20 9 | 50-51 54-55
21 | | |
22 8 | 49-48 57-56
23 | | |
24 7 | 42-43 46-47 58-59 62-63
25 | | | | | | |
26 6 | 40-41 44-45 60-61 64-65
27 | | |
28 5 | 39-38 35-34 71-70 67-66
29 | | | | | | |
30 4 | 12-13 37-36 33-32 73-72 69-68 92-93
31 | | | | | | |
32 3 | 10-11 14-15 30-31 74-75 90-91 94-95
33 | | | | | | |
34 2 | 9--8 17-16 29-28 77-76 89-88 97-96
35 | | | | | | |
36 1 | 2--3 6--7 18-19 22-23 26-27 78-79 82-83 86-87 98-99
37 | | | | | | | | | | | | |
38 Y=0 | 0--1 4--5 20-21 24-25 80-81 84-85 ...
39 |
40 +-------------------------------------------------------------
41 ^
42 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
43 The tiling is the same as the "SierpinskiCurve", but each diagonal is a
45 stair step horizontal and vertical. The correspondence is
46 SierpinskiCurve SierpinskiCurveStair
48 7-- 12--
50 / |
51 6 10-11
52 | |
53 5 9--8
54 \ |
55 1--2 4 2--3 6--7
56 / \ / | | |
57 0 3 0--1 4--5
58 The "SierpinskiCurve" N=0 to N=3 corresponds to N=0 to N=5 here. N=7
60 to N=12 which is a copy of the N=0 to N=5 base. Point N=6 is an extra
61 in between the parts. The next such extra is N=19.
62 Diagonal Length
64 The "diagonal_length" option can make longer diagonals, still in stair-
65 step style. For example
66 diagonal_length => 4
68 10 | 36-37
69 | | |
70 9 | 34-35 38-39
71 | | |
72 8 | 32-33 40-41
73 | | |
74 7 | 30-31 42-43
75 | | |
76 6 | 28-29 44-45
77 | | |
78 5 | 27-26 47-46
79 | | |
80 4 | 8--9 25-24 49-48 ...
81 | | | | | |
82 3 | 6--7 10-11 23-22 51-50 62-63
83 | | | | | |
84 2 | 4--5 12-13 21-20 53-52 60-61
85 | | | | | |
86 1 | 2--3 14-15 18-19 54-55 58-59
87 | | | | | |
88 Y=0 | 0--1 16-17 56-57
89 |
90 +------------------------------------------------------
91 ^
92 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
93 The length is reckoned from N=0 to the end of the first side N=8, which
95 is X=1 to X=5 for length 4 units.
96 Arms
98 The optional "arms" parameter can give up to eight copies of the curve,
99 each advancing successively. For example
100 arms => 8
102 98-90 66-58 57-65 89-97 5
104 | | | | | |
105 99 82-74 50-42 41-49 73-81 96 4
106 | | | |
107 91-83 26-34 33-25 80-88 3
108 | | | |
109 67-75 18-10 9-17 72-64 2
110 | | | |
111 59-51 27-19 2 1 16-24 48-56 1
112 | | | | | |
113 43-35 11--3 . 0--8 32-40 <- Y=0
114 44-36 12--4 7-15 39-47 -1
116 | | | | | |
117 60-52 28-20 5 6 23-31 55-63 -2
118 | | | |
119 68-76 21-13 14-22 79-71 -3
120 | | | |
121 92-84 29-37 38-30 87-95 -4
122 | |
123 85-77 53-45 46-54 78-86 -5
124 | | | | | |
125 93 69-61 62-70 94 -6
126 ^
128 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6
129 The multiples of 8 (or however many arms) N=0,8,16,etc is the original
131 curve, and the further mod 8 parts are the copies.
132 The middle "." shown is the origin X=0,Y=0. It would be more
134 symmetrical to have the origin the middle of the eight arms, which
135 would be X=-0.5,Y=-0.5 in the above, but that would give fractional X,Y
136 values. Apply an offset X+0.5,Y+0.5 to centre if desired.
137 Level Ranges
139 The N=0 point is reckoned as level=0, then N=0 to N=5 inclusive is
140 level=1, etc. Each level is 4 copies of the previous and an extra 2
141 points between.
142 LevelPoints[k] = 4*LevelPoints[k-1] + 2 starting LevelPoints[0]=1
144 = 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + 1*4^k
145 = (5*4^k - 2)/3
146 Nlevel[k] = LevelPoints[k] - 1 since starting at N=0
148 = 5*(4^k - 1)/3
149 = 0, 5, 25, 105, 425, 1705, 6825, 27305, ... (A146882)
150 The width along the X axis of a level doubles each time, plus an extra
152 distance 3 between.
153 LevelWidth[k] = 2*LevelWidth[k-1] + 3 starting LevelWidth[0]=0
155 = 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + 0*2^k
156 = 3*(2^k - 1)
157 Xlevel[k] = 1 + LevelWidth[k]
159 = 3*2^k - 2
160 = 1, 4, 10, 22, 46, 94, 190, 382, ... (A033484)
161 Level Ranges with Diagonal Length
163 With "diagonal_length" = L, level=0 is reckoned as having L many points
164 instead of just 1.
165 LevelPoints[k] = 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + L*4^k
167 = ( (3L+2)*4^k - 2 )/3
168 Nlevel[k] = LevelPoints[k] - 1
170 = ( (3L+2)*4^k - 5 )/3
171 The width of level=0 becomes L-1 instead of 0.
173 LevelWidth[k] = 2*LevelWidth[k-1] + 3 starting LevelWidth[0]=L-1
175 = 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + (L-1)*2^k
176 = (L+2)*2^k - 3
177 Xlevel[k] = 1 + LevelWidth[k]
179 = (L+2)*2^k - 2
180 Level=0 as L many points can be thought of as a little block which is
182 replicated in mirror image to make level=1. For example the diagonal 4
183 example above becomes
184 8 9 diagonal_length => 4
186 | |
187 6--7 10-11
188 | |
189 . 5 12 .
190 2--3 14-15
192 | |
193 0--1 16-17
194 The spacing between the parts is had in the tiling by taking a margin
196 of 1/2 at the base and 1 horizontally left and right.
197 Level Fill
199 The curve doesn't visit all the points in the eighth of the plane below
200 the X=Y diagonal. In general Nlevel+1 many points of the triangular
201 area Xlevel^2/4 are visited, for a filled fraction which approaches a
202 constant
203 Nlevel 4*(3L+2)
205 FillFrac = ------------ -> ---------
206 Xlevel^2 / 4 3*(L+2)^2
207 For example the default L=1 has FillFrac=20/27=0.74. Or L=2
209 FillFrac=2/3=0.66. As the diagonal length increases the fraction
210 decreases due to the growing holes in the pattern.
211
213 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
214 classes.
215 "$path = Math::PlanePath::SierpinskiCurveStair->new ()"
217 "$path = Math::PlanePath::SierpinskiCurveStair->new (diagonal_length =>
218 $L, arms => $A)"
219 Create and return a new path object.
220 "($x,$y) = $path->n_to_xy ($n)"
222 Return the X,Y coordinates of point number $n on the path. Points
223 begin at 0 and if "$n < 0" then the return is an empty list.
224 Fractional positions give an X,Y position along a straight line
226 between the integer positions.
227 "$n = $path->n_start()"
229 Return 0, the first N in the path.
230 Level Methods
232 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
233 Return "(0, ((3*$diagonal_length +2) * 4**$level - 5)/3" as per
234 "Level Ranges with Diagonal Length" above.
235
237 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
238 this path include
239 <http://oeis.org/A146882> (etc)
241 A146882 Nlevel, for level=1 up
243 A033484 Xmax and Ymax in level, being 3*2^n - 2
244
246 Math::PlanePath, Math::PlanePath::SierpinskiCurve
247
249 <http://user42.tuxfamily.org/math-planepath/index.html>
250
252 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
253 Kevin Ryde
254 Math-PlanePath is free software; you can redistribute it and/or modify
256 it under the terms of the GNU General Public License as published by
257 the Free Software Foundation; either version 3, or (at your option) any
258 later version.
259 Math-PlanePath is distributed in the hope that it will be useful, but
261 WITHOUT ANY WARRANTY; without even the implied warranty of
262 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
263 General Public License for more details.
264 You should have received a copy of the GNU General Public License along
266 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
267perl v5.36.0 2022-M0a7t-h2:2:PlanePath::SierpinskiCurveStair(3)