1Math::PlanePath::R5DragUosneCrurCvoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::R5DragonCurve(3)
2
6 Math::PlanePath::R5DragonCurve -- radix 5 dragon curve
7
9 use Math::PlanePath::R5DragonCurve;
10 my $path = Math::PlanePath::R5DragonCurve->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path is a "DDUU" turn pattern similar in nature to the terdragon
15 but on a square grid and with 5 segments instead of 3.
16 31-----30 27-----26 5
18 | | | |
19 32---29/33--28/24----25 4
20 | |
21 35---34/38--39/23----22 11-----10 7------6 3
22 | | | | | | |
23 36---37/41--20/40--21/17--16/12---13/9----8/4-----5 2
24 | | | | | |
25 --50 47---42/46--19/43----18 15-----14 3------2 1
26 | | | | |
27 49/53--48/64 45/65--44/68 69 0------1 <-Y=0
28 ^ ^ ^ ^ ^ ^ ^ ^ ^
30 -7 -6 -5 -4 -3 -2 -1 X=0 1
31 The name "R5" is by Jorg Arndt. The base figure is an "S" shape
33 4----5
35 |
36 3----2
37 |
38 0----1
39 which then repeats in self-similar style, so N=5 to N=10 is a copy
41 rotated +90 degrees, as per the direction of the N=1 to N=2 segment.
42 10 7----6
44 | | | <- repeat rotated +90
45 9---8,4---5
46 |
47 3----2
48 |
49 0----1
50 Like the terdragon there are no reversals or mirroring. Each
52 replication is the plain base curve.
53 The shape of N=0,5,10,15,20,25 repeats the initial N=0 to N=5,
55 25 4
57 /
58 / 10__ 3
59 / / ----___
60 20__ / 5 2
61 ----__ / /
62 15 / 1
63 /
64 0 <-Y=0
65 ^ ^ ^ ^ ^ ^
67 -4 -3 -2 -1 X=0 1
68 The curve never crosses itself. The vertices touch at corners like N=4
70 and N=8 above, but no edges repeat.
71 Spiralling
73 The first step N=1 is to the right along the X axis and the path then
74 slowly spirals anti-clockwise and progressively fatter. The end of
75 each replication is
76 Nlevel = 5^level
78 Each such point is at arctan(2/1)=63.43 degrees further around from the
80 previous,
81 Nlevel X,Y angle (degrees)
83 ------ ----- -----
84 1 1,0 0
85 5 2,1 63.4
86 25 -3,4 2*63.4 = 126.8
87 125 -11,-2 3*63.4 = 190.3
88 Arms
90 The curve fills a quarter of the plane and four copies mesh together
91 perfectly rotated by 90, 180 and 270 degrees. The "arms" parameter can
92 choose 1 to 4 such curve arms successively advancing.
93 "arms => 4" begins as follows. N=0,4,8,12,16,etc is the first arm (the
95 same shape as the plain curve above), then N=1,5,9,13,17 the second,
96 N=2,6,10,14 the third, etc.
97 arms => 4
99 16/32---20/63
100 |
101 21/60 9/56----5/12----8/59
102 | | | |
103 17/33--- 6/13--0/1/2/3---4/15---19/35
104 | | | |
105 10/57----7/14---11/58 23/62
106 |
107 22/61---18/34
108 With four arms every X,Y point is visited twice, except the origin 0,0
110 where all four begin. Every edge between the points is traversed once.
111 Tiling
113 The little "S" shapes of the N=0to5 base shape tile the plane with 2x1
114 bricks and 1x1 holes in the following pattern,
115 +--+-----| |--+--+-----| |--+--+---
117 | | | | | | | | | |
118 | |-----+-----| |-----+-----| |---
119 | | | | | | | | | | |
120 +-----| |-----+-----| |-----+-----+
121 | | | | | | | | | |
122 +-----+-----| |-----+-----| |-----+
123 | | | | | | | | | | |
124 ---| |-----+-----| |-----+-----| |
125 | | | | | | | | | |
126 ---+-----| |-----o-----| |-----+---
127 | | | | | | | | | |
128 | |-----+-----| |-----+-----| |---
129 | | | | | | | | | | |
130 +-----| |-----+-----| |-----+-----+
131 | | | | | | | | | |
132 +-----+-----| |-----+-----| |-----+
133 | | | | | | | | | | |
134 ---| |-----+-----| |-----+-----| |
135 | | | | | | | | | |
136 ---+--+--| |-----+--+--| |-----+--+
137 This is the curve with each segment N=2mod5 to N=3mod5 omitted. A 2x1
139 block has 6 edges but the "S" traverses just 4 of them. The way the
140 blocks mesh meshes together mean the other 2 edges are traversed by
141 another brick, possibly a brick on another arm of the curve.
142 This tiling is also found for example at
144 <http://tilingsearch.org/HTML/data182/AL04.html>
146 Or with enlarged square part,
148 <http://tilingsearch.org/HTML/data149/L3010.html>
149
151 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
152 classes.
153 "$path = Math::PlanePath::R5DragonCurve->new ()"
155 "$path = Math::PlanePath::R5DragonCurve->new (arms => 4)"
156 Create and return a new path object.
157 The optional "arms" parameter can make 1 to 4 copies of the curve,
159 each arm successively advancing.
160 "($x,$y) = $path->n_to_xy ($n)"
162 Return the X,Y coordinates of point number $n on the path. Points
163 begin at 0 and if "$n < 0" then the return is an empty list.
164 Fractional $n gives an X,Y position along a straight line between
166 the integer positions.
167 "$n = $path->xy_to_n ($x,$y)"
169 Return the point number for coordinates "$x,$y". If there's
170 nothing at "$x,$y" then return "undef".
171 The curve can visit an "$x,$y" twice. The smallest of the these N
173 values is returned.
174 "@n_list = $path->xy_to_n_list ($x,$y)"
176 Return a list of N point numbers for coordinates "$x,$y".
177 The origin 0,0 has "arms_count()" many N since it's the starting
179 point for each arm. Other points have up to two Ns for a given
180 "$x,$y". If arms=4 then every "$x,$y" except the origin has
181 exactly two Ns.
182 "$n = $path->n_start()"
184 Return 0, the first N in the path.
185 Level Methods
187 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
188 Return "(0, 5**$level)", or for multiple arms return "(0, $arms *
189 5**$level + ($arms-1))".
190 There are 5^level segments in a curve level, so 5^level+1 points
192 numbered from 0. For multiple arms there are arms*(5^level+1)
193 points, numbered from 0 so n_hi = arms*(5^level+1)-1.
194
196 Various formulas for boundary length, area, and more, can be found in
197 the author's mathematical write-up
198 <http://user42.tuxfamily.org/r5dragon/index.html>
200 Turn
202 At each point N the curve always turns 90 degrees either to the left or
203 right, it never goes straight ahead. As per the code in Jorg Arndt's
204 fxtbook, if N is written in base 5 then the lowest non-zero digit gives
205 the turn
206 lowest non-0 digit turn
208 ------------------ ----
209 1 left
210 2 left
211 3 right
212 4 right
213 At a point N=digit*5^level for digit=1,2,3,4 the turn follows the shape
215 at that digit, so two lefts then two rights,
216 4*5^k----5^(k+1)
218 |
219 |
220 2*5^k----2*5^k
221 |
222 |
223 0------1*5^k
224 The first and last unit segments in each level are the same direction,
226 so at those endpoints it's the next level up which gives the turn.
227 Next Turn
229 The turn at N+1 can be calculated in a similar way but from the lowest
230 non-4 digit.
231 lowest non-4 digit turn
233 ------------------ ----
234 0 left
235 1 left
236 2 right
237 3 right
238 This works simply because in N=...z444 becomes N+1=...(z+1)000 and so
240 the turn at N+1 is given by digit z+1.
241 Total Turn
243 The direction at N, ie. the total cumulative turn, is given by the
244 direction of each digit when N is written in base 5,
245 digit direction
247 0 0
248 1 1
249 2 2
250 3 1
251 4 0
252 direction = (sum direction for each digit) * 90 degrees
254 For example N=13 in base 5 is "23" so digit=2 direction=2 plus digit=3
256 direction=1 gives direction=(2+1)*90 = 270 degrees, ie. south.
257 Because there's no reversals etc in the replications there's no state
259 to maintain when considering the digits, just a plain sum of direction
260 for each digit.
261
263 The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences
264 as,
265 <http://oeis.org/A175337> (etc)
267 A175337 next turn 0=left,1=right
269 (n=0 is the turn at N=1)
270 A006495 level end X, Re(b^k)
272 A006496 level end Y, Re(b^k)
273 A079004 boundary length N=0 to 5^k, skip initial 7,10
275 being 4*3^k - 2
276 A048473 boundary/2 (one side), N=0 to 5^k
278 being half whole, 2*3^n - 1
279 A198859 boundary/2 (one side), N=0 to 25^k
280 being even levels, 2*9^n - 1
281 A198963 boundary/2 (one side), N=0 to 5*25^k
282 being odd levels, 6*9^n - 1
283 A052919,A100702 U part boundary length, N=0 to 5^k
285 A007798 1/2 * area enclosed N=0 to 5^k
287 A016209 1/4 * area enclosed N=0 to 5^k
288 A005058 1/2 * new area N=5^k to N=5^(k+1)
290 being area increments, 5^n - 3^n
291 A005059 1/4 * new area N=5^k to N=5^(k+1)
292 being area increments, (5^n - 3^n)/2
293 A125831 N middle segment of level k, (5^k-1)/2
295 A008776 count single-visited points N=0 to 5^k, being 2*3^k
296 A146086 count visited points N=0 to 5^k
297 A024024 C[k] boundary lengths, 3^k-k
299 A104743 E[k] boundary lengths, 3^k+k
300 A135518 1/4 * sum distinct abs(n-other(n)) in level N=0 to 5^k
302 arms=1 and arms=3
304 A059841 abs(dX), being simply 1,0 repeating
305 A000035 abs(dY), being simply 0,1 repeating
306 arms=4
308 A165211 abs(dY), being 0,1,0,1,1,0,1,0 repeating
309
311 House of Graphs entries for the R5 dragon curve as a graph include
312 level=2, <https://hog.grinvin.org/ViewGraphInfo.action?id=25149>
314 level=3, <https://hog.grinvin.org/ViewGraphInfo.action?id=25147>
315
317 Math::PlanePath, Math::PlanePath::DragonCurve,
318 Math::PlanePath::TerdragonCurve
319
321 <http://user42.tuxfamily.org/math-planepath/index.html>
322
324 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
325 This file is part of Math-PlanePath.
327 Math-PlanePath is free software; you can redistribute it and/or modify
329 it under the terms of the GNU General Public License as published by
330 the Free Software Foundation; either version 3, or (at your option) any
331 later version.
332 Math-PlanePath is distributed in the hope that it will be useful, but
334 WITHOUT ANY WARRANTY; without even the implied warranty of
335 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
336 General Public License for more details.
337 You should have received a copy of the GNU General Public License along
339 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
340perl v5.30.0 2019-08-17 Math::PlanePath::R5DragonCurve(3)