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,
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 on every second X and offset on alternate Y rows so as to give integer X,Y coordinates, 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 copy rotated +120 degrees like N=1 to N=2,
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 like 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 where N=2 was, and then N=7 repeats the N=4 position. Each point is 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 is N=8, N=11 and N=14.
The curve never crosses itself, only touches at little triangular shaped corners, and no edges repeat.
The first step N=1 is to the right along the X axis and the path then slowly spirals counter-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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
The little "S" shapes of the base figure N=0 to N=3 can be thought of as a little parallelogram
2-----3 . . . . 0-----1
The "S" shapes then make a tiling of the plane with those shapes
\ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \ \ / / \ \ / / \ \ / --*-----* *-----*-----* *-----*-- / \ \ / / \ \ / / \ \ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \ \ / / \ \ / / \ \ / --*-----* *-----*-----* *-----*-- / \ \ / / \ \ / / \ \ \ / / \ \ / / *-----*-----* *-----*-----* / / \ \ / / \ \
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.
arms
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.
arms => 6
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, and every edge between the points is traversed once.
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
Ndigit 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
The direction at N, ie. the total cumulative turn, is given by the number of 1s in N 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.
See "FUNCTIONS" in Math::PlanePath for the 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.
$n
$n < 0
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.
$x,$y
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.
$n = $path->n_start()
Return 0, the first N in the path.
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().
xy_to_n()
n_to_xy()
xy_to_n_list()
The six edges are three going towards the point and three going away. The midpoing 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.
The terdragon is in Sloane's Online Encyclopedia of Integer Sequences as the turn at each line segment,
http://oeis.org/A080846 etc A080846 -- turn 0=left,1=right, by 120 degrees A060236 -- turn 1=left,2=right, by 120 degrees A038502 -- without trailing ternary 0s, taken mod 3 is turn 1=L,2=R A026225 -- (3*i+1)*3^j, is N positions of left turns A026179 -- N positions of right turns (except initial 1)
A026179 starts with a value 1 arising from its morphism definition but that value should be skipped to consider it as turns. At N=1 the curve is a left turn.
Math::PlanePath, Math::PlanePath::TerdragonMidpoint, Math::PlanePath::DragonCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012 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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.