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
           /       \         /       \
     31/34          26/29/32            27
          \        /         \
           24/33/42            22/25
          /        \         /       \
  40/43/46          20/23/44          12/21           10
           \       /        \        /      \      /       \
              18/45 -------- 13/16/19        8/11/14 -------- 9
                    \       /       \      /      \
                        17             6/15 --------- 4/7
                                            \       /     \
                                               2/5 ---------  3
                                                   \
                                         0 ----------- 1

                  ^    ^    ^    ^    ^   ^    ^
                 -5   -4   -3   -2   -1  X=0   1 ...

The curve visits "inside" X,Y points three times. The first of these is X=1,Y=3 which is N=8, N=11 and N=14. The corners N=7,8,9, N=10,11,12 and N=13,14,15 have touched, but the path doesn't cross itself. The tripled vertices are all like this, touching but not crossing, and no edges repeating.

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 N=3^level which is level*30 degrees around,

    N       X,Y     angle
   ----    -----    -----
     1      1,0        0
     3      3,1       30
     9                60
    27      0,6       90
    81               120
   243               150
   ...

Here's points N=0 to N=3^6=729 with the N=729 end at the "+" mark. It's gone half-circle around to 180 degrees,

                               * *               * *
                            * * * *           * * * *
                           * * * *           * * * *
                            * * * * *   * *   * * * * *   * *
                         * * * * * * * * * * * * * * * * * * *
                        * * * * * * * * * * * * * * * * * * *
                         * * * * * * * * * * * * * * * * * * * *
                            * * * * * * * * * * * * * * * * * * *
                           * * * * * * * * * * * *   * *   * * *
                      * *   * * * * * * * * * * * *           * *
     * +           * * * * * * * * * * * * * * * *           * *
    * *           * * * * * * * * * * * *   * *
     * * *   * *   * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * * * *
     * * * * * * * * * * * * * * * * * * * *
        * * * * * * * * * * * * * * * * * * *
       * * * * * * * * * * * * * * * * * * *
        * *   * * * * *   * *   * * * * *
                 * * * *           * * * *
                * * * *           * * * *
                 * *               * *

Turns

At each point N the curve always turns 120 degrees either to the left or right, it never goes straight ahead. The ternary digit above the lowest 1 in N gives the turn direction.

...

For example at N=11 shown above the curve has just gone downwards from N=11. N=12 is binary 0b1100, the lowest 1 bit is the 0b.1.. and the bit above that is a 1, which means turn to the right. Whereas later at N=18 which has gone downwards from N=17 it's N=18 in binary 0b10010, the lowest 1 is 0b...1., and the bit above that is 0, so turn left.

...

The bits also give turn after the next by taking the bit above the lowest 0. For example at N=12 the lowest 0 is the least significant bit, and above that is a 0 too, so after going to N=13 the next turn is then to the left to go to N=14. Or for N=18 the lowest 0 is again the least significant bit, but above that is a 1 too, so after going to N=19 the next turn is to the right to go to N=20.

Arms

The curve fills a quarter 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.

     17 --- 13/6 --- 0/1/2/3 --- 4/15 --- 19

With four arms every X,Y point is visited twice (except the origin 0,0 where all four 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 => 2)

Create and return a new path object.

($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.

The optional arms parameter can trace 1 to 4 copies of the curve, each arm successively advancing.

$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 visits an $x,$y twice for various points (all the "inside" points). In the current code the smaller of the two 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
    A060236 -- turn 1=left, 2=right
    A026225 -- N positions of left turns
    A026179 -- N positions of right turns

SEE ALSO

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

cpanm App::MathImage

perl -MCPAN -e shell
install App::MathImage