1Math::PlanePath::SierpiUnssekriCCuornvter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::SierpinskiCurve(3)
2
3
4
6 Math::PlanePath::SierpinskiCurve -- Sierpinski curve
7
9 use Math::PlanePath::SierpinskiCurve;
10 my $path = Math::PlanePath::SierpinskiCurve->new (arms => 2);
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an integer version of the self-similar curve by Waclaw
15 Sierpinski traversing the plane by right triangles. The default is a
16 single arm of the curve in an eighth of the plane.
17
18 10 | 31-32
19 | / \
20 9 | 30 33
21 | | |
22 8 | 29 34
23 | \ /
24 7 | 25-26 28 35 37-38
25 | / \ / \ / \
26 6 | 24 27 36 39
27 | | |
28 5 | 23 20 43 40
29 | \ / \ / \ /
30 4 | 7--8 22-21 19 44 42-41 55-...
31 | / \ / \ /
32 3 | 6 9 18 45 54
33 | | | | | |
34 2 | 5 10 17 46 53
35 | \ / \ / \
36 1 | 1--2 4 11 13-14 16 47 49-50 52
37 | / \ / \ / \ / \ / \ /
38 Y=0 | . 0 3 12 15 48 51
39 |
40 +-----------------------------------------------------------
41 ^
42 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
43
44 The tiling it represents is
45
46 /
47 /|\
48 / | \
49 / | \
50 / 7| 8 \
51 / \ | / \
52 / \ | / \
53 / 6 \|/ 9 \
54 /-------|-------\
55 /|\ 5 /|\ 10 /|\
56 / | \ / | \ / | \
57 / | \ / | \ / | \
58 / 1| 2 X 4 |11 X 13|14 \
59 / \ | / \ | / \ | / \ ...
60 / \ | / \ | / \ | / \
61 / 0 \|/ 3 \|/ 12 \|/ 15 \
62 ----------------------------------
63
64 The points are on a square grid with integer X,Y. 4 points are used in
65 each 3x3 block. In general a point is used if
66
67 X%3==1 or Y%3==1 but not both
68
69 which means
70 ((X%3)+(Y%3)) % 2 == 1
71
72 The X axis N=0,3,12,15,48,etc are all the integers which use only
73 digits 0 and 3 in base 4. For example N=51 is 303 base4. Or
74 equivalently the values all have doubled bits in binary, for example
75 N=48 is 110000 binary. (Compare the "CornerReplicate" which also has
76 these values along the X axis.)
77
78 Level Ranges
79 Counting the N=0 point as level=0, and with each level being 4 copies
80 of the previous, the levels end at
81
82 Nlevel = 4^level - 1 = 0, 3, 15, ...
83 Xlevel = 3*2^level - 2 = 1, 4, 10, ...
84 Ylevel = 0
85
86 For example level=2 is Nlevel = 2^(2*2)-1 = 15 at X=3*2^2-2 = 10.
87
88 Doubling a level is the middle of the next level and is the top of the
89 triangle in that next level.
90
91 Ntop = 2*4^level - 1 = 1, 7, 31, ...
92 Xtop = 3*2^level - 1 = 2, 5, 11, ...
93 Ytop = 3*2^level - 2 = Xlevel = 1, 4, 10, ...
94
95 For example doubling level=2 is Ntop = 2*4^2-1 = 31 at X=3*2^2-1 = 11
96 and Y=3*2^2-2 = 10.
97
98 The factor of 3 arises from the three steps which make up the N=0,1,2,3
99 section. The Xlevel width grows as
100
101 Xlevel(1) = 3
102 Xlevel(level) = 2*Xwidth(level-1) + 3
103
104 which dividing out the factor of 3 is 2*w+1, giving 2^k-1 (in binary a
105 left shift and bring in a new 1 bit).
106
107 Notice too the Nlevel points as a fraction of the triangular area
108 Xlevel*(Xlevel-1)/2 gives the 4 out of 9 points filled,
109
110 FillFrac = Nlevel / (Xlevel*(Xlevel-1)/2)
111 -> 4/9
112
113 Arms
114 The optional "arms" parameter can draw multiple curves, each advancing
115 successively. For example 2 arms,
116
117 arms => 2 ...
118 |
119 11 | 33 39 57 63
120 | / \ / \ / \ /
121 10 | 31 35-37 41 55 59-61 62-...
122 | \ / \ /
123 9 | 29 43 53 60
124 | | | | |
125 8 | 27 45 51 58
126 | / \ / \
127 7 | 25 21-19 47-49 50-52 56
128 | \ / \ / \ /
129 6 | 23 17 48 54
130 | | |
131 5 | 9 15 46 40
132 | / \ / \ / \
133 4 | 7 11-13 14-16 44-42 38
134 | \ / \ /
135 3 | 5 12 18 36
136 | | | | |
137 2 | 3 10 20 34
138 | / \ / \
139 1 | 1 2--4 8 22 26-28 32
140 | / \ / \ / \ /
141 Y=0 | 0 6 24 30
142 |
143 +-----------------------------------------
144 ^
145 X=0 1 2 3 4 5 6 7 8 9 10 11
146
147 The N=0 point is at X=1,Y=0 (in all arms forms) so that the second arm
148 is within the first quadrant.
149
150 1 to 8 arms can be done this way. For example 8 arms are
151
152 arms => 8
153
154 ... ... 6
155 | |
156 58 34 33 57 5
157 \ / \ / \ /
158 ...-59 50-42 26 25 41-49 56-... 4
159 \ / \ /
160 51 18 17 48 3
161 | | | |
162 43 10 9 40 2
163 / \ / \
164 35 19-11 2 1 8-16 32 1
165 \ / \ / \ /
166 27 3 . 0 24 <- Y=0
167
168 28 4 7 31 -1
169 / \ / \ / \
170 36 20-12 5 6 15-23 39 -2
171 \ / \ /
172 44 13 14 47 -3
173 | | | |
174 52 21 22 55 -4
175 / \ / \
176 ...-60 53-45 29 30 46-54 63-... -5
177 / \ / \ / \
178 61 37 38 62 -6
179 | |
180 ... ... -7
181
182 ^
183 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6
184
185 The middle "." is the origin X=0,Y=0. It would be more symmetrical to
186 make the origin the middle of the eight arms, at X=-0.5,Y=-0.5 in the
187 above, but that would give fractional X,Y values. Apply an offset
188 X+0.5,Y+0.5 to centre it if desired.
189
190 Spacing
191 The optional "diagonal_spacing" and "straight_spacing" can increase the
192 space between points diagonally or vertically+horizontally. The
193 default for each is 1.
194
195 straight_spacing => 2
196 diagonal_spacing => 1
197
198 7 ----- 8
199 / \
200 6 9
201 | |
202 | |
203 | |
204 5 10 ...
205 \ / \
206 1 ----- 2 4 11 13 ---- 14 16
207 / \ / \ / \ /
208 0 3 12 15
209
210 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
211
212 The effect is only to spread the points. The straight lines are both
213 horizontal and vertical so when they're stretched the curve remains on
214 a 45 degree angle in an eighth of the plane.
215
216 In the level formulas above the "3" factor becomes 2*d+s, effectively
217 being the N=0 to N=3 section sized as d+s+d.
218
219 d = diagonal_spacing
220 s = straight_spacing
221
222 Xlevel = (2d+s)*(2^level - 1) + 1
223
224 Xtop = (2d+s)*2^(level-1) - d - s + 1
225 Ytop = (2d+s)*2^(level-1) - d - s
226
227 Closed Curve
228 Sierpinski's original conception was a closed curve filling a unit
229 square by ever greater self-similar detail,
230
231 /\_/\ /\_/\ /\_/\ /\_/\
232 \ / \ / \ / \ /
233 | | | | | | | |
234 / _ \_/ _ \ / _ \_/ _ \
235 \/ \ / \/ \/ \ / \/
236 | | | |
237 /\_/ _ \_/\ /\_/ _ \_/\
238 \ / \ / \ / \ /
239 | | | | | | | |
240 / _ \ / _ \_/ _ \ / _ \
241 \/ \/ \/ \ / \/ \/ \/
242 | |
243 /\_/\ /\_/ _ \_/\ /\_/\
244 \ / \ / \ / \ /
245 | | | | | | | |
246 / _ \_/ _ \ / _ \_/ _ \
247 \/ \ / \/ \/ \ / \/
248 | | | |
249 /\_/ _ \_/\ /\_/ _ \_/\
250 \ / \ / \ / \ /
251 | | | | | | | |
252 / _ \ / _ \ / _ \ / _ \
253 \/ \/ \/ \/ \/ \/ \/ \/
254
255 The code here might be pressed into use for this by drawing a mirror
256 image of the curve N=0 through Nlevel. Or using the "arms=>2" form N=0
257 to N=4^level - 1, inclusive, and joining up the ends.
258
259 The curve is also usually conceived as scaling down by quarters. This
260 can be had with "straight_spacing => 2" and then an offset to X+1,Y+1
261 to centre in a 4*2^level square
262
263 Koch Curve Midpoints
264 The replicating structure is the same as the Koch curve
265 (Math::PlanePath::KochCurve) in that the curve repeats four times to
266 make the next level.
267
268 The Sierpinski curve points are midpoints of a Koch curve of 90 degree
269 angles with a unit gap between verticals.
270
271 Koch Curve Koch Curve
272 90 degree angles, unit gap
273
274 /\ | |
275 / \ | |
276 / \ | |
277 ----- ----- ------ ------
278
279 Sierpinski curve points "*" as midpoints
280
281 | |
282 7 8
283 | |
284 ---6--- ---9---
285
286 ---5--- --10---
287 | | | | | |
288 1 2 4 11 13 14
289 | | | | | |
290 ---0--- ---3--- --12--- --15---
291
292 Koch Curve Rounded
293 The Sierpinski curve in mirror image across the X=Y diagonal and
294 rotated -45 degrees is pairs of points on the lines of the Koch curve
295 90 degree angles unit gap from above.
296
297 Sierpinski curve mirror image and turn -45 degrees
298 two points on each Koch line segment
299
300 15 16
301 | |
302 14 17
303
304 12--13 . . 18--19
305
306 11--10 . . 21--20
307
308 3 4 9 22 27 28
309 | | | | | |
310 2 5 8 23 26 29
311
312 0---1 . . 6---7 . . 24--25 . . 30--31
313
314 This is a kind of "rounded" form of the 90-degree Koch, similar what
315 "DragonRounded" does for the "DragonCurve". Each 90 turn of the Koch
316 curve is done by two turns of 45 degrees in the Sierpinski curve here,
317 and each 180 degree turn in the Koch is two 90 degree turns here. So
318 the Sierpinski turn sequence is pairs of the Koch turn sequence, as
319 follows. The mirroring means a swap left<->right between the two.
320
321 N=1 2 3 4 5 6 7 8
322 Koch L R L L L R L R ...
323
324 N=1,2 3,4 5,6 7,8 9,10 11,12 13,14 15,16
325 Sierp R R L L R R R R R R L L R R L L ...
326
328 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
329 classes.
330
331 "$path = Math::PlanePath::SierpinskiCurve->new ()"
332 "$path = Math::PlanePath::SierpinskiCurve->new (arms => $integer,
333 diagonal_spacing => $integer, straight_spacing => $integer)"
334 Create and return a new path object.
335
336 "($x,$y) = $path->n_to_xy ($n)"
337 Return the X,Y coordinates of point number $n on the path. Points
338 begin at 0 and if "$n < 0" then the return is an empty list.
339
340 Fractional positions give an X,Y position along a straight line
341 between the integer positions.
342
343 "$n = $path->n_start()"
344 Return 0, the first N in the path.
345
346 Level Methods
347 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
348 Return "(0, 4**$level - 1)", or for multiple arms return "(0, $arms
349 * 4**$level - 1)".
350
351 There are 4^level points in a level, or arms*4^level when multiple
352 arms, numbered starting from 0.
353
355 N to dX,dY
356 The curve direction at N even can be calculated from the base-4 digits
357 of N/2 in a fashion similar to the Koch curve ("N to Direction" in
358 Math::PlanePath::KochCurve). Counting direction in eighths so 0=East,
359 1=North-East, 2=North, etc,
360
361 digit direction
362 ----- ---------
363 0 0
364 1 -2
365 2 2
366 3 0
367
368 direction = 1 + sum direction[base-4 digits of N/2]
369 for N even
370
371 For example the direction at N=10 has N/2=5 which is "11" in base-4, so
372 direction = 1+(-2)+(-2) = -3 = south-west.
373
374 The 1 in 1+sum is direction north-east for N=0, then -2 or +2 for the
375 digits follow the curve. For an odd arm the curve is mirrored and the
376 sign of each digit direction is flipped, so a subtract instead of add,
377
378 direction
379 mirrored = 1 - sum direction[base-4 digits of N/2]
380 for N even
381
382 For odd N=2k+1 the direction at N=2k is calculated and then also the
383 turn which is made from N=2k to N=2(k+1). This is similar to the Koch
384 curve next turn ("N to Next Turn" in Math::PlanePath::KochCurve).
385
386 lowest non-3 next turn
387 digit of N/2 (at N=2k+1,N=2k+2)
388 ------------ ----------------
389 0 -1 (right)
390 1 +2 (left)
391 2 -1 (right)
392
393 Again the turn is in eighths, so -1 means -45 degrees (to the right).
394 For example at N=14 has N/2=7 which is "13" in base-4 so lowest non-3
395 is "1" which is turn +2, so at N=15 and N=16 turn by 90 degrees left.
396
397 direction = 1 + sum direction[base-4 digits of k]
398 + if N odd then nextturn[low-non-3 of k]
399 for N=2k or 2k+1
400
401 dX,dY = direction to 1,0 1,1 0,1 etc
402
403 For fractional N the same nextturn is applied to calculate the
404 direction of the next segment, and combined with the integer dX,dY as
405 per "N to dX,dY -- Fractional" in Math::PlanePath.
406
407 N=2k or 2k+1 + frac
408
409 direction = 1 + sum direction[base-4 digits of k]
410
411 if (frac != 0 or N odd)
412 turn = nextturn[low-non-3 of k]
413
414 if N odd then direction += turn
415 dX,dY = direction to 1,0 1,1 0,1 etc
416
417 if frac!=0 then
418 direction += turn
419 next_dX,next_dY = direction to 1,0 1,1 0,1 etc
420
421 dX += frac*(next_dX - dX)
422 dY += frac*(next_dY - dY)
423
424 For the "straight_spacing" and "diagonal_spacing" options the dX,dY
425 values are not units like dX=1,dY=0 but instead are the spacing amount,
426 either straight or diagonal so
427
428 direction delta with spacing
429 --------- -------------------------
430 0 dX=straight_spacing, dY=0
431 1 dX=diagonal_spacing, dY=diagonal_spacing
432 2 dX=0, dY=straight_spacing
433 3 dX=-diagonal_spacing, dY=diagonal_spacing
434 etc
435
436 As an alternative, it's possible to take just base-4 digits of N,
437 without separate handling for the low-bit of N, but it requires an
438 adjustment on the low base-4 digit, and the next turn calculation for
439 fractional N becomes hairier. A little state table could encode the
440 cumulative and lowest whatever if desired, to take N by base-4 digits
441 high to low, or equivalently by bits high to low with an initial state
442 based on high bit at an odd or even bit position.
443
445 The Sierpinski curve is in Sloane's Online Encyclopedia of Integer
446 Sequences as,
447
448 <http://oeis.org/A039963> (etc)
449
450 A039963 turn 1=right,0=left, doubling the KochCurve turns
451 A081706 N-1 of left turn positions
452 (first values 2,3 whereas N=3,4 here)
453 A127254 abs(dY), so 0=horizontal, 1=vertical or diagonal,
454 except extra initial 1
455 A081026 X at N=2^k, being successively 3*2^j-1, 3*2^j
456
457 A039963 is numbered starting n=0 for the first turn, which is at the
458 point N=1 in the path here.
459
461 Math::PlanePath, Math::PlanePath::SierpinskiCurveStair,
462 Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::KochCurve
463
465 <http://user42.tuxfamily.org/math-planepath/index.html>
466
468 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
469 Kevin Ryde
470
471 Math-PlanePath is free software; you can redistribute it and/or modify
472 it under the terms of the GNU General Public License as published by
473 the Free Software Foundation; either version 3, or (at your option) any
474 later version.
475
476 Math-PlanePath is distributed in the hope that it will be useful, but
477 WITHOUT ANY WARRANTY; without even the implied warranty of
478 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
479 General Public License for more details.
480
481 You should have received a copy of the GNU General Public License along
482 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
483
484
485
486perl v5.36.0 2022-07-22Math::PlanePath::SierpinskiCurve(3)