1Math::PlanePath::FlowsnUaskeer(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::Flowsnake(3)
2
3
4
6 Math::PlanePath::Flowsnake -- self-similar path through hexagons
7
9 use Math::PlanePath::Flowsnake;
10 my $path = Math::PlanePath::Flowsnake->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path is an integer version of the flowsnake curve by William
15 Gosper.
16
17 A single arm of the curve fills 1/3 of the plane, spiralling around
18 anti-clockwise ever fatter and with jagged self-similar edges.
19
20 39----40----41 8
21 \ \
22 32----33----34 38----37 42 7
23 \ \ / /
24 31----30 35----36 43 47----48 6
25 / \ \ \
26 28----29 17----16----15 44 46 49--.. 5
27 / \ \ \ /
28 27 23----22 18----19 14 45 4
29 \ \ \ / /
30 26 24 21----20 13 11----10 3
31 \ / \ / /
32 25 4---- 5---- 6 12 9 2
33 \ \ /
34 3---- 2 7---- 8 1
35 /
36 0---- 1 Y=0
37
38 X=-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
39
40 The points are spread out on every second X coordinate to make little
41 triangles with integer coordinates, per "Triangular Lattice" in
42 Math::PlanePath.
43
44 The base pattern is the seven points 0 to 6,
45
46 4---- 5---- 6
47 \ \
48 3---- 2
49 /
50 0---- 1
51
52 This repeats at 7-fold increasing scale, with sub-sections rotated
53 according to the edge direction and the 1, 2 and 6 sections in reverse.
54 The next level can be seen at the multiple-of-7 points
55 N=0,7,14,21,28,35,42,49.
56
57 42
58 ----------- ---
59 35 ---
60 ----------- ---
61 28 49 ---
62 ---
63 ---- 14
64 --- ----------- |
65 21 |
66 |
67 |
68 |
69 ---- 7
70 -----
71 0 ---
72
73 Notice this is the same shape as N=0 to N=6, but rotated by
74 atan(1/sqrt(7)) = 20.68 degrees anti-clockwise. Each level rotates
75 further and for example after about 18 levels it goes all the way
76 around and back to the first quadrant.
77
78 The rotation doesn't fill the plane though, only 1/3 of it. The shape
79 fattens as it curls around, but leaves a spiral gap beneath (see "Arms"
80 below).
81
82 Tiling
83 The base pattern corresponds to a tiling by hexagons as follows, with
84 the "***" lines being the base figure.
85
86 . .
87 / \ / \
88 / \ / \
89 . . .
90 | | |
91 | | |
92 4*****5*****6
93 /*\ / \ /*\
94 / * \ / \ / * \
95 . * . . * .
96 | * | | *|
97 | *| | *|
98 . 3*****2 7...
99 \ / \ /*\ /
100 \ / \ / * \ /
101 . . * .
102 | | * |
103 | |* |
104 0*****1 .
105 \ / \ /
106 \ / \ /
107 . .
108
109 In the next level the parts corresponding to 1, 2 and 6 are reversed
110 because they have their hexagon tile to the right of the line segment,
111 rather than to the left.
112
113 Arms
114 The optional "arms" parameter can give up to three copies of the
115 flowsnake, each advancing successively. For example "arms=>3" is as
116 follows.
117
118 arms => 3 51----48----45 5
119 \ \
120 ... 69----66 54----57 42 4
121 \ \ \ / /
122 28----25----22 78 72 63----60 39 33----30 3
123 \ \ \ / \ / /
124 31----34 19 75 12----15----18 36 27 2
125 / / \ \ /
126 40----37 16 4---- 1 9---- 6 21----24 1
127 / \ \ /
128 43 55----58 13 7 0---- 3 74----77---... <- Y=0
129 \ \ \ \ / \
130 46 52 61 10 2 8----11 71----68 -1
131 \ / / \ / / /
132 49 64 70----73 5 14 62----65 -2
133 \ / / / /
134 67 76 20----17 59 53----50 -3
135 / / \ / /
136 ... 23 35----38 56 47 -4
137 \ \ \ /
138 26 32 41----44 -5
139 \ /
140 29 -6
141
142 ^
143 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
144
145 The N=3*k points are the plain curve, N=3*k+1 is a copy rotated by 120
146 degrees (1/3 around), and N=3*k+2 is a copy rotated by 240 degrees (2/3
147 around). The initial N=1 of the second arm and N=2 of the third
148 correspond to N=3 of the first arm, rotated around.
149
150 Essentially the flowsnake fills an ever expanding hexagon with one
151 corner at the origin, and wiggly sides.
152
153 *---*
154 / \
155 *---* A * Plain curve in A.
156 / \ / Room for two more arms in B and C,
157 * B O---* rotated 120 and 240 degrees.
158 \ / \
159 *---* C *
160 \ /
161 *---*
162
163 The sides of these "hexagons" are not straight lines but instead wild
164 wiggly spiralling S shapes, and the endpoints rotate around by the
165 angle described above at each level. Opposing sides are symmetric, so
166 they mesh perfectly and with three arms fill the plane.
167
168 Fractal
169 The flowsnake can also be thought of as successively subdividing line
170 segments with suitably scaled copies of the 0 to 7 figure (or its
171 reversal).
172
173 The code here could be used for that by taking points N=0 to N=7^level.
174 The Y coordinates should be multiplied by sqrt(3) to make proper
175 equilateral triangles, then a rotation and scaling to make the endpoint
176 come out at some desired point, such as X=1,Y=0. With such a scaling
177 the path is confined to a finite fractal boundary.
178
180 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
181 classes.
182
183 "$path = Math::PlanePath::Flowsnake->new ()"
184 "$path = Math::PlanePath::Flowsnake->new (arms => $a)"
185 Create and return a new flowsnake path object.
186
187 The optional "arms" parameter gives between 1 and 3 copies of the
188 curve successively advancing.
189
190 "($x,$y) = $path->n_to_xy ($n)"
191 Return the X,Y coordinates of point number $n on the path. Points
192 begin at 0 and if "$n < 0" then the return is an empty list.
193
194 Fractional positions give an X,Y position along a straight line
195 between the integer positions.
196
197 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
198 In the current code the returned range is exact, meaning $n_lo and
199 $n_hi are the smallest and biggest in the rectangle, but don't rely
200 on that yet since finding the exact range is a touch on the slow
201 side. (The advantage of which though is that it helps avoid very
202 big ranges from a simple over-estimate.)
203
204 Level Methods
205 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
206 Return "(0, 7**$level)", or for multiple arms return "(0, $arms *
207 7**$level)".
208
209 There are 7^level + 1 points in a level, numbered starting from 0.
210 On the second and third arms the origin is omitted (so as not to
211 repeat that point) and so just 7^level for them, giving 7^level+1 +
212 (arms-1)*7^level = arms*7^level + 1 many points starting from 0.
213
215 N to X,Y
216 The position of a given N can be calculated from the base-7 digits of N
217 from high to low. At a given digit position the state maintained is
218
219 direction 0 to 5, multiple of 60-degrees
220 plain or reverse pattern
221
222 It's convenient to work in the "i,j" coordinates per "Triangular
223 Calculations" in Math::PlanePath. This represents a point in the
224 triangular grid as i+j*w where w=1/2+I*sqrt(3)/2 the a complex sixth
225 root of unity at +60 degrees.
226
227 foreach base-7 digit high to low
228 (i,j) = (2i-j, i+3j) # multiply by 2+w
229 (i,j) += position of digit in plain or reverse,
230 and rotated by "direction"
231
232 The multiply by 2+w scales up i,j by that vector, so for instance
233 i=1,j=0 becomes i=2,j=1. This spreads the points as per the
234 multiple-of-7 diagram shown above, so what was at N scales up to 7*N.
235
236 The digit is then added as either the plain or reversed base figure,
237
238 plain reverse
239
240 4-->5-->6
241 ^ ^
242 \ \
243 3-->2 * 6<---*
244 / ^
245 v /
246 0-->1 0 5<--4
247 \ \
248 v v
249 1<--2<--3
250
251 The arrow shown in each part is whether the state becomes plain or
252 reverse. For example in plain state at digit=1 the arrow in segment 1
253 to 2 points backwards so if digit=1 then the state changes to reverse
254 for the next digit. The direction likewise follows the direction of
255 each segment in the pattern.
256
257 Notice the endpoint "*" is at at 2+w in both patterns. When
258 considering the rotation it's convenient to reckon the direction by
259 this endpoint.
260
261 The combination of direction and plain/reverse is a total of 14
262 different states, and for each there's 7 digit values (0 to 6) for a
263 total 84 i,j.
264
265 X,Y to N
266 The current approach uses the "FlowsnakeCentres" code. The tiling in
267 "Flowsnake" and "FlowsnakeCentres" is the same so the X,Y of a given N
268 are no more than 1 away in the grid of the two forms.
269
270 The way the two lowest shapes are arranged in fact means that if the
271 Flowsnake N is at X,Y then the same N in "FlowsnakeCentres" is at one
272 of three locations
273
274 X, Y same
275 X-2, Y left (+180 degrees)
276 X-1, Y-1 left down (+240 degrees)
277
278 This is true even when the rotated "arms" multiple paths (the same
279 number of arms in both paths).
280
281 Is there an easy way to know which of the three offsets is right? The
282 current approach is to put each through "FlowsnakeCentres" to make an
283 N, and put that N back through Flowsnake "n_to_xy()" to see if it's the
284 target $n.
285
286 Rectangle to N Range
287 The current code calculates an exact "rect_to_n_range()" by searching
288 for the highest and lowest Ns which are in the rectangle.
289
290 The curve at a given level is bounded by the Gosper island shape but
291 the wiggly sides make it difficult to calculate, so a bounding radius
292 sqrt(7)^level, plus a bit, is used. The portion of the curve
293 comprising a given set of high digits of N can be excluded if the N
294 point is more than that radius away from the rectangle.
295
296 When a part of the curve is excluded it prunes a whole branch of the
297 digits tree. When the lowest digit is reached then a check for that
298 point being actually within the rectangle is made. The radius
299 calculation is a bit rough, and it doesn't take into account the
300 direction of the curve, so it's a rather large over-estimate, but it
301 works.
302
303 The same sort of search can be applied for highest and lowest N in a
304 non-rectangular shapes, calculating a radial distance away from the
305 shape. The distance calculation doesn't have to be exact either, it
306 can go from something bounding the shape until the lowest digit is
307 reached and an individual X,Y is considered as a candidate for high or
308 low N.
309
310 N to Turn
311 The turn made by the curve at a point N>=1 can be calculated from the
312 lowest non-0 digit and the plain/reverse state per the lowest non-3
313 above there.
314
315 N digits in base 7
316 strip low 0-digits, zcount many of them
317 zdigit = take next digit (lowest non-0)
318 strip 3-digits
319 tdigit = take next digit (0 if no digits left)
320 plain if tdigit=0,4,5, reverse if tdigit=1,2,6
321
322 zcount
323 ---+--------+--------+--------+--------+
324 high | tdigit | 3s | zdigit | 0s | low
325 ---+--------+--------+--------+--------+
326
327 if zcount=0 if zcount>=1
328 ie. no low 0s ie. some low 0s
329 zdigit plain reverse plain reverse
330 ------ ----- ------- ----- -------
331 1 1 1 1 1
332 2 2 0 1 -1 turn left
333 3 -1 2 -1 1 multiple of
334 4 -2 1 -1 1 60 degrees
335 5 0 -2 1 -1
336 6 -1 -1 -1 -1
337
338 For example N=9079 is base-7 "35320" so a single low 0 for zcount=1 and
339 strip it to "3532". Take zdigit=2 leaving "353". Skip low 3s leaving
340 "35". Take tdigit=5 which is "plain". So table "plain" with zcount>=1
341 is the third column and there zdigit=2 is turn=+1.
342
343 The turns in the zcount=0 "no low 0s" columns follow the turns of the
344 base pattern shown above. For example zdigit=1 is as per N=1 turning
345 120 degrees left, so +2. For the reverse pattern the turns are negated
346 and the zdigit value reversed, so the "reverse" column read 6 to 1 is
347 the same as the plain column negated and read 1 to 6.
348
349 Low 0s are stripped because the turn at a point such as N=7 ("10" in
350 base-7) is determined by the pattern above it, the self-similar
351 multiple-of-7s shape. But when there's low 0s in the way there's an
352 adjustment to apply because the last segment of the base pattern is not
353 in the same direction as the first, but instead at -60 degrees.
354 Likewise the first segment of the reverse pattern. At some zdigit
355 positions those two cancel out, such as at zdigit=1 where a plain and
356 reverse meet, but others it's not so and hence separate table columns
357 for with or without low 0s.
358
359 The plain or reverse pattern is determined by the lowest non-3 digit.
360 This works because the digit=0, digit=4, and digit=5 segments of the
361 base pattern have their sub-parts "plain" in all cases, both the plain
362 and reverse forms. Conversely digit=1, digit=2 and digit=6 segments
363 are "reverse" in all cases, both plain and reverse forms. But the
364 digit=3 part is plain in plain and reverse in reverse, so it inherits
365 the orientation of the digit above and it's therefore necessary to skip
366 across any 3s.
367
368 When taking digits, N is treated as having infinite 0-digits at the
369 high end. This only affects the tdigit plain/reverse step. If N has a
370 single non-zero such as "5000" then it's taken as zdigit=5 and above
371 that for the plain/reverse a tdigit=0 is then assumed. The first turn
372 is at N=1 so there's always at least one non-0 for the zdigit.
373
375 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
376 this path include
377
378 <http://oeis.org/A261180> (etc)
379
380 A334485 (X-Y)/2 diagonal coordinate
381 A334486 Y coordinate
382
383 A261180 direction 0 to 5
384 A261185 direction mod 2
385 A229214 direction 1,2,3,-1,-2,-3 spiralling clockwise
386
387 A261120 count of triple-visited points in the fractal limit
388 A262147 \ fractions making a spiral in the fractal
389 A262148 /
390
392 Math::PlanePath, Math::PlanePath::FlowsnakeCentres,
393 Math::PlanePath::GosperIslands
394
395 Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve,
396 Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve
397
398 Fukuda, Shimizu and Nakamura, "New Gosper Space Filling Curves", on
399 flowsnake variations in bigger hexagons (with wiggly sides too).
400
401 <http://kilin.clas.kitasato-u.ac.jp/museum/gosperex/343-024.pdf> or
402 <http://web.archive.org/web/20070630031400/http://kilin.u-shizuoka-ken.ac.jp/museum/gosperex/343-024.pdf>
403
405 <http://user42.tuxfamily.org/math-planepath/index.html>
406
408 Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
409 2020 Kevin Ryde
410
411 This file is part of Math-PlanePath.
412
413 Math-PlanePath is free software; you can redistribute it and/or modify
414 it under the terms of the GNU General Public License as published by
415 the Free Software Foundation; either version 3, or (at your option) any
416 later version.
417
418 Math-PlanePath is distributed in the hope that it will be useful, but
419 WITHOUT ANY WARRANTY; without even the implied warranty of
420 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
421 General Public License for more details.
422
423 You should have received a copy of the GNU General Public License along
424 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
425
426
427
428perl v5.34.0 2022-01-21 Math::PlanePath::Flowsnake(3)