1Math::PlanePath::SierpiUnssekriACrornotwrhiebaudt(e3d)PMeartlh:D:oPcluamneenPtaatthi:o:nSierpinskiArrowhead(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

15       This path is an integer version of 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 is self-similar triangular parts leaving middle triangle gaps
24       giving the Sierpinski triangle shape.
25
26           \
27            27----26          19----18          15----14             8
28                    \        /        \        /        \
29                     25    20          17----16          13          7
30                    /        \                          /
31                  24          21                11----12             6
32                    \        /                 /
33                     23----22                10                      5
34                                               \
35                               5---- 6           9                   4
36                             /        \        /
37                            4           7---- 8                      3
38                             \
39                               3---- 2                               2
40                                      \
41                                        1                            1
42                                      /
43                                     0                           <- Y=0
44
45            -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7  8
46
47       The base figure is the N=0 to N=3 shape.  It's repeated up in mirror
48       image as N=3 to N=6 then across as N=6 to N=9.  At the next level the
49       same is done with the N=0 to N=9 shape, up as N=9 to N=18 and across as
50       N=18 to N=27, etc.
51
52       The X,Y coordinates are on a triangular lattice done in integers by
53       using every second X, per "Triangular Lattice" in Math::PlanePath.
54
55       The base pattern is a triangle like
56
57           3---------2 - - - - .
58            \         \
59                C  /   \  B  /
60              \      D  \
61                 /       \ /
62                . - - - - 1
63                 \       /
64                     A  /
65                   \   /
66                      /
67                     0
68
69       Higher levels go into the triangles A,B,C but the middle triangle D is
70       not traversed.  It's hard to see that omitted middle in the initial N=0
71       to N=27 above.  The following is more of the visited points, making it
72       clearer
73
74               *   * *   * *   *                 * *   * *   * *
75                * *   * *   * *                 *   * *   * *
76                   * *   * *                     * *     *   *
77                  *         *                       *     * *
78                   * *   * *                       *   * *
79                      * *                           * *   *
80                     *   *                             * *
81                      * *                             *
82                         * *   * *   * *   * *   * *   *
83                        *   * *   * *   * *   * *   * *
84                         * *     *   *     * *   * *
85                            *     * *     *         *
86                           *   * *         * *   * *
87                            * *   *           * *
88                               * *           *   *
89                              *               * *
90                               * *   * *   * *
91                                  * *   * *   *
92                                 *   *     * *
93                                  * *     *
94                                     * *   *
95                                    *   * *
96                                     * *
97                                        *
98                                       *
99
100   Sierpinski Triangle
101       The path is related to the Sierpinski triangle or "gasket" by treating
102       each line segment as the side of a little triangle.  The N=0 to N=1
103       segment has a triangle on the left, N=1 to N=2 on the right, and N=2 to
104       N=3 underneath, which are per the A,B,C parts shown above.  Notice
105       there's no middle little triangle "D" in the triplets of line segments.
106       In general a segment N to N+1 has its little triangle to the left if N
107       even or to the right if N odd.
108
109       This pattern of little triangles is why the N=4 to N=5 looks like it
110       hasn't visited the vertex of the triangular N=0 to N=9 -- the 4 to 5
111       segment is standing in for a little triangle to the left of that
112       segment.  Similarly N=13 to N=14 and each alternate side midway through
113       replication levels.
114
115       There's easier ways to generate the Sierpinski triangle though.  One of
116       the simplest is to take X,Y coordinates which have no 1 bit on common,
117       ie. a bitwise-AND,
118
119           ($x & $y) == 0
120
121       which gives the shape in the first quadrant X>=0,Y>=0.  The same can be
122       had with the "ZOrderCurve" path by plotting all numbers N which have no
123       digit 3 in their base-4 representation (see "Power of 2 Values" in
124       Math::PlanePath::ZOrderCurve), since digit 3s in that case are X,Y
125       points with a 1 bit in common.
126
127       The attraction of this Arrowhead path is that it makes a connected
128       traversal through the Sierpinski triangle pattern.
129
130   Level Sizes
131       Counting the N=0,1,2,3 part as level 1, each level goes from
132
133           Nstart = 0
134           Nlevel = 3^level
135
136       inclusive of the final triangle corner position.  For example level 2
137       is from N=0 to N=3^2=9.  Each level doubles in size,
138
139                  0  <= Y <= 2^level
140           - 2^level <= X <= 2^level
141
142       The final Nlevel position is alternately on the right or left,
143
144           Xlevel = /  2^level      if level even
145                    \  - 2^level    if level odd
146
147       The Y axis is crossed, ie. X=0, at N=2,6,18,etc which is is 2/3 through
148       the level, ie. after two replications of the previous level,
149
150           Ncross = 2/3 * 3^level
151                  = 2 * 3^(level-1)
152
153   Align Parameter
154       An optional "align" parameter controls how the points are arranged
155       relative to the Y axis.  The default shown above is "triangular".  The
156       choices are the same as for the "SierpinskiTriangle" path.
157
158       "right" means points to the right of the axis, packed next to each
159       other and so using an eighth of the plane.
160
161           align => "right"
162
163               |   |
164            8  |  27-26    19-18    15-14
165               |      |   /    |   /    |
166            7  |     25 20    17-16    13
167               |    /    |            /
168            6  |  24    21       11-12
169               |   |   /        /
170            5  |  23-22       10
171               |               |
172            4  |      5--6     9
173               |    /    |   /
174            3  |   4     7--8
175               |   |
176            2  |   3--2
177               |      |
178            1  |      1
179               |    /
180           Y=0 |   0
181               +--------------------------
182                  X=0 1  2  3  4  5  6  7
183
184       "left" is similar but skewed to the left of the Y axis, ie. into
185       negative X.
186
187           align => "left"
188
189           \
190            27-26    19-18    15-14     |  8
191                 \    |   \    |   \    |
192                  25 20    17-16    13  |  7
193                   |   \             |  |
194                  24    21       11-12  |  6
195                    \    |        |     |
196                     23-22       10     |  5
197                                   \    |
198                            5--6     9  |  4
199                            |   \    |  |
200                            4     7--8  |  3
201                             \          |
202                               3--2     |  2
203                                   \    |
204                                     1  |  1
205                                     |  |
206                                     0  | Y=0
207           -----------------------------+
208
209            -8 -7 -6 -5 -4 -3 -2 -1 X=0
210
211       "diagonal" put rows on diagonals down from the Y axis to the X axis.
212       This uses the whole of the first quadrant (with gaps).
213
214           align => "diagonal"
215
216               |   |
217            8  |  27
218               |    \
219            7  |     26
220               |      |
221            6  |  24-25
222               |   |
223            5  |  23    20-19
224               |    \    |   \
225            4  |     22-21    18
226               |               |
227            3  |   4--5       17
228               |   |   \        \
229            2  |   3     6       16-15
230               |    \    |            \
231            1  |      2  7    10-11    14
232               |      |   \    |   \    |
233           Y=0 |   0--1     8--9    12-13
234               +--------------------------
235                  X=0 1  2  3  4  5  6  7
236
237   Sideways
238       Sierpinski presents the curve with a base along the X axis.  That can
239       be had here with a -60 degree rotation (see "Triangular Lattice" in
240       Math::PlanePath),
241
242           (3Y+X)/2, (Y-X)/2       rotate -60
243
244       The first point N=1 is then along the X axis at X=2,Y=0.  Or to have it
245       diagonally upwards first then apply a mirroring -X before rotating
246
247           (3Y-X)/2, (Y+X)/2       mirror X and rotate -60
248
249       The plain -60 rotate puts the Nlevel=3^level point on the X axis for
250       even number level, and at the top peak for odd level.  With the extra
251       mirroring it's the other way around.  If drawing successive levels then
252       the two ways can be alternated to have the endpoint on the X axis each
253       time.
254

FUNCTIONS

256       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
257       classes.
258
259       "$path = Math::PlanePath::SierpinskiArrowhead->new ()"
260       "$path = Math::PlanePath::SierpinskiArrowhead->new (align => $str)"
261           Create and return a new arrowhead path object.  "align" is a
262           string, one of the following as described above.
263
264               "triangular"       the default
265               "right"
266               "left"
267               "diagonal"
268
269       "($x,$y) = $path->n_to_xy ($n)"
270           Return the X,Y coordinates of point number $n on the path.  Points
271           begin at 0 and if "$n < 0" then the return is an empty list.
272
273           If $n is not an integer then the return is on a straight line
274           between the integer points.
275
276   Level Methods
277       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
278           Return "(0, 3**$level)".
279

FORMULAS

281   Turn
282       The turn at N is given by ternary
283
284           turn(N)    N + LowestNonZero(N) + CountLowZeros(N)
285           -------    ---------------------------------------
286            left                      even
287            right                     odd
288
289       In the replications, turns N=1 and N=2 are both left.  A low 0 digit
290       expansion is mirror image to maintain initial segment direction.  Parts
291       "B" digit=1 above are each mirror images too so turns flip.
292
293           [flip for each 1 digit]  [1 or 2]  [flip for each low 0 digit]
294
295       N is odd or even according as the number of ternary 1 digits is odd or
296       even (all 2 digits being even of course), so N parity accounts for the
297       "B" mirrorings.  On a binary computer this is just the low bit rather
298       than examining the high digits of N.  In any case if the ternary lowest
299       non-0 is a 1 then it is not such a mirror so adding LowestNonZero
300       cancels that.
301
302       This turn rule is noted by Alexis Monnerot-Dumaine in OEIS A156595.
303       That sequence is LowestNonZero(N) + CountLowZeros(N) mod 2 and flipping
304       according as N odd or even is the arrowhead turns.
305

OEIS

307       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
308       this path include,
309
310           <http://oeis.org/A156595> (etc)
311
312           A156595   turn 0=left,1=right at even N=2,4,6,etc
313           A189706   turn 0=left,1=right at odd N=1,3,5,etc
314           A189707     (N+1)/2 of the odd N positions of left turns
315           A189708     (N+1)/2 of the odd N positions of right turns
316

SEE ALSO

318       Math::PlanePath, Math::PlanePath::SierpinskiArrowheadCentres,
319       Math::PlanePath::SierpinskiTriangle, Math::PlanePath::KochCurve
320

HOME PAGE

322       <http://user42.tuxfamily.org/math-planepath/index.html>
323

LICENSE

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