search.cpan.org is shutting down
For details read Perl NOC. After June 25th this page will redirect to MetaCPAN.org
Kevin Ryde > Math-PlanePath > Math::PlanePath::TerdragonCurve

Download:
Math-PlanePath-126.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 0
View/Report Bugs
Module Version: 126

# 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,

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.

## 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 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 *
* *           * * * * * * * * * * * *   * *
* * *   * *   * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* *   * * * * *   * *   * * * * *
* * * *           * * * *
* * * *           * * * *
* *               * *```

## Tiling

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,

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.

# 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. `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,-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```

## 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

Various formulas for boundary length, area and more can be found in the author's mathematical write-up

http://user42.tuxfamily.org/terdragon/index.html

## 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 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.

## 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 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```

## 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 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.

## 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.

The segments for digit 0 or 2 are in the "current" direction unchanged. The segment for digit 1 is rotated +120 degrees.

## X,Y to N

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.

## 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,

```    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

House of Graphs entries for the terdragon as a graph include

level=2, https://hog.grinvin.org/ViewGraphInfo.action?id=21138
level=3, https://hog.grinvin.org/ViewGraphInfo.action?id=21140

# SEE ALSO

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 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/>.

syntax highlighting: