1Math::PlanePath::FlowsnUaskeer(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::Flowsnake(3)
2
3
4

NAME

6       Math::PlanePath::Flowsnake -- self-similar path through hexagons
7

SYNOPSIS

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

DESCRIPTION

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

FUNCTIONS

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

FORMULAS

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 for
288       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

OEIS

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

SEE ALSO

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

HOME PAGE

405       <http://user42.tuxfamily.org/math-planepath/index.html>
406

LICENSE

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.36.0                      2023-01-20     Math::PlanePath::Flowsnake(3)
Impressum