Kevin Ryde > Math-PlanePath-113 > Math::PlanePath::R5DragonCurve

Download:
Math-PlanePath-113.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 2
View/Report Bugs
Module Version: 113   Source   Latest Release: Math-PlanePath-114

# 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, as per the direction of the N=1 to N=2 segment.

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

This replication is similar to the `TerdragonCurve` in that there's no reversals or mirroring. Each replication is the plain base curve.

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 at corners like N=4 and N=8 above, but no edges repeat.

## Spiralling

The first step N=1 is to the right along the X axis and the path then slowly spirals anti-clockwise and progressively fatter. The end of each replication is

`    Nlevel = 5^level`

That point is at arctan(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.

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

```    arms => 4
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.

## Tiling

The little "S" shapes of the N=0to5 base shape tile the plane with 2x1 bricks and 1x1 holes in the following pattern,

```     |         |    |    |    |         |    |    |    |
|---------+---------|    |---------+---------|    |-
|    |    |         |    |    |    |         |    |
|    |    |         |    |    |    |         |    |
------|    |---------+---------|    |---------+------
|    |    |    |         |    |    |    |
|    |    |    |         |    |    |    |
------+---------|    |---------+---------|    |------
|    |         |    |    |    |         |    |    |
|    |         |    |    |    |         |    |    |
-|    |---------+---------|    |---------+---------|
|    |    |    |         |    |    |    |         |
|    |    |    |         |    |    |    |         |
-+---------|    |---------o---------|    |---------+-
|         |    |    |    |         |    |    |    |
|         |    |    |    |         |    |    |    |
|---------+---------|    |---------+---------|    |-
|    |    |         |    |    |    |         |    |
|    |    |         |    |    |    |         |    |
------|    |---------+---------|    |---------+------
|    |    |    |         |    |    |    |
|    |    |    |         |    |    |    |
------+---------|    |---------+---------|    |------
|    |         |    |    |    |         |    |    |
|    |         |    |    |    |         |    |    |
-|    |---------+---------|    |---------+---------|
|    |    |    |         |    |    |    |         |```

This is simply the curve with segment N=2mod5 to N=3mod5 omitted from each mod5 block. In each 2x1 block the "S" traverses 4 of the 6 edges and the way the curve meshes together traverses the other 2 edges in another brick, possibly a brick on another arm of the curve.

This tiling is also for example

http://tilingsearch.org/HTML/data182/AL04.html

Or with enlarged square part, http://tilingsearch.org/HTML/data149/L3010.html

# FUNCTIONS

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

`\$path = Math::PlanePath::R5DragonCurve->new ()`
`\$path = Math::PlanePath::R5DragonCurve->new (arms => 4)`

Create and return a new path object.

The optional `arms` parameter can make 1 to 4 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 `\$n` gives 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` twice. 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 or two N's for a given `\$x,\$y`.

`\$n = \$path->n_start()`

Return 0, the first N in the path.

# FORMULAS

## Turn

At each point N the curve always turns 90 degrees either to the left or right, it never goes straight ahead. As per the code in Jorg Arndt's fxtbook, if N is written in base 5 then the lowest non-zero digit gives the turn

```    lowest non-0 digit     turn
------------------     ----
1              left
2              left
3              right
4              right```

At a point N=digit*5^level for digit=1,2,3,4 the turn follows the shape at that digit, so two lefts then two rights,

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

The first and last unit segments in each level are the same direction, so at those endpoints it's the next level up which gives the turn.

## Next Turn

The turn at N+1 can be calculated in a similar way but from the lowest non-4 digit.

```    lowest non-4 digit     turn
------------------     ----
0              left
1              left
2              right
3              right```

This works simply because in N=...z444 becomes N+1=...(z+1)000 and the turn at N+1 is given by digit z+1.

## Total Turn

The direction at N, ie. the total cumulative turn, is given by the direction of each digit when N is written in base 5,

```    digit       direction
0             0
1             1
2             2
3             1
4             0

direction = (sum direction for each digit) * 90 degrees```

For example N=13 is base5 23 so direction=(2+1)*90 = 270 degrees, ie. south.

Because there's no reversals etc in the replications there's no state to maintain when considering the digits, just a plain sum of direction for each digit.

# OEIS

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

```    A175337    next turn 0=left,1=right
(n=0 is the turn at N=1)

arms=1 and arms=3
A059841    abs(dX), being 1,0 repeating
A000035    abs(dY), being 0,1 repeating

arms=4
A165211    abs(dY), being 0,1,0,1,1,0,1,0 repeating```

# HOME PAGE

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

# LICENSE

Copyright 2012, 2013 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/>.

syntax highlighting: