1Math::PlanePath::R5DragUosneCrurCvoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::R5DragonCurve(3)
2
3
4

NAME

6       Math::PlanePath::R5DragonCurve -- radix 5 dragon curve
7

SYNOPSIS

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

DESCRIPTION

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
17                    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
29              ^      ^      ^      ^      ^      ^      ^      ^      ^
30             -7     -6     -5     -4     -3     -2     -1     X=0     1
31
32       The name "R5" is by Jorg Arndt.  The base figure is an "S" shape
33
34           4----5
35           |
36           3----2
37                |
38           0----1
39
40       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
43           10    7----6
44            |    |    |  <- repeat rotated +90
45            9---8,4---5
46                 |
47                 3----2
48                      |
49                 0----1
50
51       Like the terdragon there are no reversals or mirroring.  Each
52       replication is the plain base curve.
53
54       The shape of N=0,5,10,15,20,25 repeats the initial N=0 to N=5,
55
56                  25                          4
57                 /
58                /           10__              3
59               /           /    ----___
60             20__         /            5      2
61                 ----__  /            /
62                       15            /        1
63                                   /
64                                  0       <-Y=0
65
66              ^    ^    ^    ^    ^    ^
67             -4   -3   -2   -1   X=0   1
68
69       The curve never crosses itself.  The vertices touch at corners like N=4
70       and N=8 above, but no edges repeat.
71
72   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
77           Nlevel = 5^level
78
79       Each such point is at arctan(2/1)=63.43 degrees further around from the
80       previous,
81
82           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
89   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
94       "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
98           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
109       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
112   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
116           +--+-----|  |--+--+-----|  |--+--+---
117           |  |     |  |  |  |     |  |  |  |
118           |  |-----+-----|  |-----+-----|  |---
119           |  |  |  |     |  |  |  |     |  |  |
120           +-----|  |-----+-----|  |-----+-----+
121           |     |  |  |  |     |  |  |  |     |
122           +-----+-----|  |-----+-----|  |-----+
123           |  |  |     |  |  |  |     |  |  |  |
124           ---|  |-----+-----|  |-----+-----|  |
125              |  |  |  |     |  |  |  |     |  |
126           ---+-----|  |-----o-----|  |-----+---
127           |  |     |  |  |  |     |  |  |  |
128           |  |-----+-----|  |-----+-----|  |---
129           |  |  |  |     |  |  |  |     |  |  |
130           +-----|  |-----+-----|  |-----+-----+
131           |     |  |  |  |     |  |  |  |     |
132           +-----+-----|  |-----+-----|  |-----+
133           |  |  |     |  |  |  |     |  |  |  |
134           ---|  |-----+-----|  |-----+-----|  |
135              |  |  |  |     |  |  |  |     |  |
136           ---+--+--|  |-----+--+--|  |-----+--+
137
138       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
143       This tiling is also found for example at
144
145           <http://tilingsearch.org/HTML/data182/AL04.html>
146
147           Or with enlarged square part,
148           <http://tilingsearch.org/HTML/data149/L3010.html>
149

FUNCTIONS

151       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
152       classes.
153
154       "$path = Math::PlanePath::R5DragonCurve->new ()"
155       "$path = Math::PlanePath::R5DragonCurve->new (arms => 4)"
156           Create and return a new path object.
157
158           The optional "arms" parameter can make 1 to 4 copies of the curve,
159           each arm successively advancing.
160
161       "($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
165           Fractional $n gives an X,Y position along a straight line between
166           the integer positions.
167
168       "$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
172           The curve can visit an "$x,$y" twice.  The smallest of the these N
173           values is returned.
174
175       "@n_list = $path->xy_to_n_list ($x,$y)"
176           Return a list of N point numbers for coordinates "$x,$y".
177
178           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
183       "$n = $path->n_start()"
184           Return 0, the first N in the path.
185
186   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
191           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

FORMULAS

196       Various formulas for boundary length, area, and more, can be found in
197       the author's mathematical write-up
198
199           <http://user42.tuxfamily.org/r5dragon/index.html>
200
201   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
207           lowest non-0 digit     turn
208           ------------------     ----
209                   1              left
210                   2              left
211                   3              right
212                   4              right
213
214       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
217           4*5^k----5^(k+1)
218            |
219            |
220           2*5^k----2*5^k
221                     |
222                     |
223            0------1*5^k
224
225       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
228   Next Turn
229       The turn at N+1 can be calculated in a similar way but from the lowest
230       non-4 digit.
231
232           lowest non-4 digit     turn
233           ------------------     ----
234                   0              left
235                   1              left
236                   2              right
237                   3              right
238
239       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
242   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
246           digit       direction
247             0             0
248             1             1
249             2             2
250             3             1
251             4             0
252
253           direction = (sum direction for each digit) * 90 degrees
254
255       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
258       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

OEIS

263       The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences
264       as,
265
266           <http://oeis.org/A175337> (etc)
267
268           A175337    next turn 0=left,1=right
269                        (n=0 is the turn at N=1)
270
271           A006495    level end X, Re(b^k)
272           A006496    level end Y, Re(b^k)
273
274           A079004    boundary length N=0 to 5^k, skip initial 7,10
275                        being 4*3^k - 2
276
277           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
284           A052919,A100702  U part boundary length, N=0 to 5^k
285
286           A007798    1/2 * area enclosed N=0 to 5^k
287           A016209    1/4 * area enclosed N=0 to 5^k
288
289           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
294           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
298           A024024    C[k] boundary lengths, 3^k-k
299           A104743    E[k] boundary lengths, 3^k+k
300
301           A135518    1/4 * sum distinct abs(n-other(n)) in level N=0 to 5^k
302
303           arms=1 and arms=3
304             A059841    abs(dX), being simply 1,0 repeating
305             A000035    abs(dY), being simply 0,1 repeating
306
307           arms=4
308             A165211    abs(dY), being 0,1,0,1,1,0,1,0 repeating
309

HOUSE OF GRAPHS

311       House of Graphs entries for the R5 dragon curve as a graph include
312
313       level=2, <https://hog.grinvin.org/ViewGraphInfo.action?id=25149>
314       level=3, <https://hog.grinvin.org/ViewGraphInfo.action?id=25147>
315

SEE ALSO

317       Math::PlanePath, Math::PlanePath::DragonCurve,
318       Math::PlanePath::TerdragonCurve
319

HOME PAGE

321       <http://user42.tuxfamily.org/math-planepath/index.html>
322

LICENSE

324       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
325
326       This file is part of Math-PlanePath.
327
328       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
333       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
338       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/>.
340
341
342
343perl v5.30.0                      2019-08-17 Math::PlanePath::R5DragonCurve(3)
Impressum