1Math::PlanePath::FlowsnUaskeerCeCnotnrtersi(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::FlowsnakeCentres(3)
2
3
4

NAME

6       Math::PlanePath::FlowsnakeCentres -- self-similar path of hexagon
7       centres
8

SYNOPSIS

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

DESCRIPTION

15       This path is a variation of the flowsnake curve by William Gosper which
16       follows the flowsnake tiling the same way but the centres of the
17       hexagons instead of corners across.  The result is the same overall
18       shape, but a symmetric base figure.
19
20                                39----40                          8
21                               /        \
22                 32----33    38----37    41                       7
23                /        \           \     \
24              31----30    34----35----36    42    47              6
25                      \                    /     /  \
26                 28----29    16----15    43    46    48--...      5
27                /           /        \     \     \
28              27    22    17----18    14    44----45              4
29             /     /  \           \     \
30           26    23    21----20----19    13    10                 3
31             \     \                    /     /  \
32              25----24     4---- 5    12----11     9              2
33                         /        \              /
34                        3---- 2     6---- 7---- 8                 1
35                               \
36                           0---- 1                            <- Y=0
37
38           -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7  8  9
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
47             /        \
48            3---- 2     6---
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 sub-sections in
54       reverse.  Eg. N=7 to N=13 is the "1" part taking the base figure in
55       reverse and rotated so the end points towards the "2".
56
57       The next level can be seen at the midpoints of each such group, being
58       N=2,11,18,23,30,37,46.
59
60                        ---- 37
61                    ----       ---
62              30----              ---
63              |                      ---
64             |                           46
65             |
66             |        ----18
67            |    -----      ---
68           23---               ---
69                                  ---
70                                  --- 11
71                             -----
72                        2 ---
73
74   Arms
75       The optional "arms" parameter can give up to three copies of the curve,
76       each advancing successively.  For example "arms=>3" is as follows.
77       Notice the N=3*k points are the plain curve, and N=3*k+1 and N=3*k+2
78       are rotated copies of it.
79
80                                   84---...    48----45                   5
81                                  /           /        \
82                                81    66    51----54    42                4
83                               /     /  \           \     \
84                 28----25    78    69    63----60----57    39    30       3
85                /        \     \     \                    /     /  \
86              31----34    22    75----72    12----15    36----33    27    2
87                      \     \              /        \              /
88                 40----37    19     4     9---- 6    18----21----24       1
89                /           /     /  \           \
90              43    58    16     7     1     0---- 3    77----80      <- Y=0
91             /     /  \     \     \                    /        \
92           46    55    61    13----10     2    11    74----71    83      -1
93             \     \     \              /     /  \           \     \
94              49----52    64    73     5---- 8    14    65----68    86   -2
95                         /     /  \              /     /           /
96                 ...   67----70    76    20----17    62    53   ...      -3
97                   \              /     /           /     /  \
98                    85----82----79    23    38    59----56    50         -4
99                                     /     /  \              /
100                                   26    35    41----44----47            -5
101                                     \     \
102                                      29----32                           -6
103
104                                             ^
105                 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7  8  9
106
107       As described in "Arms" in Math::PlanePath::Flowsnake the flowsnake
108       essentially fills a hexagonal shape with wiggly sides.  For this
109       Centres variation the start of each arm corresponds to the centre of a
110       little hexagon.  The N=0 little hexagon is at the origin, and the 1 and
111       2 beside and below,
112
113           ^ / \   / \
114            \   \ /   \
115           | \   |     |
116           |  1  |  0--->
117           |     |     |
118            \   / \   /
119             \ /   \ /
120              |     |
121              |  2  |
122              | /   |
123               /   /
124             v  \ /
125
126       Like the main Flowsnake the sides of the arms mesh perfectly and three
127       arms fill the plane.
128

FUNCTIONS

130       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
131       classes.
132
133       "$path = Math::PlanePath::FlowsnakeCentres->new ()"
134           Create and return a new path object.
135
136       "($x,$y) = $path->n_to_xy ($n)"
137           Return the X,Y coordinates of point number $n on the path.  Points
138           begin at 0 and if "$n < 0" then the return is an empty list.
139
140           Fractional positions give an X,Y position along a straight line
141           between the integer positions.
142
143       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
144           In the current code the returned range is exact, meaning $n_lo and
145           $n_hi are the smallest and biggest in the rectangle, but don't rely
146           on that yet since finding the exact range is a touch on the slow
147           side.  (The advantage of which though is that it helps avoid very
148           big ranges from a simple over-estimate.)
149
150   Level Methods
151       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
152           Return "(0, 7**$level - 1)", or for multiple arms return "(0, $arms
153           * 7**$level - 1)".
154
155           There are 7^level points in a level, or arms*7^level for multiple
156           arms, numbered starting from 0.
157

