1Math::PlanePath::TerdraUgsoenrCuCrovnet(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::TerdragonCurve(3)
2
3
4

NAME

6       Math::PlanePath::TerdragonCurve -- triangular dragon curve
7

SYNOPSIS

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

DESCRIPTION

14       This is the 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                  --- 26,29,32 ---------- 27                          6
30                     /         \
31             \      /           \
32          -- 24,33,42 ---------- 22,25                                5
33             /      \           /     \
34                     \         /       \
35                  --- 20,23,44 -------- 12,21            10           4
36                     /        \        /      \        /     \
37             \      /          \      /        \      /       \
38               18,45 --------- 13,16,19 ------ 8,11,14 -------- 9     3
39                    \          /       \      /       \
40                     \        /         \    /         \
41                         17              6,15 --------- 4,7           2
42                                              \        /    \
43                                               \      /      \
44                                                 2,5 ---------- 3     1
45                                                     \
46                                                      \
47                                           0 ----------- 1         <-Y=0
48
49                 ^        ^        ^       ^      ^      ^      ^
50                -3       -2       -1      X=0     1      2      3
51
52       The base figure is an "S" shape
53
54              2-----3
55               \
56                \
57           0-----1
58
59       which then repeats in self-similar style, so N=3 to N=6 is a copy
60       rotated +120 degrees, which is the angle of the N=1 to N=2 edge,
61
62           6      4          base figure repeats
63            \   / \          as N=3 to N=6,
64             \/    \         rotated +120 degrees
65             5 2----3
66               \
67                \
68           0-----1
69
70       Then N=6 to N=9 is a plain horizontal, which is the angle of N=2 to
71       N=3,
72
73                 8-----9       base figure repeats
74                  \            as N=6 to N=9,
75                   \           no rotation
76              6----7,4
77               \   / \
78                \ /   \
79                5,2----3
80                  \
81                   \
82              0-----1
83
84       Notice X=1,Y=1 is visited twice as N=2 and N=5.  Similarly X=2,Y=2 as
85       N=4 and N=7.  Each point can repeat up to 3 times.  "Inner" points are
86       3 times and on the edges up to 2 times.  The first tripled point is
87       X=1,Y=3 which as shown above is N=8, N=11 and N=14.
88
89       The curve never crosses itself.  The vertices touch as triangular
90       corners and no edges repeat.
91
92       The curve turns are the same as the "GosperSide", but here the turns
93       are by 120 degrees each whereas "GosperSide" is 60 degrees each.  The
94       extra angle here tightens up the shape.
95
96   Spiralling
97       The first step N=1 is to the right along the X axis and the path then
98       slowly spirals anti-clockwise and progressively fatter.  The end of
99       each replication is
100
101           Nlevel = 3^level
102
103       That point is at level*30 degrees around (as reckoned with Y*sqrt(3)
104       for a triangular grid).
105
106           Nlevel      X, Y     Angle (degrees)
107           ------    -------    -----
108              1        1, 0        0
109              3        3, 1       30
110              9        3, 3       60
111             27        0, 6       90
112             81       -9, 9      120
113            243      -27, 9      150
114            729      -54, 0      180
115
116       The following is points N=0 to N=3^6=729 going half-circle around to
117       180 degrees.  The N=0 origin is marked "0" and the N=729 end is marked
118       "E".
119
120                                      * *               * *
121                                   * * * *           * * * *
122                                  * * * *           * * * *
123                                   * * * * *   * *   * * * * *   * *
124                                * * * * * * * * * * * * * * * * * * *
125                               * * * * * * * * * * * * * * * * * * *
126                                * * * * * * * * * * * * * * * * * * * *
127                                   * * * * * * * * * * * * * * * * * * *
128                                  * * * * * * * * * * * *   * *   * * *
129                             * *   * * * * * * * * * * * *           * *
130            * E           * * * * * * * * * * * * * * * *           0 *
131           * *           * * * * * * * * * * * *   * *
132            * * *   * *   * * * * * * * * * * * *
133           * * * * * * * * * * * * * * * * * * *
134            * * * * * * * * * * * * * * * * * * * *
135               * * * * * * * * * * * * * * * * * * *
136              * * * * * * * * * * * * * * * * * * *
137               * *   * * * * *   * *   * * * * *
138                        * * * *           * * * *
139                       * * * *           * * * *
140                        * *               * *
141
142   Tiling
143       The little "S" shapes of the base figure N=0 to N=3 can be thought of
144       as a rhombus
145
146              2-----3
147             .     .
148            .     .
149           0-----1
150
151       The "S" shapes of each 3 points make a tiling of the plane with those
152       rhombi
153
154               \     \ /     /   \     \ /     /
155                *-----*-----*     *-----*-----*
156               /     / \     \   /     / \     \
157            \ /     /   \     \ /     /   \     \ /
158           --*-----*     *-----*-----*     *-----*--
159            / \     \   /     / \     \   /     / \
160               \     \ /     /   \     \ /     /
161                *-----*-----*     *-----*-----*
162               /     / \     \   /     / \     \
163            \ /     /   \     \ /     /   \     \ /
164           --*-----*     *-----o-----*     *-----*--
165            / \     \   /     / \     \   /     / \
166               \     \ /     /   \     \ /     /
167                *-----*-----*     *-----*-----*
168               /     / \     \   /     / \     \
169
170       Which is an ancient pattern,
171
172           <http://tilingsearch.org/HTML/data23/C07A.html>
173
174   Arms
175       The curve fills a sixth of the plane and six copies rotated by 60, 120,
176       180, 240 and 300 degrees mesh together perfectly.  The "arms" parameter
177       can choose 1 to 6 such curve arms successively advancing.
178
179       For example "arms => 6" begins as follows.  N=0,6,12,18,etc is the
180       first arm (the same shape as the plain curve above), then N=1,7,13,19
181       the second, N=2,8,14,20 the third, etc.
182
183                         \         /             \           /
184                          \       /               \         /
185                       --- 8,13,31 ---------------- 7,12,30 ---
186                         /        \               /         \
187            \           /          \             /           \          /
188             \         /            \           /             \        /
189           --- 9,14,32 ------------- 0,1,2,3,4,5 -------------- 6,17,35 ---
190             /         \            /           \             /        \
191            /           \          /             \           /          \
192                         \        /               \         /
193                      --- 10,15,33 ---------------- 11,16,34 ---
194                         /        \               /         \
195                        /          \             /           \
196
197       With six arms every X,Y point is visited three times, except the origin
198       0,0 where all six begin.  Every edge between points is traversed once.
199

FUNCTIONS

201       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
202       classes.
203
204       "$path = Math::PlanePath::TerdragonCurve->new ()"
205       "$path = Math::PlanePath::TerdragonCurve->new (arms => 6)"
206           Create and return a new path object.
207
208           The optional "arms" parameter can make 1 to 6 copies of the curve,
209           each arm successively advancing.
210
211       "($x,$y) = $path->n_to_xy ($n)"
212           Return the X,Y coordinates of point number $n on the path.  Points
213           begin at 0 and if "$n < 0" then the return is an empty list.
214
215           Fractional positions give an X,Y position along a straight line
216           between the integer positions.
217
218       "$n = $path->xy_to_n ($x,$y)"
219           Return the point number for coordinates "$x,$y".  If there's
220           nothing at "$x,$y" then return "undef".
221
222           The curve can visit an "$x,$y" up to three times.  "xy_to_n()"
223           returns the smallest of the these N values.
224
225       "@n_list = $path->xy_to_n_list ($x,$y)"
226           Return a list of N point numbers for coordinates "$x,$y".
227
228           The origin 0,0 has "arms_count()" many N since it's the starting
229           point for each arm.  Other points have up to 3 Ns for a given
230           "$x,$y".  If arms=6 then every even "$x,$y" except the origin has
231           exactly 3 Ns.
232
233   Descriptive Methods
234       "$n = $path->n_start()"
235           Return 0, the first N in the path.
236
237       "$dx = $path->dx_minimum()"
238       "$dx = $path->dx_maximum()"
239       "$dy = $path->dy_minimum()"
240       "$dy = $path->dy_maximum()"
241           The dX,dY values on the first arm take three possible combinations,
242           being 120 degree angles.
243
244               dX,dY   for arms=1
245               -----
246                2, 0        dX minimum = -1, maximum = +2
247               -1, 1        dY minimum = -1, maximum = +1
248                1,-1
249
250           For 2 or more arms the second arm is rotated by 60 degrees so
251           giving the following additional combinations, for a total six.
252           This changes the dX minimum.
253
254               dX,dY   for arms=2 or more
255               -----
256               -2, 0        dX minimum = -2, maximum = +2
257                1, 1        dY minimum = -1, maximum = +1
258               -1,-1
259
260   Level Methods
261       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
262           Return "(0, 3**$level)", or for multiple arms return "(0, $arms *
263           3**$level + ($arms-1))".
264
265           There are 3^level segments in a curve level, so 3^level+1 points
266           numbered from 0.  For multiple arms there are arms*(3^level+1)
267           points, numbered from 0 so n_hi = arms*(3^level+1)-1.
268

