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 curve visits "inner" X,Y points three times, and outside points either once or twice. The first triple point is X=1,Y=3 which is N=8, N=11 and N=14. The path N=7,8,9 make a vertex there, as does N=10,11,12 and N=13,14,15. The path touches but doesn't cross itself. The tripled vertices are all like this, touching but not crossing, 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 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 = $path->n_start()
Return 0, the first N in the path.
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 -- trim 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 -- gives 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.
xy_to_n() is a bit slow due to doing a crude backtracking digits search.
xy_to_n()
Math::PlanePath, Math::PlanePath::DragonCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2010, 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.