1Math::PlanePath::FlowsnUaskeerCeCnotnrtersi(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::FlowsnakeCentres(3)
2
6 Math::PlanePath::FlowsnakeCentres -- self-similar path of hexagon
7 centres
8
10 use Math::PlanePath::FlowsnakeCentres;
11 my $path = Math::PlanePath::FlowsnakeCentres->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
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 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 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
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
47 / \
48 3---- 2 6---
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 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 The next level can be seen at the midpoints of each such group, being
58 N=2,11,18,23,30,37,46.
59 ---- 37
61 ---- ---
62 30---- ---
63 | ---
64 | 46
65 |
66 | ----18
67 | ----- ---
68 23--- ---
69 ---
70 --- 11
71 -----
72 2 ---
73 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 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 ^
105 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
106 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 ^ / \ / \
114 \ \ / \
115 | \ | |
116 | 1 | 0--->
117 | | |
118 \ / \ /
119 \ / \ /
120 | |
121 | 2 |
122 | / |
123 / /
124 v \ /
125 Like the main Flowsnake the sides of the arms mesh perfectly and three
127 arms fill the plane.
128
130 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
131 classes.
132 "$path = Math::PlanePath::FlowsnakeCentres->new ()"
134 Create and return a new path object.
135 "($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 Fractional positions give an X,Y position along a straight line
141 between the integer positions.
142 "($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 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 There are 7^level points in a level, or arms*7^level for multiple
156 arms, numbered starting from 0.
157
159 N to X,Y
160 The "n_to_xy()" calculation follows Ed Schouten's method
161 <http://80386.nl/projects/flowsnake/>
163 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 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 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 In triangular grid X,Y a remainder is formed
181 m = (x + 2*y) mod 7
183 Taking the base figure's N=0 at 0,0 the remainders are
185 4---- 6
187 / \
188 1---- 3 5
189 \
190 0---- 2
191 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 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 Xshrunk = (3*Y + 5*X) / 14
201 Yshrunk = (5*Y - X) / 14
202 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 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 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 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
227 Math::PlanePath, Math::PlanePath::Flowsnake,
228 Math::PlanePath::GosperIslands
229 Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve,
231 Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve
232 <http://80386.nl/projects/flowsnake/> -- Ed Schouten's code
234
236 <http://user42.tuxfamily.org/math-planepath/index.html>
237
239 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
240 This file is part of Math-PlanePath.
242 Math-PlanePath is free software; you can redistribute it and/or modify
244 it under the terms of the GNU General Public License as published by
245 the Free Software Foundation; either version 3, or (at your option) any
246 later version.
247 Math-PlanePath is distributed in the hope that it will be useful, but
249 WITHOUT ANY WARRANTY; without even the implied warranty of
250 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
251 General Public License for more details.
252 You should have received a copy of the GNU General Public License along
254 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
255perl v5.32.0 2020-07-2M8ath::PlanePath::FlowsnakeCentres(3)