FORMULAS

270       Various formulas for boundary length, area and more can be found in the
271       author's mathematical write-up
272
273           <http://user42.tuxfamily.org/terdragon/index.html>
274
275   N to X,Y
276       There's no reversals or reflections in the curve so "n_to_xy()" can
277       take the digits of N either low to high or high to low and apply what
278       is effectively powers of the N=3 position.  The current code goes low
279       to high using i,j,k coordinates as described in "Triangular
280       Calculations" in Math::PlanePath.
281
282           si = 1    # position of endpoint N=3^level
283           sj = 0    #    where level=number of digits processed
284           sk = 0
285
286           i = 0     # position of N for digits so far processed
287           j = 0
288           k = 0
289
290           loop base 3 digits of N low to high
291              if digit == 0
292                 i,j,k no change
293              if digit == 1
294                 (i,j,k) = (si-j, sj-k, sk+i)  # rotate +120, add si,sj,sk
295              if digit == 2
296                 i -= sk      # add (si,sj,sk) rotated +60
297                 j += si
298                 k += sj
299
300              (si,sj,sk) = (si - sk,      # add rotated +60
301                            sj + si,
302                            sk + sj)
303
304       The digit handling is a combination of rotate and offset,
305
306           digit==1                   digit 2
307           rotate and offset          offset at si,sj,sk rotated
308
309                ^                          2------>
310                 \
311                  \                          \
312           *---  --1                  *--   --*
313
314       The calculation can also be thought of in term of w=1/2+I*sqrt(3)/2, a
315       complex number sixth root of unity.  i is the real part, j in the w
316       direction (60 degrees), and k in the w^2 direction (120 degrees).
317       si,sj,sk increase as if multiplied by w+1.
318
319   Turn
320       At each point N the curve always turns 120 degrees either to the left
321       or right, it never goes straight ahead.  If N is written in ternary
322       then the lowest non-zero digit gives the turn
323
324          ternary lowest
325          non-zero digit     turn
326          --------------     -----
327                1            left
328                2            right
329
330       At N=3^level or N=2*3^level the turn follows the shape at that 1 or 2
331       point.  The first and last unit step in each level are in the same
332       direction, so the next level shape gives the turn.
333
334              2*3^k-------3*3^k
335                 \
336                  \
337           0-------1*3^k
338
339   Next Turn
340       The next turn, ie. the turn at position N+1, can be calculated from the
341       ternary digits of N similarly.  The lowest non-2 digit gives the turn.
342
343          ternary lowest
344            non-2 digit       turn
345          --------------      -----
346                 0            left
347                 1            right
348
349       If N is all 2s then the lowest non-2 is taken to be a 0 above the high
350       end.  For example N=8 is 22 ternary so considered 022 for lowest non-2
351       digit=0 and turn left after the segment at N=8, ie. at point N=9 turn
352       left.
353
354       This rule works for the same reason as the plain turn above.  The next
355       turn of N is the plain turn of N+1 and adding +1 turns trailing 2s into
356       trailing 0s and increments the 0 or 1 digit above them to be 1 or 2.
357
358   Total Turn
359       The direction at N, ie. the total cumulative turn, is given by the
360       number of 1 digits when N is written in ternary,
361
362           direction = (count 1s in ternary N) * 120 degrees
363
364       For example N=12 is ternary 110 which has two 1s so the cumulative turn
365       at that point is 2*120=240 degrees, ie. the segment N=16 to N=17 is at
366       angle 240.
367
368       The segments for digit 0 or 2 are in the "current" direction unchanged.
369       The segment for digit 1 is rotated +120 degrees.
370
371   X,Y to N
372       The current code find digits of N low to high by a remainder on X,Y to
373       get the lowest then subtract and divide to unexpand.  See "unpoint" in
374       the author's mathematical write-up for details.
375
376   X,Y Visited
377       When arms=6 all "even" points of the plane are visited.  As per the
378       triangular representation of X,Y this means
379
380           X+Y mod 2 == 0        "even" points
381

OEIS

383       The terdragon is in Sloane's Online Encyclopedia of Integer Sequences
384       as,
385
386           <http://oeis.org/A080846> (etc)
387
388           A060236   turn 1=left,2=right, by 120 degrees
389                       (lowest non-zero ternary digit)
390           A137893   turn 1=left,0=right (morphism)
391           A189640   turn 0=left,1=right (morphism, extra initial 0)
392           A080846   next turn 0=left,1=right, by 120 degrees
393                       (n=0 is turn at N=1)
394           A189673   prev turn 1=left,0=right (morphism, extra initial 0)
395           A038502   strip trailing ternary 0s,
396                       taken mod 3 is turn 1=left,2=right
397           A133162   1=segment, 2=right turn between
398
399       A189673 and A026179 start with extra initial values arising from their
400       morphism definition.  That can be skipped to consider the turns
401       starting with a left turn at N=1.
402
403           A026225   N positions of left turns,
404                       being (3*i+1)*3^j so lowest non-zero digit is 1
405           A026179   N positions of right turns (except initial 1)
406                       being (3*i+2)*3^j so lowest non-zero digit is 2
407           A060032   bignum turns 1=left,2=right to 3^level
408           A189674   num left turns 1 to N
409           A189641   num right turns 1 to N
410           A189672     same
411
412           A026141   \ dTurnLeft increment between left turns N
413           A026171   /
414           A026181   \ dTurnRight increment between right turns N
415           A131989   /
416
417           A062756   direction (net total turn), count ternary 1s
418           A005823   N positions where direction = 0, ternary no 1s
419           A023692 through A023698
420                     N positions where direction = 1 to 7, ternary num 1s
421
422           A111286   boundary length, N=0 to N=3^k, skip initial 1
423           A003945   boundary/2
424           A002023   boundary odd levels N=0 to N=3^(2k+1),
425                     or even levels one side N=0 to N=3^(2k),
426                       being 6*4^k
427           A164346   boundary even levels N=0 to N=3^(2k),
428                     or one side, odd levels, N=0 to N=3^(2k+1),
429                       being 3*4^k
430           A042950   V[k] boundary length
431
432           A056182   area enclosed N=0 to N=3^k, being 2*(3^k-2^k)
433           A081956     same
434           A118004   1/2 area N=0 to N=3^(2k+1), odd levels, 9^n-4^n
435           A155559   join area, being 0 then 2^k
436
437           A099754   1/2 count distinct visited points N=0 to N=3^k
438
439           A092236   count East segments N=0 to N=3^k-1
440           A135254   count North-West segments N=0 to N=3^k-1, extra 0
441           A133474   count South-West segments N=0 to N=3^k-1
442           A057083   count segments diff from 3^(k-1)
443           A101990   count segments same dir as middle N=0 to N=3^k-1
444
445           A097038   num runs of 12 consecutive segments within N=0 to 3^k-1
446                       each segment enclosing a new unit triangle
447
448           A057682   level X, at N=3^level
449                       also arms=2 level Y, at N=2*3^level
450           A057083   level Y, at N=3^level
451                       also arms=6 level X at N=6*3^level
452
453           A057681   arms=2 level X, at N=2*3^level
454                       also arms=3 level Y at 3*3^level
455           A103312   same
456

