--- name: "Math::PlanePath::TerdragonCurve" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::TerdragonCurve" --- # Math::PlanePath::TerdragonCurve(3pm) ## NAME Math::PlanePath::TerdragonCurve -- triangular dragon curve ## SYNOPSIS ``` use Math::PlanePath::TerdragonCurve; my $path = Math::PlanePath::TerdragonCurve->new; my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This is the terdragon curve by Davis and Knuth, Chandler Davis and Donald Knuth, "Number Representations and Dragon Curves -- I", Journal Recreational Mathematics, volume 3, number 2 (April 1970), pages 66-81 and "Number Representations and Dragon Curves -- II", volume 3, number 3 (July 1970), pages 133-149. Reprinted with addendum in Knuth "Selected Papers on Fun and Games", 2010, pages 571--614. \ Points are a triangular grid using every second integer X,Y as per "Triangular Lattice" in Math::PlanePath, beginning ``` \ / \ --- 26,29,32 ---------- 27 6 / \ \ / \ -- 24,33,42 ---------- 22,25 5 / \ / \ \ / \ --- 20,23,44 -------- 12,21 10 4 / \ / \ / \ \ / \ / \ / \ 18,45 --------- 13,16,19 ------ 8,11,14 -------- 9 3 \ / \ / \ \ / \ / \ 17 6,15 --------- 4,7 2 \ / \ \ / \ 2,5 ---------- 3 1 \ \ 0 ----------- 1 <-Y=0 ^ ^ ^ ^ ^ ^ ^ -3 -2 -1 X=0 1 2 3 ``` The base figure is an "S" shape ``` 2-----3 \ \ 0-----1 ``` which then repeats in self-similar style, so N=3 to N=6 is a copy rotated +120 degrees, which is the angle of the N=1 to N=2 edge, ``` 6 4 base figure repeats \ / \ as N=3 to N=6, \/ \ rotated +120 degrees 5 2----3 \ \ 0-----1 ``` Then N=6 to N=9 is a plain horizontal, which is the angle of N=2 to N=3, ``` 8-----9 base figure repeats \ as N=6 to N=9, \ no rotation 6----7,4 \ / \ \ / \ 5,2----3 \ \ 0-----1 ``` Notice X=1,Y=1 is visited twice as N=2 and N=5. Similarly X=2,Y=2 as N=4 and N=7. Each point can repeat up to 3 times. "Inner" points are 3 times and on the edges up to 2 times. The first tripled point is X=1,Y=3 which as shown above is N=8, N=11 and N=14. The curve never crosses itself. The vertices touch as triangular corners and no edges repeat. The curve turns are the same as the `"GosperSide"`, but here the turns are by 120 degrees each whereas `"GosperSide"` is 60 degrees each. The extra angle here tightens up the shape. ### Spiralling The first step N=1 is to the right along the X axis and the path then slowly spirals anti-clockwise and progressively fatter. The end of each replication is ``` Nlevel = 3^level ``` That point is at level\*30 degrees around (as reckoned with Y\*[**sqrt**(3)](/sqrt/3.md) for a triangular grid). ``` Nlevel X, Y Angle (degrees) ------ ------- ----- 1 1, 0 0 3 3, 1 30 9 3, 3 60 27 0, 6 90 81 -9, 9 120 243 -27, 9 150 729 -54, 0 180 ``` The following is points N=0 to N=3^6=729 going half-circle around to 180 degrees. The N=0 origin is marked "0" and the N=729 end is marked "E". ``` * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * E * * * * * * * * * * * * * * * * 0 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ``` ### Tiling The little "S" shapes of the base figure N=0 to N=3 can be thought of as a rhombus ``` 2-----3 . . . . 0-----1 ``` The "S" shapes of each 3 points make a tiling of the plane with those rhombi ``` \ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \ \ / / \ \ / / \ \ / --*-----* *-----*-----* *-----*-- / \ \ / / \ \ / / \ \ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \ \ / / \ \ / / \ \ / --*-----* *-----o-----* *-----*-- / \ \ / / \ \ / / \ \ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \ ``` Which is an ancient pattern, \ ### Arms The curve fills a sixth of the plane and six copies rotated by 60, 120, 180, 240 and 300 degrees mesh together perfectly. The `"arms"` parameter can choose 1 to 6 such curve arms successively advancing. For example `"arms => 6"` begins as follows. N=0,6,12,18,etc is the first arm (the same shape as the plain curve above), then N=1,7,13,19 the second, N=2,8,14,20 the third, etc. ``` \ / \ / \ / \ / --- 8,13,31 ---------------- 7,12,30 --- / \ / \ \ / \ / \ / \ / \ / \ / --- 9,14,32 ------------- 0,1,2,3,4,5 -------------- 6,17,35 --- / \ / \ / \ / \ / \ / \ \ / \ / --- 10,15,33 ---------------- 11,16,34 --- / \ / \ / \ / \ ``` With six arms every X,Y point is visited three times, except the origin 0,0 where all six begin. Every edge between points is traversed once. ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. - "$path = Math::PlanePath::TerdragonCurve-\>new ()" - "$path = Math::PlanePath::TerdragonCurve-\>new (arms =\> 6)" Create and return a new path object. The optional `"arms"` parameter can make 1 to 6 copies of the curve, each arm successively advancing. - "($x,$y) = $path-\>n\_to\_xy ($n)" Return the X,Y coordinates of point number `$n` on the path. Points begin at 0 and if `"$n < 0"` then the return is an empty list. Fractional positions give an X,Y position along a straight line between the integer positions. - "$n = $path-\>xy\_to\_n ($x,$y)" Return the point number for coordinates `"$x,$y"`. If there's nothing at `"$x,$y"` then return `"undef"`. The curve can visit an `"$x,$y"` up to three times. `"xy_to_n()"` returns the smallest of the these N values. - "@n\_list = $path-\>xy\_to\_n\_list ($x,$y)" Return a list of N point numbers for coordinates `"$x,$y"`. The origin 0,0 has `"arms_count()"` many N since it's the starting point for each arm. Other points have up to 3 Ns for a given `"$x,$y"`. If arms=6 then every even `"$x,$y"` except the origin has exactly 3 Ns. ### Descriptive Methods - "$n = $path-\>n\_start()" Return 0, the first N in the path. - "$dx = $path-\>dx\_minimum()" - "$dx = $path-\>dx\_maximum()" - "$dy = $path-\>dy\_minimum()" - "$dy = $path-\>dy\_maximum()" The dX,dY values on the first arm take three possible combinations, being 120 degree angles. ``` dX,dY for arms=1 ----- 2, 0 dX minimum = -1, maximum = +2 -1, 1 dY minimum = -1, maximum = +1 1,-1 ``` For 2 or more arms the second arm is rotated by 60 degrees so giving the following additional combinations, for a total six. This changes the dX minimum. ``` dX,dY for arms=2 or more ----- -2, 0 dX minimum = -2, maximum = +2 1, 1 dY minimum = -1, maximum = +1 -1,-1 ``` ### Level Methods - "($n\_lo, $n\_hi) = $path-\>level\_to\_n\_range($level)" Return `"(0, 3**$level)"`, or for multiple arms return `"(0, $arms *` `3**$level + ($arms-1))"`. There are 3^level segments in a curve level, so 3^level+1 points numbered from 0. For multiple arms there are arms\*(3^level+1) points, numbered from 0 so n\_hi = arms\*(3^level+1)-1. ## FORMULAS Various formulas for boundary length, area and more can be found in the author's mathematical write-up \ ### N to X,Y There's no reversals or reflections in the curve so `"n_to_xy()"` can take the digits of N either low to high or high to low and apply what is effectively powers of the N=3 position. The current code goes low to high using i,j,k coordinates as described in "Triangular Calculations" in Math::PlanePath. ``` si = 1 # position of endpoint N=3^level sj = 0 # where level=number of digits processed sk = 0 i = 0 # position of N for digits so far processed j = 0 k = 0 loop base 3 digits of N low to high if digit == 0 i,j,k no change if digit == 1 (i,j,k) = (si-j, sj-k, sk+i) # rotate +120, add si,sj,sk if digit == 2 i -= sk # add (si,sj,sk) rotated +60 j += si k += sj (si,sj,sk) = (si - sk, # add rotated +60 sj + si, sk + sj) ``` The digit handling is a combination of rotate and offset, ``` digit==1 digit 2 rotate and offset offset at si,sj,sk rotated ^ 2------> \ \ \ *--- --1 *-- --* ``` The calculation can also be thought of in term of w=1/2+I\*[**sqrt**(3)](/sqrt/3.md)/2, a complex number sixth root of unity. i is the real part, j in the w direction (60 degrees), and k in the w^2 direction (120 degrees). si,sj,sk increase as if multiplied by w+1. ### Turn At each point N the curve always turns 120 degrees either to the left or right, it never goes straight ahead. If N is written in ternary then the lowest non-zero digit gives the turn ``` ternary lowest non-zero digit turn -------------- ----- 1 left 2 right ``` At N=3^level or N=2\*3^level the turn follows the shape at that 1 or 2 point. The first and last unit step in each level are in the same direction, so the next level shape gives the turn. ``` 2*3^k-------3*3^k \ \ 0-------1*3^k ``` ### Next Turn The next turn, ie. the turn at position N+1, can be calculated from the ternary digits of N similarly. The lowest non-2 digit gives the turn. ``` ternary lowest non-2 digit turn -------------- ----- 0 left 1 right ``` If N is all 2s then the lowest non-2 is taken to be a 0 above the high end. For example N=8 is 22 ternary so considered 022 for lowest non-2 digit=0 and turn left after the segment at N=8, ie. at point N=9 turn left. This rule works for the same reason as the plain turn above. The next turn of N is the plain turn of N+1 and adding +1 turns trailing 2s into trailing 0s and increments the 0 or 1 digit above them to be 1 or 2. ### Total Turn The direction at N, ie. the total cumulative turn, is given by the number of 1 digits when N is written in ternary, ``` direction = (count 1s in ternary N) * 120 degrees ``` For example N=12 is ternary 110 which has two 1s so the cumulative turn at that point is 2\*120=240 degrees, ie. the segment N=16 to N=17 is at angle 240. The segments for digit 0 or 2 are in the "current" direction unchanged. The segment for digit 1 is rotated +120 degrees. ### X,Y to N The current code find digits of N low to high by a remainder on X,Y to get the lowest then subtract and divide to unexpand. See "unpoint" in the author's mathematical write-up for details. ### X,Y Visited When arms=6 all "even" points of the plane are visited. As per the triangular representation of X,Y this means ``` X+Y mod 2 == 0 "even" points ``` ## OEIS The terdragon is in Sloane's Online Encyclopedia of Integer Sequences as, \ (etc) ``` A060236 turn 1=left,2=right, by 120 degrees (lowest non-zero ternary digit) A137893 turn 1=left,0=right (morphism) A189640 turn 0=left,1=right (morphism, extra initial 0) A080846 next turn 0=left,1=right, by 120 degrees (n=0 is turn at N=1) A189673 prev turn 1=left,0=right (morphism, extra initial 0) A038502 strip trailing ternary 0s, taken mod 3 is turn 1=left,2=right A133162 1=segment, 2=right turn between ``` A189673 and A026179 start with extra initial values arising from their morphism definition. That can be skipped to consider the turns starting with a left turn at N=1. ``` A026225 N positions of left turns, being (3*i+1)*3^j so lowest non-zero digit is 1 A026179 N positions of right turns (except initial 1) being (3*i+2)*3^j so lowest non-zero digit is 2 A060032 bignum turns 1=left,2=right to 3^level A189674 num left turns 1 to N A189641 num right turns 1 to N A189672 same A026141 \ dTurnLeft increment between left turns N A026171 / A026181 \ dTurnRight increment between right turns N A131989 / A062756 direction (net total turn), count ternary 1s A005823 N positions where direction = 0, ternary no 1s A023692 through A023698 N positions where direction = 1 to 7, ternary num 1s A111286 boundary length, N=0 to N=3^k, skip initial 1 A003945 boundary/2 A002023 boundary odd levels N=0 to N=3^(2k+1), or even levels one side N=0 to N=3^(2k), being 6*4^k A164346 boundary even levels N=0 to N=3^(2k), or one side, odd levels, N=0 to N=3^(2k+1), being 3*4^k A042950 V[k] boundary length A056182 area enclosed N=0 to N=3^k, being 2*(3^k-2^k) A081956 same A118004 1/2 area N=0 to N=3^(2k+1), odd levels, 9^n-4^n A155559 join area, being 0 then 2^k A099754 1/2 count distinct visited points N=0 to N=3^k A092236 count East segments N=0 to N=3^k-1 A135254 count North-West segments N=0 to N=3^k-1, extra 0 A133474 count South-West segments N=0 to N=3^k-1 A057083 count segments diff from 3^(k-1) A101990 count segments same dir as middle N=0 to N=3^k-1 A097038 num runs of 12 consecutive segments within N=0 to 3^k-1 each segment enclosing a new unit triangle A057682 level X, at N=3^level also arms=2 level Y, at N=2*3^level A057083 level Y, at N=3^level also arms=6 level X at N=6*3^level A057681 arms=2 level X, at N=2*3^level also arms=3 level Y at 3*3^level A103312 same ``` ## HOUSE OF GRAPHS House of Graphs entries for the terdragon as a graph include \ etc ``` 19655 level=0 (1-segment path) 594 level=1 (3-segment path) 21138 level=2 21140 level=3 33761 level=4 33763 level=5 ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::TerdragonRounded, Math::PlanePath::TerdragonMidpoint, Math::PlanePath::GosperSide Math::PlanePath::DragonCurve, Math::PlanePath::R5DragonCurve Larry Riddle's Terdragon page, for boundary and area calculations of the terdragon as an infinite fractal \ ## HOME PAGE \ ## LICENSE Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde This file is part of Math-PlanePath. Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see \.