/ 
Math-PlanePath-74
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::R5DragonCurve

NAME

Math::PlanePath::R5DragonCurve -- radix 5 dragon curve

SYNOPSIS

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

DESCRIPTION

This is the R5 dragon curve by Jorg Arndt,

         31-----30     27-----26                                  5
          |      |      |      |
         32---29/33--28/24----25                                  4
                 |      |
         35---34/38--39/23----22     11-----10      7------6      3
                 |             |      |      |      |      |
         36---37/41--20/40--21/17--16/12---13/9----8/4-----5      2
                 |      |      |      |      |      |
--50     47---42/46--19/43----18     15-----14      3------2      1
   |      |      |      |                                  |
49/53--48/64  45/65--44/68    69                    0------1  <-Y=0

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

The base figure is an "S" shape

4----5
|
3----2
     |
0----1

which then repeats in self-similar style, so N=5 to N=10 is a copy rotated +90 degrees, which is the angle of the N=1 to N=2 edge,

10    7----6
 |    |    |  <- repeat rotated +90
 9---8 4---5
       |
       3---2
           |
      0----1

The shape of N=0,5,10,15,20,25 repeats the initial N=0 to N=5,

     25                          4
    /
   /           10__              3
  /           /    ----___
20__         /            5      2
    ----__  /            /
          15            /        1
                      /
                     0       <-Y=0

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

The curve never crosses itself. The vertices touch as corners like N=4 and N=8 but no edges repeat.

Spiralling

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 = 5^level

That point is at atan(2,1)=63.43 degrees further around for each level,

Nlevel     X,Y     angle (degrees)
------    -----    -----
  1        1,0        0
  5        2,1       63.4
 25       -3,4      126.8
125      -11, -2    190.3

Arms

The curve fills a quarter of the plane and four copies mesh together perfectly rotated by 90, 180 and 270 degrees. The arms parameter can choose 1 to 4 such curve arms successively advancing.

For example arms => 4 begins as follows. N=0,4,8,12,16,etc is the first arm (the same shape as the plain curve above), then N=1,5,9,13,17 the second, N=2,6,10,14 the third, etc.

                16/32---20/63
                  |
21/60    9/56----5/12----8/59
  |       |       |       |
17/33--- 6/13--0/1/2/3---4/15---19/35
          |       |       |       |
        10/57----7/14---11/58   23/62
                  |
        22/61---18/34

With four arms every X,Y point is visited twice, except the origin 0,0 where all four 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::R5DragonCurve->new ()
$path = Math::PlanePath::R5DragonCurve->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.

$n = $path->n_start()

Return 0, the first N in the path.

FORMULAS

Turns

At each point N the curve always turns 90 degrees either to the left or right, it never goes straight ahead. If N is written in base 5 then the lowest non-zero digit gives the turn

Ndigit      Turn
------      ----
  1         left
  2         left
  3         right
  4         right

Essentially at a point N=5^level, N=2*3^level, N=3*3^level or N=4*3^level the turn follows the shape at that 1 to 4 multiplier point. The first and last unit step in each level are in the same direction, so the next level shape gives the turn.

4*5^k----5^(k+1)
 |
 |
2*5^k----2*5^k
          |
          |
 0------1*5^k

OEIS

The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences as,

http://oeis.org/A175337  etc

A175337 -- turn 0=left,1=right by 90 degrees at N=n

SEE ALSO

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

HOME PAGE

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

LICENSE

Copyright 2012 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath 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.

Math-PlanePath 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 Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.