1Math::PlanePath::DragonURsoeurndCeodn(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::DragonRounded(3)
2
3
4
6 Math::PlanePath::DragonRounded -- dragon curve, with rounded corners
7
9 use Math::PlanePath::DragonRounded;
10 my $path = Math::PlanePath::DragonRounded->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is a version of the dragon curve by Harter, Heighway, et al, done
15 with two points per edge and skipping vertices so as to make rounded-
16 off corners,
17
18 17-16 9--8 6
19 / \ / \
20 18 15 10 7 5
21 | | | |
22 19 14 11 6 4
23 \ \ / \
24 20-21 13-12 5--4 3
25 \ \
26 22 3 2
27 | |
28 23 2 1
29 / /
30 33-32 25-24 . 0--1 Y=0
31 / \ /
32 34 31 26 -1
33 | | |
34 35 30 27 -2
35 \ \ /
36 36-37 29-28 44-45 -3
37 \ / \
38 38 43 46 -4
39 | | |
40 39 42 47 -5
41 \ / /
42 40-41 49-48 -6
43 /
44 50 -7
45 |
46 ...
47
48
49 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
50 -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 ...
51
52 The two points on an edge have one of X or Y a multiple of 3 and the
53 other Y or X at 1 mod 3 or 2 mod 3. For example N=19 and N=20 are on
54 the X=-9 edge (a multiple of 3), and at Y=4 and Y=5 (1 and 2 mod 3).
55
56 The "rounding" of the corners ensures that for example N=13 and N=21
57 don't touch as they approach X=-6,Y=3. The curve always approaches
58 vertices like this and never crosses itself.
59
60 Arms
61 The dragon curve fills a quarter of the plane and four copies mesh
62 together rotated by 90, 180 and 270 degrees. The "arms" parameter can
63 choose 1 to 4 curve arms, successively advancing. For example "arms =>
64 4" gives
65
66 36-32 59-... 6
67 / \ /
68 ... 40 28 55 5
69 | | | |
70 56 44 24 51 4
71 \ / \ \
72 52-48 13--9 20-16 47-43 3
73 / \ \ \
74 17 5 12 39 2
75 | | | |
76 21 1 8 35 1
77 / / /
78 29-25 6--2 0--4 27-31 <- Y=0
79 / / /
80 33 10 3 23 -1
81 | | | |
82 37 14 7 19 -2
83 \ \ \ /
84 41-45 18-22 11-15 50-54 -3
85 \ \ / \
86 49 26 46 58 -4
87 | | | |
88 53 30 42 ... -5
89 / \ /
90 ...-57 34-38 -6
91
92
93
94 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
95 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6
96
97 With 4 arms like this all 3x3 blocks are visited, using 4 out of 9
98 points in each.
99
100 Midpoint
101 The points of this rounded curve correspond to the "DragonMidpoint"
102 with a little squish to turn each 6x6 block into a 4x4 block. For
103 instance in the following N=2,3 are pushed to the left, and N=6 through
104 N=11 shift down and squashes up horizontally.
105
106 DragonRounded DragonMidpoint
107
108 9--8
109 / \
110 10 7 9---8
111 | | | |
112 11 6 10 7
113 / \ | |
114 5--4 <=> -11 6---5---4
115 \ |
116 3 3
117 | |
118 2 2
119 / |
120 . 0--1 0---1
121
123 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
124 classes.
125
126 "$path = Math::PlanePath::DragonRounded->new ()"
127 "$path = Math::PlanePath::DragonRounded->new (arms => $aa)"
128 Create and return a new path object.
129
130 The optional "arms" parameter makes a multi-arm curve. The default
131 is 1 for just one arm.
132
133 "($x,$y) = $path->n_to_xy ($n)"
134 Return the X,Y coordinates of point number $n on the path. Points
135 begin at 0 and if "$n < 0" then the return is an empty list.
136
137 "$n = $path->n_start()"
138 Return 0, the first N in the path.
139
140 Level Methods
141 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
142 Return "(0, 2 * 2**$level - 1)", or for multiple arms return "(0,
143 $arms * 2 * 2**$level - 1)".
144
145 There are 2^level segments comprising the dragon, or arms*2^level
146 when multiple arms. Each has 2 points in this rounded curve,
147 numbered starting from 0.
148
150 X,Y to N
151 The correspondence with the "DragonMidpoint" noted above allows the
152 method from that module to be used for the rounded "xy_to_n()".
153
154 The correspondence essentially reckons each point on the rounded curve
155 as the midpoint of a dragon curve of one greater level of detail, and
156 segments on 45-degree angles.
157
158 The coordinate conversion turns each 6x6 block of "DragonRounded" to a
159 4x4 block of "DragonMidpoint". There's no rotations or anything.
160
161 Xmid = X - floor(X/3) - Xadj[X%6][Y%6]
162 Ymid = Y - floor(Y/3) - Yadj[X%6][Y%6]
163
164 N = DragonMidpoint n_to_xy of Xmid,Ymid
165
166 Xadj[][] is a 6x6 table of 0 or 1 or undef
167 Yadj[][] is a 6x6 table of -1 or 0 or undef
168
169 The Xadj,Yadj tables are a handy place to notice X,Y points not on the
170 "DragonRounded" style 4 of 9 points. Or 16 of 36 points since the
171 tables are 6x6.
172
174 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
175 this path include the various "DragonCurve" sequences at even N, and in
176 addition
177
178 <http://oeis.org/A152822> (etc)
179
180 A152822 abs(dX), so 0=vertical,1=not, being 1,1,0,1 repeating
181 A166486 abs(dY), so 0=horizontal,1=not, being 0,1,1,1 repeating
182
184 Math::PlanePath, Math::PlanePath::DragonCurve,
185 Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonRounded
186
188 <http://user42.tuxfamily.org/math-planepath/index.html>
189
191 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
192
193 Math-PlanePath is free software; you can redistribute it and/or modify
194 it under the terms of the GNU General Public License as published by
195 the Free Software Foundation; either version 3, or (at your option) any
196 later version.
197
198 Math-PlanePath is distributed in the hope that it will be useful, but
199 WITHOUT ANY WARRANTY; without even the implied warranty of
200 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
201 General Public License for more details.
202
203 You should have received a copy of the GNU General Public License along
204 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
205
206
207
208perl v5.28.1 2017-12-03 Math::PlanePath::DragonRounded(3)