1Math::PlanePath::AlternUasteerTeCrodnrtargiobnu(t3e)d PeMralthD:o:cPulmaennetPaattiho:n:AlternateTerdragon(3)
2
3
4

NAME

6       Math::PlanePath::AlternateTerdragon -- alternate terdragon curve
7

SYNOPSIS

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

DESCRIPTION

14       This is the alternate terdragon curve by Davis and Knuth,
15
16           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
21           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
25       Points are a triangular grid using every second integer X,Y as per
26       "Triangular Lattice" in Math::PlanePath, beginning
27
28                                        \   /       \   /
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
40                  ^     ^     ^     ^     ^     ^     ^     ^
41                 X=0    1     2     3     4     5     6     7
42
43       A segment 0 to 1 is unfolded to
44
45              2-----3
46               \
47                \
48           0-----1
49
50       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
53              2-----3                   2-----3
54               \   /                     \   /
55                \ /                       \ /
56           0----1,4----5             0----1,4---5,8----9
57                      /                         / \
58                     /                         /   \
59                    6                         6-----7
60
61       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
66       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
71                        * *
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
99       The top boundary extent is at an angle +60 degrees and the bottom at
100       -30 degrees,
101
102              / 60 deg
103             /
104            /
105           O-------------------
106            --__
107                --__ 30 deg
108
109       An even expansion level is within a rectangle with endpoint at
110       X=2*3^(k/2),Y=0.
111
112   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
117       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
121                         \         /             \           /
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
135       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

FUNCTIONS

139       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
140       classes.
141
142       "$path = Math::PlanePath::AlternateTerdragon->new ()"
143       "$path = Math::PlanePath::AlternateTerdragon->new (arms => 6)"
144           Create and return a new path object.
145
146           The optional "arms" parameter can make 1 to 6 copies of the curve,
147           each arm successively advancing.
148
149       "($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
153           Fractional positions give an X,Y position along a straight line
154           between the integer positions.
155
156       "$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
160           The curve can visit an "$x,$y" up to three times.  "xy_to_n()"
161           returns the smallest of the these N values.
162
163       "@n_list = $path->xy_to_n_list ($x,$y)"
164           Return a list of N point numbers for coordinates "$x,$y".
165
166           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
171   Descriptive Methods
172       "$n = $path->n_start()"
173           Return 0, the first N in the path.
174
175       "$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
182               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
188           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
192               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
198       "$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
204           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
210       "$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
216           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
221   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
226           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

FORMULAS

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
238          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
243       The flip of turn at odd positions is the "alternating" in the curve.
244
245          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
250   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
254           direction = 120deg * sum / +1  if digit=1 at even position
255                                    \ -1  if digit=1 at odd position
256
257       This is used mod 3 for "n_to_dxdy()".
258
259   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
264   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
268           X+Y mod 2 == 0        "even" points
269

OEIS

271       Sequences in Sloane's Online Encyclopedia of Integer Sequences related
272       to the alternate terdragon include,
273
274           <http://oeis.org/A156595> (etc)
275
276           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

SEE ALSO

282       Math::PlanePath, Math::PlanePath::TerdragonCurve
283
284       Math::PlanePath::DragonCurve, Math::PlanePath::AlternatePaper
285

HOME PAGE

287       <http://user42.tuxfamily.org/math-planepath/index.html>
288

LICENSE

290       Copyright 2018 Kevin Ryde
291
292       This file is part of Math-PlanePath.
293
294       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
299       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
304       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/>.
306
307
308
309perl v5.30.1                      2020-01M-a3t0h::PlanePath::AlternateTerdragon(3)
Impressum