FORMULAS

159   N to X,Y
160       The "n_to_xy()" calculation follows Ed Schouten's method
161
162           <http://80386.nl/projects/flowsnake/>
163
164       breaking N into base-7 digits, applying reversals from high to low
165       according to digits 1, 2, or 6, then applying rotation and position
166       according to the resulting digits.
167
168       Unlike Ed's code, the path here starts from N=0 at the edge of the
169       Gosper island shape and for that reason doesn't cover the plane.  An
170       offset of N-2*7^21 and suitable X,Y offset can be applied to get the
171       same result.
172
173   X,Y to N
174       The "xy_to_n()" calculation also follows Ed Schouten's method.  It's
175       based on a nice observation that the seven cells of the base figure can
176       be identified from their X,Y coordinates, and the centre of those seven
177       cell figures then shrunk down a level to be a unit apart, thus
178       generating digits of N from low to high.
179
180       In triangular grid X,Y a remainder is formed
181
182           m = (x + 2*y) mod 7
183
184       Taking the base figure's N=0 at 0,0 the remainders are
185
186               4---- 6
187             /        \
188            1---- 3     5
189                    \
190               0---- 2
191
192       The remainders are unchanged when the shape is moved by some multiple
193       of the next level X=5,Y=1 or the same at 120 degrees X=1,Y=3 or 240
194       degrees X=-4,Y=1.  Those vectors all have X+2*Y==0 mod 7.
195
196       From the m remainder an offset can be applied to move X,Y to the 0
197       position, leaving X,Y a multiple of the next level vectors X=5,Y=1 etc.
198       Those vectors can then be shrunk down with
199
200           Xshrunk = (3*Y + 5*X) / 14
201           Yshrunk = (5*Y - X) / 14
202
203       This gives integers since 3*Y+5*X and 5*Y-X are always multiples of 14.
204       For example the N=35 point at X=2,Y=6 reduces to X = (3*6+5*2)/14 = 2
205       and Y = (5*6-2)/14 = 2, which is then the "5" part of the base figure.
206
207       The remainders can be mapped to digits and then reversals and rotations
208       applied, from high to low, according to the edge orientation.  Those
209       steps can be combined in a single lookup table with 6 states (three
210       rotations, and each one forward or reverse).
211
212       For the main curve the reduction ends at 0,0.  For the multi-arm form
213       the second arm ends to the right at -2,0 and the third below at -1,-1.
214       Notice the modulo and shrink procedure maps those three points back to
215       themselves unchanged.  The calculation can be done without paying
216       attention to which arms are supposed to be in use.  On reaching one of
217       the three ends the "arm" is determined and the original X,Y can be
218       rejected or accepted accordingly.
219
220       The key to this approach is that the base figure is symmetric around a
221       central point, so the tiling can be broken down first, and the
222       rotations or reversals in the path applied afterwards.  Can it work on
223       a non-symmetric base figure like the "across" style of the main
224       Flowsnake, or something like the "DragonCurve" for that matter?
225

SEE ALSO

227       Math::PlanePath, Math::PlanePath::Flowsnake,
228       Math::PlanePath::GosperIslands
229
230       Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve,
231       Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve
232
233       <http://80386.nl/projects/flowsnake/> -- Ed Schouten's code
234

HOME PAGE

236       <http://user42.tuxfamily.org/math-planepath/index.html>
237

LICENSE

239       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
240       Kevin Ryde
241
242       This file is part of Math-PlanePath.
243
244       Math-PlanePath is free software; you can redistribute it and/or modify
245       it under the terms of the GNU General Public License as published by
246       the Free Software Foundation; either version 3, or (at your option) any
247       later version.
248
249       Math-PlanePath is distributed in the hope that it will be useful, but
250       WITHOUT ANY WARRANTY; without even the implied warranty of
251       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
252       General Public License for more details.
253
254       You should have received a copy of the GNU General Public License along
255       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
256
257
258
259perl v5.32.1                      2021-01-2M7ath::PlanePath::FlowsnakeCentres(3)
Impressum