Math::PlanePath::TerdragonCurve -- triangular dragon curve
use Math::PlanePath::TerdragonCurve; my $path = Math::PlanePath::TerdragonCurve->new; my ($x, $y) = $path->n_to_xy (123);
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. http://www-cs-faculty.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
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.
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) 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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
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,
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.
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.
$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
($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.
Various formulas for boundary length, area and more can be found in the author's mathematical write-up
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)/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.
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
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.
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.
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.
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
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) 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 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 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^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 entries for the terdragon as a graph include
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
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 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/>.