Kevin Ryde > Math-PlanePath-113 > Math::PlanePath::TerdragonCurve

Math-PlanePath-113.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 2
View/Report Bugs
Module Version: 113   Source   Latest Release: Math-PlanePath-114

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

```              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 a triangular grid using every second integer X,Y 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 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 N=5 is a repeat of point X=1,Y=1 which is also N=2, and then N=7 repeats the N=4 position X=2,Y=2. Each point 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 can be seen above as N=8, N=11 and N=14.

The curve never crosses itself. The vertices touch as little triangular corners and no edges repeat.

The shape is the same as the `GosperSide`, but the turns here are by 120 degrees each whereas the `GosperSide` is by 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 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 *
* *           * * * * * * * * * * * *   * *
* * *   * *   * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* *   * * * * *   * *   * * * * *
* * * *           * * * *
* * * *           * * * *
* *               * *```

## Tiling

The little "S" shapes of the base figure N=0 to N=3 can be thought of as a parallelogram

```       2-----3
.     .
.     .
0-----1```

The "S" shapes of each 3 points make a tiling of the plane with those parallelograms

```        \     \ /     /   \     \ /     /
*-----*-----*     *-----*-----*
/     / \     \   /     / \     \
\ /     /   \     \ /     /   \     \ /
--*-----*     *-----*-----*     *-----*--
/ \     \   /     / \     \   /     / \
\     \ /     /   \     \ /     /
*-----*-----*     *-----*-----*
/     / \     \   /     / \     \
\ /     /   \     \ /     /   \     \ /
--*-----*     *-----o-----*     *-----*--
/ \     \   /     / \     \   /     / \
\     \ /     /   \     \ /     /
*-----*-----*     *-----*-----*
/     / \     \   /     / \     \```

As per for example

http://tilingsearch.org/HTML/data23/C07A.html

## Arms

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.

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

## 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, at 120 degree angles.

```    dX,dY
-----
2, 0        dX minimum -1, maximum +2   arms == 1
-1, 1        dY minimum -1, maximum +1
1,-1```

For 2 or more arms the second arm is rotated by 60 degrees so giving additional combinations for a total six

```    dX,dY also
-----
-2, 0        dX minimum -2, maximum +2   arms >= 2
1, 1        dY minimum -1, maximum +1
-1,-1```

# FORMULAS

## 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 applying what's in effect 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 as using w=1/2+I*sqrt(3)/2, a complex 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     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```

## 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       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 N=9 turn left.

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

## X,Y to N

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()`.

The six edges are three going towards the point and three going away. The midpoint 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.

## 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)
A189640   turn 0=left,1=right (morphism, extra initial 0)
A189673   turn 1=left,0=right (morphism, extra initial 0)
A038502   strip trailing ternary 0s,
taken mod 3 is turn 1=left,2=right

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

A062756   total turn, count ternary 1s
A005823   N positions where total turn == 0, ternary no 1s```

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.

http://user42.tuxfamily.org/math-planepath/index.html