1Math::PlanePath::SierpiUnssekriACrornotwrhiMebaautdthCe:ed:nPtPlreaernsle(P3Da)otchu:m:eSniteartpiionnskiArrowheadCentres(3)
2
3
4

NAME

6       Math::PlanePath::SierpinskiArrowheadCentres -- self-similar triangular
7       path traversal
8

SYNOPSIS

10        use Math::PlanePath::SierpinskiArrowheadCentres;
11        my $path = Math::PlanePath::SierpinskiArrowheadCentres->new;
12        my ($x, $y) = $path->n_to_xy (123);
13

DESCRIPTION

15       This path is variation on Sierpinski's curve from
16
17           Waclaw Sierpinski, "Sur une Courbe Dont Tout Point est un Point de
18           Ramification", Comptes Rendus Hebdomadaires des Séances de
19           l'Académie des Sciences, volume 160, January-June 1915, pages
20           302-305.
21           <http://gallica.bnf.fr/ark:/12148/bpt6k31131/f302.image.langEN>
22
23       The path here takes the centres of each triangle represented by the
24       arrowhead segments.  The points visited are the same as the
25       "SierpinskiTriangle" path, but traversing in a connected sequence
26       (rather than across rows).
27
28                     ...                                 ...
29                      /                                   /
30               .    30     .     .     .     .     .    65     .   ...
31                   /                                      \        /
32           28----29     .     .     .     .     .     .    66    68      9
33             \                                               \  /
34              27     .     .     .     .     .     .     .    67         8
35                \
36                 26----25    19----18----17    15----14----13            7
37                      /        \           \  /           /
38                    24     .    20     .    16     .    12               6
39                      \        /                       /
40                       23    21     .     .    10----11                  5
41                         \  /                    \
42                          22     .     .     .     9                     4
43                                                 /
44                              4---- 5---- 6     8                        3
45                               \           \  /
46                                 3     .     7                           2
47                                  \
48                                    2---- 1                              1
49                                        /
50                                       0                             <- Y=0
51
52           -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7
53
54       The base figure is the N=0 to N=2 shape.  It's repeated up in mirror
55       image as N=3 to N=6 then rotated across as N=6 to N=9.  At the next
56       level the same is done with N=0 to N=8 as the base, then N=9 to N=17 up
57       mirrored, and N=18 to N=26 across, etc.
58
59       The X,Y coordinates are on a triangular lattice using every second
60       integer X, per "Triangular Lattice" in Math::PlanePath.
61
62       The base pattern is a triangle like
63
64             .-------.-------.
65              \     / \     /
66               \ 2 /   \ 1 /
67                \ /     \ /
68                 .- - - -.
69                  \     /
70                   \ 0 /
71                    \ /
72                     .
73
74       Higher levels replicate this within the triangles 0,1,2 but the middle
75       is not traversed.  The result is the familiar Sierpinski triangle by
76       connected steps of either 2 across or 1 diagonal.
77
78           * * * * * * * * * * * * * * * *
79            *   *   *   *   *   *   *   *
80             * *     * *     * *     * *
81              *       *       *       *
82               * * * *         * * * *
83                *   *           *   *
84                 * *             * *
85                  *               *
86                   * * * * * * * *
87                    *   *   *   *
88                     * *     * *
89                      *       *
90                       * * * *
91                        *   *
92                         * *
93                          *
94
95       See the "SierpinskiTriangle" path to traverse by rows instead.
96
97   Level Ranges
98       Counting the N=0,1,2 part as level 1, each replication level goes from
99
100           Nstart = 0
101           Nlevel = 3^level - 1     inclusive
102
103       For example level 2 from N=0 to N=3^2-1=9.  Each level doubles in size,
104
105                        0  <= Y <= 2^level - 1
106           - (2^level - 1) <= X <= 2^level - 1
107
108       The Nlevel position is alternately on the right or left,
109
110           Xlevel = /  2^level - 1      if level even
111                    \  - 2^level + 1    if level odd
112
113       The Y axis ie. X=0, is crossed just after N=1,5,17,etc which is is 2/3
114       through the level, which is after two replications of the previous
115       level,
116
117           Ncross = 2/3 * 3^level - 1
118                  = 2 * 3^(level-1) - 1
119
120   Align Parameter
121       An optional "align" parameter controls how the points are arranged
122       relative to the Y axis.  The default shown above is "triangular".  The
123       choices are the same as for the "SierpinskiTriangle" path.
124
125       "right" means points to the right of the axis, packed next to each
126       other and so using an eighth of the plane.
127
128           align => "right"
129
130               |   |
131            7  |  26-25 19-18-17 15-14-13
132               |    /    |     |/     /
133            6  |  24    20    16    12
134               |   |   /           /
135            5  |  23 21       10-11
136               |   |/          |
137            4  |  22           9
138               |             /
139            3  |   4--5--6  8
140               |   |     |/
141            2  |   3     7
142               |   |
143            1  |   2--1
144               |    /
145           Y=0 |   0
146               +--------------------------
147                  X=0 1  2  3  4  5  6  7
148
149       "left" is similar but skewed to the left of the Y axis, ie. into
150       negative X.
151
152           align => "left"
153
154           \                         |
155            26-25 19-18-17 15-14-13  |  7
156                |   \     \ |     |  |
157               24    20    16    12  |  6
158                 \    |           |  |
159                  23 21       10-11  |  5
160                    \ |         \    |
161                     22           9  |  4
162                                  |  |
163                         4--5--6  8  |  3
164                          \     \ |  |
165                            3     7  |  2
166                             \       |
167                               2--1  |  1
168                                  |  |
169                                  0  | Y=0
170           --------------------------+
171
172            -7 -6 -5 -4 -3 -2 -1 X=0
173
174       "diagonal" puts rows on diagonals down from the Y axis to the X axis.
175       This uses the whole of the first quadrant, with gaps.
176
177           align => "diagonal"
178
179               |   |
180            7  |  26
181               |    \
182            6  |  24-25
183               |   |
184            5  |  23    19
185               |   |     |\
186            4  |  22-21-20 18
187               |             \
188            3  |   4          17
189               |   |\          |
190            2  |   3  5       16-15
191               |   |   \           \
192            1  |   2     6    10    14
193               |    \    |     |\     \
194           Y=0 |   0--1  7--8--9 11-12-13
195               +--------------------------
196                  X=0 1  2  3  4  5  6  7
197
198       These diagonals visit all points X,Y where X and Y written in binary
199       have no 1-bits in the same places, ie. where X bitand Y = 0.  This is
200       the same as the "SierpinskiTriangle" with align=diagonal.
201

