1Math::PlanePath::SierpiUnssekriCCuornvter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::SierpinskiCurve(3)
2
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 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 The tiling it represents is
45 /
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 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 X%3==1 or Y%3==1 but not both
68 which means
70 ((X%3)+(Y%3)) % 2 == 1
71 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 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 Nlevel = 4^level - 1 = 0, 3, 15, ...
83 Xlevel = 3*2^level - 2 = 1, 4, 10, ...
84 Ylevel = 0
85 For example level=2 is Nlevel = 2^(2*2)-1 = 15 at X=3*2^2-2 = 10.
87 Doubling a level is the middle of the next level and is the top of the
89 triangle in that next level.
90 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 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 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 Xlevel(1) = 3
102 Xlevel(level) = 2*Xwidth(level-1) + 3
103 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 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 FillFrac = Nlevel / (Xlevel*(Xlevel-1)/2)
111 -> 4/9
112 Arms
114 The optional "arms" parameter can draw multiple curves, each advancing
115 successively. For example 2 arms,
116 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 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 1 to 8 arms can be done this way. For example 8 arms are
151 arms => 8
153 ... ... 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 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 ^
183 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6
184 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 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 straight_spacing => 2
196 diagonal_spacing => 1
197 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 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
211 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 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 d = diagonal_spacing
220 s = straight_spacing
221 Xlevel = (2d+s)*(2^level - 1) + 1
223 Xtop = (2d+s)*2^(level-1) - d - s + 1
225 Ytop = (2d+s)*2^(level-1) - d - s
226 Closed Curve
228 Sierpinski's original conception was a closed curve filling a unit
229 square by ever greater self-similar detail,
230 /\_/\ /\_/\ /\_/\ /\_/\
232 \ / \ / \ / \ /
233 | | | | | | | |
234 / _ \_/ _ \ / _ \_/ _ \
235 \/ \ / \/ \/ \ / \/
236 | | | |
237 /\_/ _ \_/\ /\_/ _ \_/\
238 \ / \ / \ / \ /
239 | | | | | | | |
240 / _ \ / _ \_/ _ \ / _ \
241 \/ \/ \/ \ / \/ \/ \/
242 | |
243 /\_/\ /\_/ _ \_/\ /\_/\
244 \ / \ / \ / \ /
245 | | | | | | | |
246 / _ \_/ _ \ / _ \_/ _ \
247 \/ \ / \/ \/ \ / \/
248 | | | |
249 /\_/ _ \_/\ /\_/ _ \_/\
250 \ / \ / \ / \ /
251 | | | | | | | |
252 / _ \ / _ \ / _ \ / _ \
253 \/ \/ \/ \/ \/ \/ \/ \/
254 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 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 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 The Sierpinski curve points are midpoints of a Koch curve of 90 degree
269 angles with a unit gap between verticals.
270 Koch Curve Koch Curve
272 90 degree angles, unit gap
273 /\ | |
275 / \ | |
276 / \ | |
277 ----- ----- ------ ------
278 Sierpinski curve points "*" as midpoints
280 | |
282 7 8
283 | |
284 ---6--- ---9---
285 ---5--- --10---
287 | | | | | |
288 1 2 4 11 13 14
289 | | | | | |
290 ---0--- ---3--- --12--- --15---
291 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 Sierpinski curve mirror image and turn -45 degrees
298 two points on each Koch line segment
299 15 16
301 | |
302 14 17
303 12--13 . . 18--19
305 11--10 . . 21--20
307 3 4 9 22 27 28
309 | | | | | |
310 2 5 8 23 26 29
311 0---1 . . 6---7 . . 24--25 . . 30--31
313 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 N=1 2 3 4 5 6 7 8
322 Koch L R L L L R L R ...
323 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 "$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 "($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 Fractional positions give an X,Y position along a straight line
341 between the integer positions.
342 "$n = $path->n_start()"
344 Return 0, the first N in the path.
345 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 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 digit direction
362 ----- ---------
363 0 0
364 1 -2
365 2 2
366 3 0
367 direction = 1 + sum direction[base-4 digits of N/2]
369 for N even
370 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 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 direction
379 mirrored = 1 - sum direction[base-4 digits of N/2]
380 for N even
381 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 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 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 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 dX,dY = direction to 1,0 1,1 0,1 etc
402 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 N=2k or 2k+1 + frac
408 direction = 1 + sum direction[base-4 digits of k]
410 if (frac != 0 or N odd)
412 turn = nextturn[low-non-3 of k]
413 if N odd then direction += turn
415 dX,dY = direction to 1,0 1,1 0,1 etc
416 if frac!=0 then
418 direction += turn
419 next_dX,next_dY = direction to 1,0 1,1 0,1 etc
420 dX += frac*(next_dX - dX)
422 dY += frac*(next_dY - dY)
423 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 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 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 <http://oeis.org/A039963> (etc)
449 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 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 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 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 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/>.
483perl v5.34.0 2022-01-21Math::PlanePath::SierpinskiCurve(3)