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 6681 and "Number Representations and Dragon Curves  II", volume 3, number 3 (July 1970), pages 133149.
Reprinted with addendum in Knuth "Selected Papers on Fun and Games", 2010, pages 571614. http://wwwcsfaculty.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
23
\
\
01
Then 0 to 3 is unfolded likewise, but the folds are the opposite way. Where 12 went on the left, for 36 goes to the right.
23 23
\ / \ /
\ / \ /
01,45 01,45,89
/ / \
/ / \
6 67
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 45 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 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,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 antidiagonal. 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 allsumxy_maximum
are unbounded soundef
. $diffxy = $path>diffxy_minimum()
$diffxy = $path>diffxy_maximum()

Return the minimum or maximum values taken by coordinate difference XY reached by integer N values in the path. If there's no minimum or maximum then return
undef
.D=XY 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 alldiffxy_maximum
are unbounded soundef
.
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 + ($arms1))
.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 nonzero digit at its position gives the turn. Positions are counted from 0 for the least significant digit and up from there.
turn ternary lowest nonzero 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 non2 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,
http://oeis.org/A156595 (etc)
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 (1segment path)
594 level=1 (3segment path)
30397 level=2
30399 level=3
33575 level=4
33577 level=5
SEE ALSO
Math::PlanePath, Math::PlanePath::TerdragonCurve
Math::PlanePath::DragonCurve, Math::PlanePath::AlternatePaper
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2018, 2019 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.