1Math::PlanePath::AlternUasteerTeCrodnrtargiobnu(t3e)d PeMralthD:o:cPulmaennetPaattiho:n:AlternateTerdragon(3)
2
6 Math::PlanePath::AlternateTerdragon -- alternate terdragon curve
7
9 use Math::PlanePath::AlternateTerdragon;
10 my $path = Math::PlanePath::AlternateTerdragon->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is the alternate terdragon curve by Davis and Knuth,
15 Chandler Davis and Donald Knuth, "Number Representations and Dragon
17 Curves -- I", Journal Recreational Mathematics, volume 3, number 2
18 (April 1970), pages 66-81 and "Number Representations and Dragon
19 Curves -- II", volume 3, number 3 (July 1970), pages 133-149.
20 Reprinted with addendum in Knuth "Selected Papers on Fun and
22 Games", 2010, pages 571--614.
23 <http://www-cs-faculty.stanford.edu/~uno/fg.html>
24 Points are a triangular grid using every second integer X,Y as per
26 "Triangular Lattice" in Math::PlanePath, beginning
27 \ / \ /
29 Y=2 14,17 --- 15,24,33 --
30 \ / \
31 \ / \ /
32 Y=1 2 ------- 3,12 ---- 10,13,34 -- 32,35,38
33 \ / \ / \ / \
34 \ / \ / \ /
35 Y=0 0 -------- 1,4 ----- 5,8,11 ----- 9,36 ----
36 / \
37 / \
38 Y=-1 6 --------- 7
39 ^ ^ ^ ^ ^ ^ ^ ^
41 X=0 1 2 3 4 5 6 7
42 A segment 0 to 1 is unfolded to
44 2-----3
46 \
47 \
48 0-----1
49 Then 0 to 3 is unfolded likewise, but the folds are the opposite way.
51 Where 1-2 went on the left, for 3-6 goes to the right.
52 2-----3 2-----3
54 \ / \ /
55 \ / \ /
56 0----1,4----5 0----1,4---5,8----9
57 / / \
58 / / \
59 6 6-----7
60 Successive unfolds go alternate ways. Taking two unfold at a time is
62 segment replacement by the 0 to 9 figure (rotated as necessary). The
63 curve never crosses itself. Vertices touch at triangular corners.
64 Points can be visited 1, 2 or 3 times.
65 The two triangles have segment 4-5 between. In general points to a
67 level N=3^k have a single segment between two blobs, for example N=0 to
68 N=3^6=729 below. But as the curve continues it comes back to put
69 further segments there (and a single segment between bigger blobs).
70 * *
72 * * * *
73 * * * *
74 * * * * * * *
75 * * * * * * * * * *
76 * * * * * * * * * *
77 * * * * * * * * * *
78 * * * * * * * * * * *
79 * * * * * * * * * *
80 * * * * * * * * * * * * * * *
81 * * * * * * * * * * * * * * * * *
82 * * * * * * * * * * * * * * * * *
83 * * * * * * * * * * * * * * * * * * * * * * *
84 O * * * * * * * * * * * * * * * * * * * * * * * * * * E
85 * * * * * * * * * * * * * * * * * * * * * * *
86 * * * * * * * * * * * * * * * * *
87 * * * * * * * * * * * * * * * * *
88 * * * * * * * * * * * * * * *
89 * * * * * * * * * *
90 * * * * * * * * * * *
91 * * * * * * * * * *
92 * * * * * * * * * *
93 * * * * * * * * * *
94 * * * * * * *
95 * * * *
96 * * * *
97 * *
98 The top boundary extent is at an angle +60 degrees and the bottom at
100 -30 degrees,
101 / 60 deg
103 /
104 /
105 O-------------------
106 --__
107 --__ 30 deg
108 An even expansion level is within a rectangle with endpoint at
110 X=2*3^(k/2),Y=0.
111 Arms
113 The curve fills a sixth of the plane and six copies rotated by 60, 120,
114 180, 240 and 300 degrees mesh together perfectly. The "arms" parameter
115 can choose 1 to 6 such curve arms successively advancing.
116 For example "arms => 6" begins as follows. N=0,6,12,18,etc is the
118 first arm (the same shape as the plain curve above), then N=1,7,13,19
119 the second, N=2,8,14,20 the third, etc.
120 \ / \ /
122 \ / \ /
123 --- 7,8,26 ----------------- 1,12,19 ---
124 / \ / \
125 \ / \ / \ /
126 \ / \ / \ /
127 --- 3,14,21 ------------- 0,1,2,3,4,5 -------------- 6,11,24 ---
128 / \ / \ / \
129 / \ / \ / \
130 \ / \ /
131 ---- 9,10,28 ---------------- 5,16,23 ---
132 / \ / \
133 / \ / \
134 With six arms every X,Y point is visited three times, except the origin
136 0,0 where all six begin. Every edge between points is traversed once.
137
139 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
140 classes.
141 "$path = Math::PlanePath::AlternateTerdragon->new ()"
143 "$path = Math::PlanePath::AlternateTerdragon->new (arms => 6)"
144 Create and return a new path object.
145 The optional "arms" parameter can make 1 to 6 copies of the curve,
147 each arm successively advancing.
148 "($x,$y) = $path->n_to_xy ($n)"
150 Return the X,Y coordinates of point number $n on the path. Points
151 begin at 0 and if "$n < 0" then the return is an empty list.
152 Fractional positions give an X,Y position along a straight line
154 between the integer positions.
155 "$n = $path->xy_to_n ($x,$y)"
157 Return the point number for coordinates "$x,$y". If there's
158 nothing at "$x,$y" then return "undef".
159 The curve can visit an "$x,$y" up to three times. "xy_to_n()"
161 returns the smallest of the these N values.
162 "@n_list = $path->xy_to_n_list ($x,$y)"
164 Return a list of N point numbers for coordinates "$x,$y".
165 The origin 0,0 has "arms_count()" many N since it's the starting
167 point for each arm. Other points have up to 3 Ns for a given
168 "$x,$y". If arms=6 then every even "$x,$y" except the origin has
169 exactly 3 Ns.
170 Descriptive Methods
172 "$n = $path->n_start()"
173 Return 0, the first N in the path.
174 "$dx = $path->dx_minimum()"
176 "$dx = $path->dx_maximum()"
177 "$dy = $path->dy_minimum()"
178 "$dy = $path->dy_maximum()"
179 The dX,dY values on the first arm take three possible combinations,
180 being 120 degree angles.
181 dX,dY for arms=1
183 -----
184 2, 0 dX minimum = -1, maximum = +2
185 -1, 1 dY minimum = -1, maximum = +1
186 1,-1
187 For 2 or more arms the second arm is rotated by 60 degrees so
189 giving the following additional combinations, for a total six.
190 This changes the dX minimum.
191 dX,dY for arms=2 or more
193 -----
194 -2, 0 dX minimum = -2, maximum = +2
195 1, 1 dY minimum = -1, maximum = +1
196 -1,-1
197 "$sum = $path->sumxy_minimum()"
199 "$sum = $path->sumxy_maximum()"
200 Return the minimum or maximum values taken by coordinate sum X+Y
201 reached by integer N values in the path. If there's no minimum or
202 maximum then return "undef".
203 S=X+Y is an anti-diagonal. The first arm is entirely above a line
205 135deg -- -45deg, per the +60deg to -30deg extents shown above.
206 Likewise the second arm which is to 60+60=120deg. They have
207 "sumxy_minimum = 0". More arms and all "sumxy_maximum" are
208 unbounded so "undef".
209 "$diffxy = $path->diffxy_minimum()"
211 "$diffxy = $path->diffxy_maximum()"
212 Return the minimum or maximum values taken by coordinate difference
213 X-Y reached by integer N values in the path. If there's no minimum
214 or maximum then return "undef".
215 D=X-Y is a leading diagonal. The first arm is entirely right of a
217 line 45deg -- -135deg, per the +60deg to -30deg extents shown
218 above, so it has "diffxy_minimum = 0". More arms and all
219 "diffxy_maximum" are unbounded so "undef".
220 Level Methods
222 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
223 Return "(0, 3**$level)", or for multiple arms return "(0, $arms *
224 3**$level + ($arms-1))".
225 There are 3^level segments in a curve level, so 3^level+1 points
227 numbered from 0. For multiple arms there are arms*(3^level+1)
228 points, numbered from 0 so n_hi = arms*(3^level+1)-1.
229
231 Turn
232 At each point N the curve always turns 120 degrees either to the left
233 or right, it never goes straight ahead. If N is written in ternary
234 then the lowest non-zero digit at its position gives the turn.
235 Positions are counted from 0 for the least significant digit and up
236 from there.
237 turn ternary lowest non-zero digit
239 ----- ---------------------------------------
240 left 1 at even position or 2 at odd position
241 right 2 at even position or 1 at odd position
242 The flip of turn at odd positions is the "alternating" in the curve.
244 next turn ternary lowest non-2 digit
246 --------- ---------------------------------------
247 left 0 at even position or 1 at odd position
248 right 1 at even position or 0 at odd position
249 Total Turn
251 The direction at N, ie. the total cumulative turn, is given by the 1
252 digits of N written in ternary.
253 direction = 120deg * sum / +1 if digit=1 at even position
255 \ -1 if digit=1 at odd position
256 This is used mod 3 for "n_to_dxdy()".
258 X,Y to N
260 The current code is roughly the same as "TerdragonCurve" "xy_to_n()",
261 but with a conjugate (negate Y, reverse direction d) after each digit
262 low to high.
263 X,Y Visited
265 When arms=6 all "even" points of the plane are visited. As per the
266 triangular representation of X,Y this means
267 X+Y mod 2 == 0 "even" points
269
271 Sequences in Sloane's Online Encyclopedia of Integer Sequences related
272 to the alternate terdragon include,
273 <http://oeis.org/A156595> (etc)
275 A156595 next turn 0=left, 1=right (morphism)
277 A189715 N positions of left turns
278 A189716 N positions of right turns
279 A189717 count right turns so far
280
282 Math::PlanePath, Math::PlanePath::TerdragonCurve
283 Math::PlanePath::DragonCurve, Math::PlanePath::AlternatePaper
285
287 <http://user42.tuxfamily.org/math-planepath/index.html>
288
290 Copyright 2018 Kevin Ryde
291 This file is part of Math-PlanePath.
293 Math-PlanePath is free software; you can redistribute it and/or modify
295 it under the terms of the GNU General Public License as published by
296 the Free Software Foundation; either version 3, or (at your option) any
297 later version.
298 Math-PlanePath is distributed in the hope that it will be useful, but
300 WITHOUT ANY WARRANTY; without even the implied warranty of
301 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
302 General Public License for more details.
303 You should have received a copy of the GNU General Public License along
305 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
306perl v5.32.0 2020-07M-a2t8h::PlanePath::AlternateTerdragon(3)