NAME

Math::PlanePath::DragonRounded -- dragon curve, with rounded corners

SYNOPSIS

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

DESCRIPTION

This is a version of the dragon curve by Harter, Heighway, et al, done with two points per edge and skipping vertices so as to make rounded-off corners,

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


      ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^
    -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3 ...

The two points on an edge have one of X or Y a multiple of 3 and the other Y or X at 1 mod 3 or 2 mod 3. For example N=19 and N=20 are on the X=-9 edge (a multiple of 3), and at Y=4 and Y=5 (1 and 2 mod 3).

The "rounding" of the corners ensures that for example N=13 and N=21 don't touch as they approach X=-6,Y=3. The curve always approaches vertices like this and never crosses itself.

Arms

The dragon curve fills a quarter of the plane and four copies mesh together rotated by 90, 180 and 270 degrees. The arms parameter can choose 1 to 4 curve arms, successively advancing. For example arms => 4 gives

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



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

With 4 arms like this all 3x3 blocks are visited, using 4 out of 9 points in each.

Midpoint

The points of this rounded curve correspond to the DragonMidpoint with a little squish to turn each 6x6 block into a 4x4 block. For instance in the following N=2,3 are pushed to the left, and N=6 through N=11 shift down and squashes up horizontally.

     DragonRounded               DragonMidpoint

        9--8                     
       /    \
     10      7                     9---8         
      |      |                     |   |         
     11      6                    10   7         
    /         \                    |   |         
               5--4      <=>     -11   6---5---4 
                   \                           | 
                    3                          3 
                    |                          | 
                    2                          2 
                   /                           | 
             . 0--1                        0---1 
                            

FUNCTIONS

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

$path = Math::PlanePath::DragonRounded->new ()
$path = Math::PlanePath::DragonRounded->new (arms => $aa)

Create and return a new path object.

The optional arms parameter makes a multi-arm curve. The default is 1 for just one arm.

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

$n = $path->n_start()

Return 0, the first N in the path.

Level Methods

($n_lo, $n_hi) = $path->level_to_n_range($level)

Return (0, 2 * 2**$level - 1), or for multiple arms return (0, $arms * 2 * 2**$level - 1).

There are 2^level segments comprising the dragon, or arms*2^level when multiple arms. Each has 2 points in this rounded curve, numbered starting from 0.

FORMULAS

X,Y to N

The correspondence with the DragonMidpoint noted above allows the method from that module to be used for the rounded xy_to_n().

The correspondence essentially reckons each point on the rounded curve as the midpoint of a dragon curve of one greater level of detail, and segments on 45-degree angles.

The coordinate conversion turns each 6x6 block of DragonRounded to a 4x4 block of DragonMidpoint. There's no rotations or anything.

    Xmid = X - floor(X/3) - Xadj[X%6][Y%6]
    Ymid = Y - floor(Y/3) - Yadj[X%6][Y%6]

    N = DragonMidpoint n_to_xy of Xmid,Ymid

    Xadj[][] is a 6x6 table of 0 or 1 or undef
    Yadj[][] is a 6x6 table of -1 or 0 or undef

The Xadj,Yadj tables are a handy place to notice X,Y points not on the DragonRounded style 4 of 9 points. Or 16 of 36 points since the tables are 6x6.

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include the various DragonCurve sequences at even N, and in addition

    A152822   abs(dX), so 0=vertical,1=not, being 1,1,0,1 repeating
    A166486   abs(dY), so 0=horizontal,1=not, being 0,1,1,1 repeating

SEE ALSO

Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonRounded

HOME PAGE

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

LICENSE

Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

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