1Math::PlanePath::FlowsnUaskeer(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::Flowsnake(3)
2
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 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 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 X=-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
39 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 The base pattern is the seven points 0 to 6,
45 4---- 5---- 6
47 \ \
48 3---- 2
49 /
50 0---- 1
51 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 42
58 ----------- ---
59 35 ---
60 ----------- ---
61 28 49 ---
62 ---
63 ---- 14
64 --- ----------- |
65 21 |
66 |
67 |
68 |
69 ---- 7
70 -----
71 0 ---
72 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 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 Tiling
83 The base pattern corresponds to a tiling by hexagons as follows, with
84 the "***" lines being the base figure.
85 . .
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 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 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 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 ^
143 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
144 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 Essentially the flowsnake fills an ever expanding hexagon with one
151 corner at the origin, and wiggly sides.
152 *---*
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 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 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 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 "$path = Math::PlanePath::Flowsnake->new ()"
184 "$path = Math::PlanePath::Flowsnake->new (arms => $a)"
185 Create and return a new flowsnake path object.
186 The optional "arms" parameter gives between 1 and 3 copies of the
188 curve successively advancing.
189 "($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 Fractional positions give an X,Y position along a straight line
195 between the integer positions.
196 "($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 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 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 direction 0 to 5, multiple of 60-degrees
220 plain or reverse pattern
221 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 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 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 The digit is then added as either the plain or reversed base figure,
237 plain reverse
239 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 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 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 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 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 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 X, Y same
275 X-2, Y left (+180 degrees)
276 X-1, Y-1 left down (+240 degrees)
277 This is true even when the rotated "arms" multiple paths (the same
279 number of arms in both paths).
280 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 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 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 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 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 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 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 zcount
323 ---+--------+--------+--------+--------+
324 high | tdigit | 3s | zdigit | 0s | low
325 ---+--------+--------+--------+--------+
326 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 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 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 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 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 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 <http://oeis.org/A261180> (etc)
379 A334485 (X-Y)/2 diagonal coordinate
381 A334486 Y coordinate
382 A261180 direction 0 to 5
384 A261185 direction mod 2
385 A229214 direction 1,2,3,-1,-2,-3 spiralling clockwise
386 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 Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve,
396 Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve
397 Fukuda, Shimizu and Nakamura, "New Gosper Space Filling Curves", on
399 flowsnake variations in bigger hexagons (with wiggly sides too).
400 <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 This file is part of Math-PlanePath.
412 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 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 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/>.
425perl v5.36.0 2023-01-20 Math::PlanePath::Flowsnake(3)