1Math::PlanePath::SierpiUnssekriACrornotwrhiMebaautdthCe:ed:nPtPlreaernsle(P3Da)otchu:m:eSniteartpiionnskiArrowheadCentres(3)
2
3
4
6 Math::PlanePath::SierpinskiArrowheadCentres -- self-similar triangular
7 path traversal
8
10 use Math::PlanePath::SierpinskiArrowheadCentres;
11 my $path = Math::PlanePath::SierpinskiArrowheadCentres->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
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
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
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
315 Math::PlanePath, Math::PlanePath::SierpinskiArrowhead,
316 Math::PlanePath::SierpinskiTriangle
317
319 <http://user42.tuxfamily.org/math-planepath/index.html>
320
322 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
323
324 Math-PlanePath is free software; you can redistribute it and/or modify
325 it under the terms of the GNU General Public License as published by
326 the Free Software Foundation; either version 3, or (at your option) any
327 later version.
328
329 Math-PlanePath is distributed in the hope that it will be useful, but
330 WITHOUT ANY WARRANTY; without even the implied warranty of
331 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
332 General Public License for more details.
333
334 You should have received a copy of the GNU General Public License along
335 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
336
337
338
339perl v5.28.1 Ma2t0h1:7:-P1l2a-n0e3Path::SierpinskiArrowheadCentres(3)