1Math::PlanePath::SierpiUnssekriACrornotwrhiMebaautdthCe:ed:nPtPlreaernsle(P3Da)otchu:m:eSniteartpiionnskiArrowheadCentres(3)
2
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 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 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 ... ...
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 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7
53 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 The X,Y coordinates are on a triangular lattice using every second
60 integer X, per "Triangular Lattice" in Math::PlanePath.
61 The base pattern is a triangle like
63 .-------.-------.
65 \ / \ /
66 \ 2 / \ 1 /
67 \ / \ /
68 .- - - -.
69 \ /
70 \ 0 /
71 \ /
72 .
73 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 * * * * * * * * * * * * * * * *
79 * * * * * * * *
80 * * * * * * * *
81 * * * *
82 * * * * * * * *
83 * * * *
84 * * * *
85 * *
86 * * * * * * * *
87 * * * *
88 * * * *
89 * *
90 * * * *
91 * *
92 * *
93 *
94 See the "SierpinskiTriangle" path to traverse by rows instead.
96 Level Ranges
98 Counting the N=0,1,2 part as level 1, each replication level goes from
99 Nstart = 0
101 Nlevel = 3^level - 1 inclusive
102 For example level 2 from N=0 to N=3^2-1=9. Each level doubles in size,
104 0 <= Y <= 2^level - 1
106 - (2^level - 1) <= X <= 2^level - 1
107 The Nlevel position is alternately on the right or left,
109 Xlevel = / 2^level - 1 if level even
111 \ - 2^level + 1 if level odd
112 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 Ncross = 2/3 * 3^level - 1
118 = 2 * 3^(level-1) - 1
119 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 "right" means points to the right of the axis, packed next to each
126 other and so using an eighth of the plane.
127 align => "right"
129 | |
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 "left" is similar but skewed to the left of the Y axis, ie. into
150 negative X.
151 align => "left"
153 \ |
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 -7 -6 -5 -4 -3 -2 -1 X=0
173 "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 align => "diagonal"
178 | |
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 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 "$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 "triangular" the default
213 "right"
214 "left"
215 "diagonal"
216 "($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 If $n is not an integer then the return is on a straight line
222 between the integer points.
223 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 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 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 state=0 state=3
245 +---------+ +---------+
246 |^ 2 | | |\ 0 | |
247 | \ | | | \ | |
248 | \ | | | v | |
249 |----+----| |----+----|
250 | |^ | | || |
251 | 0 || 1 | | 0 || 1 |
252 |--->|| | |<---|v |
253 +---------+ +---------+
254 state=6 state=9
256 +---------+ +---------+
257 | | | | | |
258 | 1 | | | 1 | |
259 |--->| | |<---| |
260 |----+----| |----+----|
261 |^ |\ 2 | || |^ |
262 ||0 | \ | || 2 | \0 |
263 || | v | |v | \ |
264 +---------+ +---------+
265 state=12 state=15
267 +---------+ +---------+
268 || 0 | | |^ | |
269 || | | || 2 | |
270 |v | | || | |
271 |----+----| |----+----|
272 |\ 1 | | |^ 1 | |
273 | \ | 2 | | \ | 0 |
274 | v |--->| | \ |<---|
275 +---------+ +---------+
276 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 Having calculated an X,Y in align="diagonal" style it can be mapped to
283 the other alignments by
284 align coordinates from diagonal X,Y
286 ----- -----------------------------
287 triangular X-Y, X+Y
288 right X, X+Y
289 left -Y, X+Y
290 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 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 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 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 level = floor(log2(Ymax)) + 1
308 Nmax = 3^level - 1
309 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 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 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 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/>.
336perl v5.28.0 Ma2t0h1:7:-P1l2a-n0e3Path::SierpinskiArrowheadCentres(3)