Math::PlanePath::DragonRounded -- dragon curve, with rounded corners
use Math::PlanePath::DragonRounded; my $path = Math::PlanePath::DragonRounded->new; my ($x, $y) = $path->n_to_xy (123);
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.
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
arms
arms => 4
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.
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.
DragonMidpoint
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
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
$n < 0
$n = $path->n_start()
Return 0, the first N in the path.
($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).
(0, 2 * 2**$level - 1)
(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.
The correspondence with the DragonMidpoint noted above allows the method from that module to be used for the rounded xy_to_n().
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.
DragonRounded
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.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include the various DragonCurve sequences at even N, and in addition
DragonCurve
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
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonRounded
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.