/ 
math-image-86
River stage zero No dependents
/ Math::PlanePath::MathImageTerdragonCurve

NAME

Math::PlanePath::MathImageTerdragonCurve -- triangular dragon curve

SYNOPSIS

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

DESCRIPTION

In progress ...

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

The curve visits "inner" X,Y points three times, and outside points either once or twice. The first triple point is X=1,Y=3 which is N=8, N=11 and N=14. The curve N=7,8,9 make a vertex there, as does N=10,11,12 and N=13,14,15. The curve touches, but doesn't cross itself. The tripled vertices are all like this, touching but not crossing, and no edges repeat.

The first step N=1 is to the right along the X axis and the path then slowly spirals counter-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 *
* *           * * * * * * * * * * * *   * *
 * * *   * *   * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * * * *
   * * * * * * * * * * * * * * * * * * *
    * *   * * * * *   * *   * * * * *
             * * * *           * * * *
            * * * *           * * * *
             * *               * *

Arms

The curve fills a sixth of the plane and six copies mesh together perfectly when rotated by 60, 120, 180, 240 and 300 degrees. The arms parameter can choose 1 to 6 curve arms successively advancing.

For example arms => 6 begins as follows, with N=0,6,12,18,etc being one arm, 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) and every edge between the points is traversed once.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

$path = Math::PlanePath::MathImageTerdragonCurve->new ()
$path = Math::PlanePath::MathImageTerdragonCurve->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 smaller of the these N values is returned. Is that the best way?

$n = $path->n_start()

Return 0, the first N in the path.

OEIS

The terdragon is in Sloane's Online Encyclopedia of Integer Sequences as the turn at each line segment,

http://oeis.org/A080846  etc

A080846 -- turn 0=left,1=right, by 120 degrees
A060236 -- turn 1=left,2=right, by 120 degrees
A038502 -- taken mod 3 is turn 1=left,2=right
A026225 -- N positions of left turns
A026179 -- N positions of right turns (except initial 1)

A026179 starts with a value 1 arising from its morphism definition but that value should be skipped to consider it as turns. At N=1 the curve is a left turn (value 1 is in the A026225 left turns sequence).

BUGS

xy_to_n() is a bit slow due to doing a crude backtracking digits search.

SEE ALSO

Math::PlanePath, Math::PlanePath::DragonCurve