Kevin Ryde > Math-PlanePath > Math::PlanePath::DragonRounded

Download:
Math-PlanePath-117.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

Open  1
View/Report Bugs
Module Version: 117   Source  

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

http://oeis.org/A152822 (etc)

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

syntax highlighting: