1Math::PlanePath::TerdraUgsoenrCuCrovnet(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::TerdragonCurve(3)
2
6 Math::PlanePath::TerdragonCurve -- triangular dragon curve
7
9 use Math::PlanePath::TerdragonCurve;
10 my $path = Math::PlanePath::TerdragonCurve->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is the 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 --- 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 ^ ^ ^ ^ ^ ^ ^
50 -3 -2 -1 X=0 1 2 3
51 The base figure is an "S" shape
53 2-----3
55 \
56 \
57 0-----1
58 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 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 Then N=6 to N=9 is a plain horizontal, which is the angle of N=2 to
71 N=3,
72 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 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 The curve never crosses itself. The vertices touch as triangular
90 corners and no edges repeat.
91 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 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 Nlevel = 3^level
102 That point is at level*30 degrees around (as reckoned with Y*sqrt(3)
104 for a triangular grid).
105 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 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 * * * *
121 * * * * * * * *
122 * * * * * * * *
123 * * * * * * * * * * * * * *
124 * * * * * * * * * * * * * * * * * * *
125 * * * * * * * * * * * * * * * * * * *
126 * * * * * * * * * * * * * * * * * * * *
127 * * * * * * * * * * * * * * * * * * *
128 * * * * * * * * * * * * * * * * *
129 * * * * * * * * * * * * * * * *
130 * E * * * * * * * * * * * * * * * * 0 *
131 * * * * * * * * * * * * * * * *
132 * * * * * * * * * * * * * * * * *
133 * * * * * * * * * * * * * * * * * * *
134 * * * * * * * * * * * * * * * * * * * *
135 * * * * * * * * * * * * * * * * * * *
136 * * * * * * * * * * * * * * * * * * *
137 * * * * * * * * * * * * * *
138 * * * * * * * *
139 * * * * * * * *
140 * * * *
141 Tiling
143 The little "S" shapes of the base figure N=0 to N=3 can be thought of
144 as a rhombus
145 2-----3
147 . .
148 . .
149 0-----1
150 The "S" shapes of each 3 points make a tiling of the plane with those
152 rhombi
153 \ \ / / \ \ / /
155 *-----*-----* *-----*-----*
156 / / \ \ / / \ \
157 \ / / \ \ / / \ \ /
158 --*-----* *-----*-----* *-----*--
159 / \ \ / / \ \ / / \
160 \ \ / / \ \ / /
161 *-----*-----* *-----*-----*
162 / / \ \ / / \ \
163 \ / / \ \ / / \ \ /
164 --*-----* *-----o-----* *-----*--
165 / \ \ / / \ \ / / \
166 \ \ / / \ \ / /
167 *-----*-----* *-----*-----*
168 / / \ \ / / \ \
169 Which is an ancient pattern,
171 <http://tilingsearch.org/HTML/data23/C07A.html>
173 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 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 \ / \ /
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 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
201 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
202 classes.
203 "$path = Math::PlanePath::TerdragonCurve->new ()"
205 "$path = Math::PlanePath::TerdragonCurve->new (arms => 6)"
206 Create and return a new path object.
207 The optional "arms" parameter can make 1 to 6 copies of the curve,
209 each arm successively advancing.
210 "($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 Fractional positions give an X,Y position along a straight line
216 between the integer positions.
217 "$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 The curve can visit an "$x,$y" up to three times. "xy_to_n()"
223 returns the smallest of the these N values.
224 "@n_list = $path->xy_to_n_list ($x,$y)"
226 Return a list of N point numbers for coordinates "$x,$y".
227 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 Descriptive Methods
234 "$n = $path->n_start()"
235 Return 0, the first N in the path.
236 "$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 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 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 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 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 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
270 Various formulas for boundary length, area and more can be found in the
271 author's mathematical write-up
272 <http://user42.tuxfamily.org/terdragon/index.html>
274 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 si = 1 # position of endpoint N=3^level
283 sj = 0 # where level=number of digits processed
284 sk = 0
285 i = 0 # position of N for digits so far processed
287 j = 0
288 k = 0
289 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 (si,sj,sk) = (si - sk, # add rotated +60
301 sj + si,
302 sk + sj)
303 The digit handling is a combination of rotate and offset,
305 digit==1 digit 2
307 rotate and offset offset at si,sj,sk rotated
308 ^ 2------>
310 \
311 \ \
312 *--- --1 *-- --*
313 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 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 ternary lowest
325 non-zero digit turn
326 -------------- -----
327 1 left
328 2 right
329 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 2*3^k-------3*3^k
335 \
336 \
337 0-------1*3^k
338 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 ternary lowest
344 non-2 digit turn
345 -------------- -----
346 0 left
347 1 right
348 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 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 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 direction = (count 1s in ternary N) * 120 degrees
363 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 The segments for digit 0 or 2 are in the "current" direction unchanged.
369 The segment for digit 1 is rotated +120 degrees.
370 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 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 X+Y mod 2 == 0 "even" points
381
383 The terdragon is in Sloane's Online Encyclopedia of Integer Sequences
384 as,
385 <http://oeis.org/A080846> (etc)
387 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 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 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 A026141 \ dTurnLeft increment between left turns N
413 A026171 /
414 A026181 \ dTurnRight increment between right turns N
415 A131989 /
416 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 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 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 A099754 1/2 count distinct visited points N=0 to N=3^k
438 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 A097038 num runs of 12 consecutive segments within N=0 to 3^k-1
446 each segment enclosing a new unit triangle
447 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 A057681 arms=2 level X, at N=2*3^level
454 also arms=3 level Y at 3*3^level
455 A103312 same
456
458 House of Graphs entries for the terdragon as a graph include
459 <https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc
461 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
470 Math::PlanePath, Math::PlanePath::TerdragonRounded,
471 Math::PlanePath::TerdragonMidpoint, Math::PlanePath::GosperSide
472 Math::PlanePath::DragonCurve, Math::PlanePath::R5DragonCurve
474 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
480 <http://user42.tuxfamily.org/math-planepath/index.html>
481
483 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
484 Kevin Ryde
485 This file is part of Math-PlanePath.
487 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 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 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/>.
500perl v5.34.0 2021-07-22Math::PlanePath::TerdragonCurve(3)