Provided by: libmath-planepath-perl_113-1_all 
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,
30 28 7
/ \ / \
/ \ / \
31,34 -------- 26,29,32 ---------- 27 6
\ / \
\ / \
24,33,42 ---------- 22,25 5
/ \ / \
/ \ / \
40,43,46 ------ 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
^ ^ ^ ^ ^ ^ ^ ^
-4 -3 -2 -1 X=0 1 2 3
Points are a triangular grid using every second integer X,Y as per "Triangular Lattice" in
Math::PlanePath.
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 N=5 is a repeat of point X=1,Y=1 which is also N=2, and then N=7 repeats the N=4
position X=2,Y=2. Each point repeats up to 3 times. Inner points are 3 times and on the
edges of the curve area up to 2 times. The first tripled point is X=1,Y=3 which can be
seen above as N=8, N=11 and N=14.
The curve never crosses itself. The vertices touch as little triangular corners and no
edges repeat.
The shape is the same as the "GosperSide", but the turns here are by 120 degrees each
whereas the "GosperSide" is by 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 the usual Y*sqrt(3) for a
triangular grid, per "Triangular Lattice" in Math::PlanePath).
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 "o" and the N=729 end marked "e".
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* e * * * * * * * * * * * * * * * * o *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
Tiling
The little "S" shapes of the base figure N=0 to N=3 can be thought of as a parallelogram
2-----3
. .
. .
0-----1
The "S" shapes of each 3 points make a tiling of the plane with those parallelograms
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \
\ / / \ \ / / \ \ /
--*-----* *-----*-----* *-----*--
/ \ \ / / \ \ / / \
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \
\ / / \ \ / / \ \ /
--*-----* *-----o-----* *-----*--
/ \ \ / / \ \ / / \
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \
As per for example
<http://tilingsearch.org/HTML/data23/C07A.html>
Arms
The curve fills a sixth of the plane and six copies mesh together perfectly rotated by 60,
120, 180, 240 and 300 degrees. 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 the 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. In the current code the smallest of
the these N values is returned. Is that the best way?
"@n_list = $path->xy_to_n_list ($x,$y)"
Return a list of N point numbers for coordinates "$x,$y". There can be none, one, two
or three N's for a given "$x,$y".
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, at 120 degree
angles.
dX,dY
-----
2, 0 dX minimum -1, maximum +2 arms == 1
-1, 1 dY minimum -1, maximum +1
1,-1
For 2 or more arms the second arm is rotated by 60 degrees so giving additional
combinations for a total six
dX,dY also
-----
-2, 0 dX minimum -2, maximum +2 arms >= 2
1, 1 dY minimum -1, maximum +1
-1,-1
FORMULAS
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 applying what's in effect 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 as using w=1/2+I*sqrt(3)/2, a complex 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 Turn
-------- ----
1 left
2 right
Essentially 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^(k+1)
\
\
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 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 N=9 turn left.
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.
X,Y to N
The current code applies "TerdragonMidpoint" "xy_to_n()" to calculate six candidate N from
the six edges around a point. Those N values which convert back to the target X,Y by
"n_to_xy()" are the results for "xy_to_n_list()".
The six edges are three going towards the point and three going away. The midpoint
calculation gives N-1 for the towards and N for the away. Is there a good way to tell
which edge is the smallest? Or just which 3 edges lead away? It might be directions
0,2,4 for the even arms and 1,3,5 for the odd ones, but the boundary of those areas is
tricky.
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 non-zero ternary digit)
A137893 turn 1=left,0=right (morphism)
A189640 turn 0=left,1=right (morphism, extra initial 0)
A189673 turn 1=left,0=right (morphism, extra initial 0)
A038502 strip trailing ternary 0s,
taken mod 3 is turn 1=left,2=right
A026225 N positions of left turns,
being (3*i+1)*3^j so lowest non-zero digit is a 1
A026179 N positions of right turns (except initial 1)
A060032 bignum turns 1=left,2=right to 3^level
A062756 total turn, count ternary 1s
A005823 N positions where total turn == 0, ternary no 1s
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.
SEE ALSO
Math::PlanePath, Math::PlanePath::TerdragonRounded, Math::PlanePath::TerdragonMidpoint,
Math::PlanePath::GosperSide
Math::PlanePath::DragonCurve, Math::PlanePath::R5DragonCurve
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2011, 2012, 2013 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 <http://www.gnu.org/licenses/>.