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 6681 and "Number Representations and Dragon Curves  II", volume 3, number 3 (July 1970), pages 133149.
Reprinted with addendum in Knuth "Selected Papers on Fun and Games", 2010, pages 571614. http://wwwcsfaculty.stanford.edu/~uno/fg.html
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
23
\
\
01
which then repeats in selfsimilar 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 23
\
\
01
Then N=6 to N=9 is a plain horizontal, which is the angle of N=2 to N=3,
89 base figure repeats
\ as N=6 to N=9,
\ no rotation
67,4
\ / \
\ / \
5,23
\
\
01
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 anticlockwise 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) 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 halfcircle 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
23
. .
. .
01
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 returnundef
.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 + ($arms1))
.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 writeup
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) = (sij, sjk, 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)/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 nonzero digit gives the turn
ternary lowest
nonzero 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^k3*3^k
\
\
01*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 non2 digit gives the turn.
ternary lowest
non2 digit turn
 
0 left
1 right
If N is all 2s then the lowest non2 is taken to be a 0 above the high end. For example N=8 is 22 ternary so considered 022 for lowest non2 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 writeup 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,
http://oeis.org/A080846 (etc)
A080846 next turn 0=left,1=right, by 120 degrees
(n=0 is turn at N=1)
A060236 turn 1=left,2=right, by 120 degrees
(lowest nonzero ternary digit)
A137893 turn 1=left,0=right (morphism)
A189673 turn 1=left,0=right (morphism, extra initial 0)
A189640 turn 0=left,1=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 nonzero digit is a 1
A026179 N positions of right turns (except initial 1)
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 \ dN increment between left turns N
A026171 /
A026181 \ dN increment between left turns N
A131989 /
A062756 total turn, count ternary 1s
A005823 N positions where net turn == 0, ternary no 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^k2^k)
A081956 same
A118004 1/2 area N=0 to N=3^(2k+1), odd levels, 9^n4^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^k1
A135254 count NorthWest segments N=0 to N=3^k1, extra 0
A133474 count SouthWest segments N=0 to N=3^k1
A057083 count segments diff from 3^(k1)
A101990 count segments same dir as middle N=0 to N=3^k1
A097038 num runs of 12 consecutive segments within N=0 to 3^k1
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
 level=2, https://hog.grinvin.org/ViewGraphInfo.action?id=21138
 level=3, https://hog.grinvin.org/ViewGraphInfo.action?id=21140
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 http://ecademy.agnesscott.edu/~lriddle/ifs/heighway/terdragon.htm
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.