FUNCTIONS

203       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
204       classes.
205
206       "$path = Math::PlanePath::SierpinskiArrowheadCentres->new ()"
207       "$path = Math::PlanePath::SierpinskiArrowheadCentres->new (align =>
208       $str)"
209           Create and return a new arrowhead path object.  "align" is a
210           string, one of the following as described above.
211
212               "triangular"       the default
213               "right"
214               "left"
215               "diagonal"
216
217       "($x,$y) = $path->n_to_xy ($n)"
218           Return the X,Y coordinates of point number $n on the path.  Points
219           begin at 0 and if "$n < 0" then the return is an empty list.
220
221           If $n is not an integer then the return is on a straight line
222           between the integer points.
223
224   Level Methods
225       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
226           Return "(0, 3**$level - 1)".
227

FORMULAS

229   N to X,Y
230       The align="diagonal" style is the most convenient to calculate.  Each
231       ternary digit of N becomes a bit of X and Y.
232
233           ternary digits of N, high to low
234               xbit = state_to_xbit[state+digit]
235               ybit = state_to_ybit[state+digit]
236               state = next_state[state+digit]
237
238       There's a total of 6 states which are the permutations of 0,1,2 in the
239       three triangular parts.  The states are in pairs as forward and
240       reverse, but that has no particular significance.  Numbering the states
241       by "3"s allows the digit 0,1,2 to be added to make an index into tables
242       for X,Y bit and next state.
243
244           state=0     state=3
245           +---------+ +---------+
246           |^ 2 |    | |\ 0 |    |
247           | \  |    | | \  |    |
248           |  \ |    | |  v |    |
249           |----+----| |----+----|
250           |    |^   | |    ||   |
251           | 0  || 1 | | 0  || 1 |
252           |--->||   | |<---|v   |
253           +---------+ +---------+
254
255           state=6      state=9
256           +---------+  +---------+
257           |    |    |  |    |    |
258           | 1  |    |  | 1  |    |
259           |--->|    |  |<---|    |
260           |----+----|  |----+----|
261           |^   |\ 2 |  ||   |^   |
262           ||0  | \  |  || 2 | \0 |
263           ||   |  v |  |v   |  \ |
264           +---------+  +---------+
265
266           state=12     state=15
267           +---------+  +---------+
268           || 0 |    |  |^   |    |
269           ||   |    |  || 2 |    |
270           |v   |    |  ||   |    |
271           |----+----|  |----+----|
272           |\ 1 |    |  |^ 1 |    |
273           | \  | 2  |  | \  |  0 |
274           |  v |--->|  |  \ |<---|
275           +---------+  +---------+
276
277       The initial state is 0 if an even number of ternary digits, or 6 if
278       odd.  In the samples above it can be seen for example that N=0 to N=8
279       goes upwards as per state 0, whereas N=0 to N=2 goes across as per
280       state 6.
281
282       Having calculated an X,Y in align="diagonal" style it can be mapped to
283       the other alignments by
284
285           align        coordinates from diagonal X,Y
286           -----        -----------------------------
287           triangular      X-Y, X+Y
288           right           X, X+Y
289           left            -Y, X+Y
290
291   N to dX,dY
292       For fractional N the direction of the curve towards the N+1 point can
293       be found from the least significant digit 0 or 1 (ie. a non-2 digit)
294       and the state at that point.
295
296       This works because if the least significant ternary digit of N is a 2
297       then the direction of the curve is determined by the next level up, and
298       so on for all trailing 2s until reaching a non-2 digit.
299
300       If N is all 2s then the direction should be reckoned from an initial 0
301       digit above them, which means the opposite 6 or 0 of the initial state.
302
303   Rectangle to N Range
304       An easy over-estimate of the range can be had from inverting the Nlevel
305       formulas in "Level Ranges" above.
306
307           level = floor(log2(Ymax)) + 1
308           Nmax = 3^level - 1
309
310       For example Y=5, level=floor(log2(11))+1=3, so Nmax=3^3-1=26, which is
311       the left end of the Y=7 row, ie. rounded up to the end of the Y=4 to
312       Y=7 replication.
313

SEE ALSO

315       Math::PlanePath, Math::PlanePath::SierpinskiArrowhead,
316       Math::PlanePath::SierpinskiTriangle
317

HOME PAGE

319       <http://user42.tuxfamily.org/math-planepath/index.html>
320

LICENSE

322       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
323       Kevin Ryde
324
325       Math-PlanePath is free software; you can redistribute it and/or modify
326       it under the terms of the GNU General Public License as published by
327       the Free Software Foundation; either version 3, or (at your option) any
328       later version.
329
330       Math-PlanePath is distributed in the hope that it will be useful, but
331       WITHOUT ANY WARRANTY; without even the implied warranty of
332       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
333       General Public License for more details.
334
335       You should have received a copy of the GNU General Public License along
336       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
337
338
339
340perl v5.34.0                    Ma2t0h2:2:-P0l1a-n2e1Path::SierpinskiArrowheadCentres(3)
Impressum