# NAME

Math::PlanePath::AlternateTerdragon -- alternate terdragon curve

# SYNOPSIS

`````` use Math::PlanePath::AlternateTerdragon;
my \$path = Math::PlanePath::AlternateTerdragon->new;
my (\$x, \$y) = \$path->n_to_xy (123);``````

# DESCRIPTION

This is the alternate 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

``````                                 \   /       \   /
Y=2                          14,17 --- 15,24,33 --
\       /   \
\   /       \   /
Y=1          2 ------- 3,12 ---- 10,13,34 -- 32,35,38
\       /   \       /   \       /   \
\   /       \   /       \   /
Y=0    0 -------- 1,4 ----- 5,8,11 ----- 9,36 ----
/   \
/       \
Y=-1                     6 --------- 7

^     ^     ^     ^     ^     ^     ^     ^
X=0    1     2     3     4     5     6     7``````

A segment 0 to 1 is unfolded to

``````       2-----3
\
\
0-----1``````

Then 0 to 3 is unfolded likewise, but the folds are the opposite way. Where 1-2 went on the left, for 3-6 goes to the right.

``````       2-----3                   2-----3
\   /                     \   /
\ /                       \ /
0----1,4----5             0----1,4---5,8----9
/                         / \
/                         /   \
6                         6-----7``````

Successive unfolds go alternate ways. Taking two unfold at a time is segment replacement by the 0 to 9 figure (rotated as necessary). The curve never crosses itself. Vertices touch at triangular corners. Points can be visited 1, 2 or 3 times.

The two triangles have segment 4-5 between. In general points to a level N=3^k have a single segment between two blobs, for example N=0 to N=3^6=729 below. But as the curve continues it comes back to put further segments there (and a single segment between bigger blobs).

``````                 * *
* * * *
* * * *
* * * * *   * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * *
* *   * * * * * * * * * * *         * *
* * * * * * * * * * * * *           * * * *
* * * * * * * * * * * * *           * * * *
* * * * * * * * * * * * * *   * *   * * * * *   * *
O * * * * * * * * * * * * * * * * * * * * * * * * * * E
* *   * * * * *   * *   * * * * * * * * * * * * * *
* * * *           * * * * * * * * * * * * *
* * * *           * * * * * * * * * * * * *
* *         * * * * * * * * * * *   * *
* * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* *   * * * * *
* * * *
* * * *
* *``````

The top boundary extent is at an angle +60 degrees and the bottom at -30 degrees,

``````       / 60 deg
/
/
O-------------------
--__
--__ 30 deg``````

An even expansion level is within a rectangle with endpoint at X=2*3^(k/2),Y=0.

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

``````                  \         /             \           /
\       /               \         /
--- 7,8,26 ----------------- 1,12,19 ---
/        \               /         \
\           /          \             /           \          /
\         /            \           /             \        /
--- 3,14,21 ------------- 0,1,2,3,4,5 -------------- 6,11,24 ---
/         \            /           \             /        \
/           \          /             \           /          \
\        /               \         /
---- 9,10,28 ---------------- 5,16,23 ---
/        \               /         \
/          \             /           \``````

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::AlternateTerdragon->new ()`
`\$path = Math::PlanePath::AlternateTerdragon->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``````
`\$sum = \$path->sumxy_minimum()`
`\$sum = \$path->sumxy_maximum()`

Return the minimum or maximum values taken by coordinate sum X+Y reached by integer N values in the path. If there's no minimum or maximum then return `undef`.

S=X+Y is an anti-diagonal. The first arm is entirely above a line 135deg -- -45deg, per the +60deg to -30deg extents shown above. Likewise the second arm which is to 60+60=120deg. They have `sumxy_minimum = 0`. More arms and all `sumxy_maximum` are unbounded so `undef`.

`\$diffxy = \$path->diffxy_minimum()`
`\$diffxy = \$path->diffxy_maximum()`

Return the minimum or maximum values taken by coordinate difference X-Y reached by integer N values in the path. If there's no minimum or maximum then return `undef`.

D=X-Y is a leading diagonal. The first arm is entirely right of a line 45deg -- -135deg, per the +60deg to -30deg extents shown above, so it has `diffxy_minimum = 0`. More arms and all `diffxy_maximum` are unbounded so `undef`.

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

## 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 at its position gives the turn. Positions are counted from 0 for the least significant digit and up from there.

``````   turn          ternary lowest non-zero digit
-----     ---------------------------------------
left      1 at even position or 2 at odd position
right     2 at even position or 1 at odd position``````

The flip of turn at odd positions is the "alternating" in the curve.

``````   next turn         ternary lowest non-2 digit
---------    ---------------------------------------
left       0 at even position or 1 at odd position
right      1 at even position or 0 at odd position``````

## Total Turn

The direction at N, ie. the total cumulative turn, is given by the 1 digits of N written in ternary.

``````    direction = 120deg * sum / +1  if digit=1 at even position
\ -1  if digit=1 at odd position``````

This is used mod 3 for `n_to_dxdy()`.

## X,Y to N

The current code is roughly the same as `TerdragonCurve` `xy_to_n()`, but with a conjugate (negate Y, reverse direction d) after each digit low to high.

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

Sequences in Sloane's Online Encyclopedia of Integer Sequences related to the alternate terdragon include,

``````    A156595   next turn 0=left, 1=right (morphism)
A189715   N positions of left turns
A189716   N positions of right turns
A189717   count right turns so far``````

# HOUSE OF GRAPHS

House of Graphs entries for the alternate terdragon curve as a graph include

``````    19655     level=0 (1-segment path)
594       level=1 (3-segment path)
30397     level=2
30399     level=3
33575     level=4
33577     level=5``````

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