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 A080846 next turn 0=left,1=right, by 120 degrees
389 (n=0 is turn at N=1)
390 A060236 turn 1=left,2=right, by 120 degrees
392 (lowest non-zero ternary digit)
393 A137893 turn 1=left,0=right (morphism)
394 A189673 turn 1=left,0=right (morphism, extra initial 0)
395 A189640 turn 0=left,1=right (morphism, extra initial 0)
396 A038502 strip trailing ternary 0s,
397 taken mod 3 is turn 1=left,2=right
398 A133162 1=segment, 2=right turn between
399 A189673 and A026179 start with extra initial values arising from their
401 morphism definition. That can be skipped to consider the turns
402 starting with a left turn at N=1.
403 A026225 N positions of left turns,
405 being (3*i+1)*3^j so lowest non-zero digit is a 1
406 A026179 N positions of right turns (except initial 1)
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 \ dN increment between left turns N
413 A026171 /
414 A026181 \ dN increment between left turns N
415 A131989 /
416 A062756 total turn, count ternary 1s
418 A005823 N positions where net turn == 0, ternary no 1s
419 A111286 boundary length, N=0 to N=3^k, skip initial 1
421 A003945 boundary/2
422 A002023 boundary odd levels N=0 to N=3^(2k+1),
423 or even levels one side N=0 to N=3^(2k),
424 being 6*4^k
425 A164346 boundary even levels N=0 to N=3^(2k),
426 or one side, odd levels, N=0 to N=3^(2k+1),
427 being 3*4^k
428 A042950 V[k] boundary length
429 A056182 area enclosed N=0 to N=3^k, being 2*(3^k-2^k)
431 A081956 same
432 A118004 1/2 area N=0 to N=3^(2k+1), odd levels, 9^n-4^n
433 A155559 join area, being 0 then 2^k
434 A099754 1/2 count distinct visited points N=0 to N=3^k
436 A092236 count East segments N=0 to N=3^k-1
438 A135254 count North-West segments N=0 to N=3^k-1, extra 0
439 A133474 count South-West segments N=0 to N=3^k-1
440 A057083 count segments diff from 3^(k-1)
441 A101990 count segments same dir as middle N=0 to N=3^k-1
442 A097038 num runs of 12 consecutive segments within N=0 to 3^k-1
444 each segment enclosing a new unit triangle
445 A057682 level X, at N=3^level
447 also arms=2 level Y, at N=2*3^level
448 A057083 level Y, at N=3^level
449 also arms=6 level X at N=6*3^level
450 A057681 arms=2 level X, at N=2*3^level
452 also arms=3 level Y at 3*3^level
453 A103312 same
454
456 House of Graphs entries for the terdragon as a graph include
457 level=2, <https://hog.grinvin.org/ViewGraphInfo.action?id=21138>
459 level=3, <https://hog.grinvin.org/ViewGraphInfo.action?id=21140>
460
462 Math::PlanePath, Math::PlanePath::TerdragonRounded,
463 Math::PlanePath::TerdragonMidpoint, Math::PlanePath::GosperSide
464 Math::PlanePath::DragonCurve, Math::PlanePath::R5DragonCurve
466 Larry Riddle's Terdragon page, for boundary and area calculations of
468 the terdragon as an infinite fractal
469 <http://ecademy.agnesscott.edu/~lriddle/ifs/heighway/terdragon.htm>
470
472 <http://user42.tuxfamily.org/math-planepath/index.html>
473
475 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
476 This file is part of Math-PlanePath.
478 Math-PlanePath is free software; you can redistribute it and/or modify
480 it under the terms of the GNU General Public License as published by
481 the Free Software Foundation; either version 3, or (at your option) any
482 later version.
483 Math-PlanePath is distributed in the hope that it will be useful, but
485 WITHOUT ANY WARRANTY; without even the implied warranty of
486 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
487 General Public License for more details.
488 You should have received a copy of the GNU General Public License along
490 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
491perl v5.30.0 2019-08-17Math::PlanePath::TerdragonCurve(3)