1Math::PlanePath::QuinteUtsReerplCiocnattrei(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::QuintetReplicate(3)
2
6 Math::PlanePath::QuintetReplicate -- self-similar "+" tiling
7
9 use Math::PlanePath::QuintetReplicate;
10 my $path = Math::PlanePath::QuintetReplicate->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is a self-similar tiling of the plane with "+" shapes. It's the
15 same kind of tiling as the "QuintetCurve" (and "QuintetCentres"), but
16 with the middle square of the "+" shape centred on the origin.
17 12 3
19 13 10 11 7 2
21 14 2 8 5 6 1
23 17 3 0 1 9 <- Y=0
25 18 15 16 4 22 -1
27 19 23 20 21 -2
29 24 -3
31 ^
33 -4 -3 -2 -1 X=0 1 2 3 4
34 The base pattern is a "+" shape
36 +---+
38 | 2 |
39 +---+---+---+
40 | 3 | 0 | 1 |
41 +---+---+---+
42 | 4 |
43 +---+
44 which is then replicated
46 +--+
48 | |
49 +--+ +--+ +--+
50 | 10 | | |
51 +--+ +--+--+ +--+
52 | | | 5 |
53 +--+--+ +--+ +--+
54 | | 0 | |
55 +--+ +--+ +--+--+
56 | 15 | | |
57 +--+ +--+--+ +--+
58 | | | 20 |
59 +--+ +--+ +--+
60 | |
61 +--+
62 The effect is to tile the whole plane. Notice the centres 0,5,10,15,20
64 are the same "+" shape but positioned around at angle atan(1/2)=26.565
65 degrees. The relative positioning in each of those parts is the same,
66 so at 5 the successive 6,7,8,9 are E,N,W,S like the base shape.
67 Complex Base
69 This tiling corresponds to expressing a complex integer X+i*Y as
70 base b=2+i
72 X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
73 where each digit position factor a[i] corresponds to N digits
75 N digit a[i]
77 ------- ------
78 0 0
79 1 1
80 2 i
81 3 -1
82 4 -i
83 The base b is at an angle arg(b) = atan(1/2) = 26.56 degrees as seen at
85 N=5 above. Successive powers b^2, b^3, b^4 etc at N=5^level rotate
86 around by that much each time.
87 Npow = 5^level at b^level
89 angle(Npow) = level*26.56 degrees
90 radius(Npow) = sqrt(5) ^ level
91 The path can be reckoned bottom-up as a new low digit of N expanding
93 each unit square to the base "+" shape.
94 +---C
96 D-------C | 2 |
97 | | D---+---+---+
98 | | => | 3 | 0 | 1 |
99 | | +---+---+---B
100 A-------B | 4 |
101 A---+
102 Side A-B becomes a 3-segment S. Such an expansion is the same as the
104 TerdragonCurve or GosperSide, but here turns of 90 degrees. Like
105 GosperSide there is no touching or overlap of the sides expansions, so
106 boundary length 4*3^level.
107 Rotate Numbering
109 Parameter "numbering_type => 'rotate'" applies a rotation to the
110 numbering in each sub-part according to its location around the
111 preceding level.
112 The effect can be illustrated by writing N in base-5. Part 10-14 is
114 the same as the middle 0-4. Part 20-24 has a rotation by +90 degrees.
115 Part 30-34 has rotation by +180 degrees, and part 40-44 by +270
116 degrees.
117 21
119 / |
120 22 20 24 12 numbering_type => 'rotate'
121 \ / / \ N shown in base-5
122 23 2 13 10--11
123 / \ \
124 34 3 0-- 1 14
125 \ \
126 31--30 33 4 41
127 \ / / \
128 32 43 40 42
129 | /
130 41
131 Notice this means in each part the 11, 21, 31, etc, points are directed
133 away from the middle in the same way, relative to the sub-part
134 locations.
135 Working through the expansions gives the following rule for when an N
137 is on the boundary of level k,
138 write N in base-5 digits (empty string if k=0)
140 if length < k then non-boundary
141 ignore high digit and all 1 digits
142 if any pair 32, 33, 44 then non-boundary
143 A 0 digit is the middle of a block, so always non-boundary. After that
145 the 4,1,2,3 parts variously expand with rotations so that a 44 is
146 enclosed on the clockwise side and 32 and 33 on the anti-clockwise
147 side.
148
150 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
151 classes.
152 "$path = Math::PlanePath::QuintetReplicate->new ()"
154 Create and return a new path object.
155 "($x,$y) = $path->n_to_xy ($n)"
157 Return the X,Y coordinates of point number $n on the path. Points
158 begin at 0 and if "$n < 0" then the return is an empty list.
159 Level Methods
161 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
162 Return "(0, 5**$level - 1)".
163
165 Axis Rotations
166 The digits positions 1,2,3,4 go around +90deg each, so the N for
167 rotation by +90 is each digit +1, cycling around.
168 rot+90(N) = 0, 2, 3, 4, 1, 10, 12, 13, 14, 11, 15, ... decimal
170 = 0, 2, 3, 4, 1, 20, 22, 23, 24, 21, 30, ... base5
171 rot-90(N) = 0, 4, 1, 2, 3, 20, 24, 21, 22, 23, 5, ... decimal
173 = 0, 4, 1, 2, 3, 40, 44, 41, 42, 43, 10, ... base5
174 rot180(N) = 0, 3, 4, 1, 2, 15, 18, 19, 16, 17, 20, ... decimal
176 = 0, 3, 4, 1, 2, 30, 33, 34, 31, 32, 40, ... base5
177 X,Y Extents
179 The maximum X in a given level N=0 to 5^k-1 can be calculated from the
180 replications. A given high digit 1 to 4 has sub-parts located at
181 b^k*i^(d-1). Those sub-parts are all the same, so the one with maximum
182 real(b^k*i^(d-1)) contains the maximum X.
183 N_xmax_digit(j) = d=1,2,3,4 where real(i^(d-1) * b^j) is maximum
185 = 1,1,4,4,4,4,3,3,3,2,2,2,1,1, ...
186 k-1
188 N_xmax(k) = digits N_xmax_digit(j) low digit j=0
189 j=0
190 = 0, 1, 6, 106, 606, 3106, 15606, ... decimal
191 = 0, 1, 11, 411, 4411, 44411, 444411, ... base5
192 k-1
194 z_xmax(k) = sum i^d[j] * b^j
195 j=0 each d[j] with real(i^d[j] * b^j) maximum
196 = 0, 1, 3+i, 7-2*i, 18-4*i, 42+3*i, 83+41*i, ...
197 xmax(k) = real(z_xmax(k))
199 = 0, 1, 3, 7, 18, 42, 83, 200, 478, 1005, ...
200 For computer calculation these maximums can be calculated by the
202 powers. The digit parts can also be written in terms of the angle
203 arg(b) = atan(1/2). For successive k, if adding atan(1/2) pushes the
204 b^k angle past +45deg then the preceding digit goes past -45deg and
205 becomes the new maximum X. Write the angle as a fraction of 90deg
206 (pi/2),
207 F = atan(1/2) / (pi/2) = 0.295167 ...
209 This is irrational since b^k is never on the X or Y axes. That can be
211 seen since imag(b^k) mod 5 == 1 if k odd and == 4 if k even >= 2.
212 Similarly real(b^k) mod 5 == 2,3 so not on the Y axis, or also anything
213 on the Y axis would have 3*k fall on the X axis.
214 Digits low to high successively step back in a cycle 4,3,2,1 so that
216 (with mod giving 0 to 3),
217 N_xmax_digit(j) = (-floor(F*j+1/2) mod 4) + 1
219 The +1/2 is since initial direction b^0=1 is angle 0 which is half way
221 between -45 and +45 deg.
222 Similarly the X,Y location, using -i for rotation back
224 z_xmax_exp(j) = floor(F*j+1/2)
226 = 0,0,1,1,1,1,2,2,2,3,3,3,4,4,4,4,5,5, ...
227 z_xmax(k) = sum(j=0,k-1, (-i)^z_xmax_exp(j) * b^j)
228 By symmetry the maximum extent is the same for Y vertically and for X
230 or Y negative, suitably rotated. The N in those cases has the digits
231 1,2,3,4 cycled around as per "Axis Rotations" above.
232 If the +1/2 in the floor is omitted then the effect is to find the
234 maximum point in direction +45deg, so the point(s) with maximum sum S =
235 X+Y.
236 N_smax_digit(j) = (-floor(F*j) mod 4) + 1
238 = 1,1,1,1,4,4,4,3,3,3,3,2,2,2,1, ...
239 k-1
241 N_smax(k) = digits N_smax_digit(j) low digit j=0
242 j=0
243 = 0, 1, 6, 31, 156, 2656, 15156, ... decimal
244 = 0, 1, 11, 111, 1111, 41111, 441111, ... base5
245 and also N_smax() + 1
246 z_smax_exp(j) = floor(F*j)
248 = 0,0,0,0,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5, ...
249 z_smax(k) = sum(j=0,k-1, (-i)^z_smax_exp(j) * b^j)
250 = 0, 1, 3+i, 6+5*i, 8+16*i, 32+23*i, 73+61*i, ...
251 and also z_smax() + 1+i
252 smax(k) = real(z_smax(k)) + imag(z_smax(k))
254 = 0, 1, 4, 11, 24, 55, 134, 295, 602, 1465, ...
255 In the base figure points 1 and 2 are both on the same 45deg line and
257 this remains so in subsequent levels, so that for k>=1 N_smax(k) and
258 N_smax(k)+1 are equal maximums.
259
261 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
262 this path include
263 <http://oeis.org/A316657> (etc)
265 A316657 X coordinate
267 A316658 Y coordinate
268 A316707 norm X^2 + Y^2
269
271 Math::PlanePath, Math::PlanePath::QuintetCurve,
272 Math::PlanePath::ComplexMinus, Math::PlanePath::GosperReplicate
273
275 <http://user42.tuxfamily.org/math-planepath/index.html>
276
278 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020,
279 2021 Kevin Ryde
280 Math-PlanePath is free software; you can redistribute it and/or modify
282 it under the terms of the GNU General Public License as published by
283 the Free Software Foundation; either version 3, or (at your option) any
284 later version.
285 Math-PlanePath is distributed in the hope that it will be useful, but
287 WITHOUT ANY WARRANTY; without even the implied warranty of
288 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
289 General Public License for more details.
290 You should have received a copy of the GNU General Public License along
292 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
293perl v5.32.1 2021-01-2M7ath::PlanePath::QuintetReplicate(3)