HOUSE OF GRAPHS

458       House of Graphs entries for the terdragon as a graph include
459
460           <https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc
461
462           19655     level=0 (1-segment path)
463           594       level=1 (3-segment path)
464           21138     level=2
465           21140     level=3
466           33761     level=4
467           33763     level=5
468

SEE ALSO

470       Math::PlanePath, Math::PlanePath::TerdragonRounded,
471       Math::PlanePath::TerdragonMidpoint, Math::PlanePath::GosperSide
472
473       Math::PlanePath::DragonCurve, Math::PlanePath::R5DragonCurve
474
475       Larry Riddle's Terdragon page, for boundary and area calculations of
476       the terdragon as an infinite fractal
477       <http://ecademy.agnesscott.edu/~lriddle/ifs/heighway/terdragon.htm>
478

HOME PAGE

480       <http://user42.tuxfamily.org/math-planepath/index.html>
481

LICENSE

483       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
484       Kevin Ryde
485
486       This file is part of Math-PlanePath.
487
488       Math-PlanePath is free software; you can redistribute it and/or modify
489       it under the terms of the GNU General Public License as published by
490       the Free Software Foundation; either version 3, or (at your option) any
491       later version.
492
493       Math-PlanePath is distributed in the hope that it will be useful, but
494       WITHOUT ANY WARRANTY; without even the implied warranty of
495       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
496       General Public License for more details.
497
498       You should have received a copy of the GNU General Public License along
499       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
500
501
502
503perl v5.32.1                      2021-01-27Math::PlanePath::TerdragonCurve(3)
Impressum