1Math::PlanePath::SierpiUnssekriACrornotwrhiebaudt(e3d)PMeartlh:D:oPcluamneenPtaatthi:o:nSierpinskiArrowhead(3)
2
6 Math::PlanePath::SierpinskiArrowhead -- self-similar triangular path
7 traversal
8
10 use Math::PlanePath::SierpinskiArrowhead;
11 my $path = Math::PlanePath::SierpinskiArrowhead->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path is an integer version of Sierpinski's curve from
16 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 The path is self-similar triangular parts leaving middle triangle gaps
24 giving the Sierpinski triangle shape.
25 \
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 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8
46 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 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 The base pattern is a triangle like
56 3---------2 - - - - .
58 \ \
59 C / \ B /
60 \ D \
61 / \ /
62 . - - - - 1
63 \ /
64 A /
65 \ /
66 /
67 0
68 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 * * * * * * * * * * * *
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 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 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 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 ($x & $y) == 0
120 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 The attraction of this Arrowhead path is that it makes a connected
128 traversal through the Sierpinski triangle pattern.
129 Level Sizes
131 Counting the N=0,1,2,3 part as level 1, each level goes from
132 Nstart = 0
134 Nlevel = 3^level
135 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 0 <= Y <= 2^level
140 - 2^level <= X <= 2^level
141 The final Nlevel position is alternately on the right or left,
143 Xlevel = / 2^level if level even
145 \ - 2^level if level odd
146 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 Ncross = 2/3 * 3^level
151 = 2 * 3^(level-1)
152 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 "right" means points to the right of the axis, packed next to each
159 other and so using an eighth of the plane.
160 align => "right"
162 | |
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 "left" is similar but skewed to the left of the Y axis, ie. into
185 negative X.
186 align => "left"
188 \
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 -8 -7 -6 -5 -4 -3 -2 -1 X=0
210 "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 align => "diagonal"
215 | |
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 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 (3Y+X)/2, (Y-X)/2 rotate -60
243 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 (3Y-X)/2, (Y+X)/2 mirror X and rotate -60
248 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
256 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
257 classes.
258 "$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 "triangular" the default
265 "right"
266 "left"
267 "diagonal"
268 "($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 If $n is not an integer then the return is on a straight line
274 between the integer points.
275 Level Methods
277 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
278 Return "(0, 3**$level)".
279
281 Turn
282 The turn at N is given by ternary
283 turn(N) N + LowestNonZero(N) + CountLowZeros(N)
285 ------- ---------------------------------------
286 left even
287 right odd
288 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 [flip for each 1 digit] [1 or 2] [flip for each low 0 digit]
294 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 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
307 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
308 this path include,
309 <http://oeis.org/A156595> (etc)
311 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
318 Math::PlanePath, Math::PlanePath::SierpinskiArrowheadCentres,
319 Math::PlanePath::SierpinskiTriangle, Math::PlanePath::KochCurve
320
322 <http://user42.tuxfamily.org/math-planepath/index.html>
323
325 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
326 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 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 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/>.
339perl v5.28.1 2018-0M1a-t3h1::PlanePath::SierpinskiArrowhead(3)