Math::...onCurve(3pm)
🦋 Math::PlanePath::TerdragonCurve(3pm) 🦋
okay bestie, this is the User Contributed Perl Documentation page for Math::PlanePath::TerdragonCurve, aka the triangular dragon curve. It's giving iconic fractal energy. Let's go. 💅
🌸 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 💖
okay so this is the terdragon curve by Davis and Knuth. The receipts are:
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>
The points sit on a triangular grid, using every second integer X,Y, just like "Triangular Lattice" in Math::PlanePath says. It starts like this:
\ / \
--- 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 3The base figure is lowkey an "S" shape:
2-----3
\
\
0-----1and then it repeats in a self-similar way, so N=3 to N=6 is a copy rotated +120 degrees, which is literally 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-----1Then N=6 to N=9 is just a plain horizontal, which is the angle of N=2 to N=3, no rotation, periodt:
8-----9 base figure repeats
\ as N=6 to N=9,
\ no rotation
6----7,4
\ / \
\ / \
5,2----3
\
\
0-----1Notice that 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. slay.
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. iconic.
🌀 Spiralling 🌀
The first step N=1 is to the right along the X axis, and then the path slowly spirals anti-clockwise and progressively fatter. The end of each replication is
Nlevel = 3^levelThat 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 180The 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 *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *🧩 Tiling 🧩
The little "S" shapes of the base figure N=0 to N=3 can be thought of as a rhombus:
2-----3
. .
. .
0-----1The "S" shapes of each 3 points make a tiling of the plane with those rhombi:
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \
\ / / \ \ / / \ \ /
--*-----* *-----*-----* *-----*--
/ \ \ / / \ \ / / \
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \
\ / / \ \ / / \ \ /
--*-----* *-----o-----* *-----*--
/ \ \ / / \ \ / / \
\ \ / / \ \ / /
*-----*-----* *-----*-----*
/ / \ \ / / \ \Which is literally an ancient pattern,
<http://tilingsearch.org/HTML/data23/C07A.html>🦾 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. no cap.
🛠️ 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$non the path. Points begin at 0 and if$n < 0then 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,$ythen 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,-1For 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 + ($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.
🧮 FORMULAS 🧮
okay so all the boundary length, area and more math? the author wrote it all up in a mathematical write-up, go look:
<http://user42.tuxfamily.org/terdragon/index.html>
🔢 N to X,Y 🔢
bestie, there's no reversals or reflections in the curve at all, so n_to_xy() can take the digits of N either low to high or high to low and apply what's effectively powers of the N=3 position. The current code goes low to high using i,j,k coordinates, exactly like it says 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 combo of rotate and offset, like:
digit==1 digit 2
rotate and offset offset at si,sj,sk rotated
^ 2------>
\
\ \
*--- --1 *-- --*You can also think about it in terms of w=1/2+I*sqrt(3)/2, a complex number that's a sixth root of unity. i is the real part, j is in the w direction (60 degrees), and k is in the w^2 direction (120 degrees). si,sj,sk increase as if multiplied by w+1. 💅
🔄 Turn 🔄
At every point N the curve always turns 120 degrees either left or right — it never goes straight ahead. If N is written in ternary then the lowest non-zero digit tells you the turn:
ternary lowest
non-zero digit turn
-------------- -----
1 left
2 rightAt 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 go the same direction, so the next level shape gives you the turn.
2*3^k-------3*3^k
\
\
0-------1*3^k⏭️ Next Turn ⏭️
The next turn — meaning the turn at position N+1 — can be calculated from the ternary digits of N the same kinda way. The lowest non-2 digit gives the turn:
ternary lowest
non-2 digit turn
-------------- -----
0 left
1 rightIf 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 it's 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. ✨
🌀 Total Turn 🌀
The direction at N — the total cumulative turn — comes from the number of 1 digits when N is written in ternary:
direction = (count 1s in ternary N) * 120 degreesFor 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 stay in the "current" direction, unchanged. The segment for digit 1 is rotated +120 degrees. 🎀
🗺️ X,Y to N 🗺️
The current code finds 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 the deets.
👀 X,Y Visited 👀
When arms=6 all "even" points of the plane get visited. As per the triangular representation of X,Y that means:
X+Y mod 2 == 0 "even" points🔍 OEIS 🔍
The terdragon lives in Sloane's Online Encyclopedia of Integer Sequences as
<http://oeis.org/A080846> (etc)
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)A080846— next turn 0=left,1=right, by 120 degrees (n=0 is turn at N=1)A189673— prev turn 1=left,0=right (morphism, extra initial 0)A038502— strip trailing ternary 0s, taken mod 3 is turn 1=left,2=rightA133162— 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^jso lowest non-zero digit is 1A026179— N positions of right turns (except initial 1) being(3*i+2)*3^jso lowest non-zero digit is 2A060032— bignum turns 1=left,2=right to 3^levelA189674— num left turns 1 to NA189641— num right turns 1 to NA189672— sameA026141— \ dTurnLeft increment between left turns NA026171— /A026181— \ dTurnRight increment between right turns NA131989— /A062756— direction (net total turn), count ternary 1sA005823— N positions where direction = 0, ternary no 1sA023692throughA023698— N positions where direction = 1 to 7, ternary num 1sA111286— boundary length, N=0 to N=3^k, skip initial 1A003945— boundary/2A002023— boundary odd levels N=0 to N=3^(2k+1), or even levels one side N=0 to N=3^(2k), being6*4^kA164346— boundary even levels N=0 to N=3^(2k), or one side, odd levels, N=0 to N=3^(2k+1), being3*4^kA042950— V[k] boundary lengthA056182— area enclosed N=0 to N=3^k, being2*(3^k-2^k)A081956— sameA118004— 1/2 area N=0 to N=3^(2k+1), odd levels,9^n-4^nA155559— join area, being 0 then2^kA099754— 1/2 count distinct visited points N=0 to N=3^kA092236— count East segments N=0 to N=3^k-1A135254— count North-West segments N=0 to N=3^k-1, extra 0A133474— count South-West segments N=0 to N=3^k-1A057083— count segments diff from3^(k-1)A101990— count segments same dir as middle N=0 to N=3^k-1A097038— num runs of 12 consecutive segments within N=0 to 3^k-1, each segment enclosing a new unit triangleA057682— level X, atN=3^level, alsoarms=2level Y, atN=2*3^levelA057083— level Y, atN=3^level, alsoarms=6level X atN=6*3^levelA057681—arms=2level X, atN=2*3^level, alsoarms=3level Y at3*3^levelA103312— same
🏠 HOUSE OF GRAPHS 🏠
House of Graphs entries for the terdragon as a graph include
<https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc
19655— level=0 (1-segment path)594— level=1 (3-segment path)21138— level=221140— level=333761— level=433763— level=5
👋 SEE ALSO 👋
Math::PlanePathMath::PlanePath::TerdragonRoundedMath::PlanePath::TerdragonMidpointMath::PlanePath::GosperSideMath::PlanePath::DragonCurveMath::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/math-planepath/index.html>
📜 LICENSE 📜
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.
fr fr, read the license, bestie, it's the whole point 💀
and that's a wrap, gorgeous 🫶 this whole page is from perl v5.32.0, dated 2021-01-23, and it's the Math::...onCurve(3pm) manual — you read the whole thing, iconic behavior, no cap ✨👑💖
📦 where this page comes from
- debian bookworm: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- debian trixie: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu jammy: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu noble: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu resolute: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu stonking: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on : a language model's rewrite of the original, under its terms