1Math::PlanePath::SierpiUnssekriCCuornvter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::SierpinskiCurve(3)
2
3
4

NAME

6       Math::PlanePath::SierpinskiCurve -- Sierpinski curve
7

SYNOPSIS

9        use Math::PlanePath::SierpinskiCurve;
10        my $path = Math::PlanePath::SierpinskiCurve->new (arms => 2);
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

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

FUNCTIONS

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

FORMULAS

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

OEIS

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

SEE ALSO

461       Math::PlanePath, Math::PlanePath::SierpinskiCurveStair,
462       Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::KochCurve
463

HOME PAGE

465       <http://user42.tuxfamily.org/math-planepath/index.html>
466

LICENSE

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)
Impressum