Math::PlanePath::ComplexMinus -- twindragon and other complex number base i-r
use Math::PlanePath::ComplexMinus; my $path = Math::PlanePath::ComplexMinus->new (realpart=>1); my ($x, $y) = $path->n_to_xy (123);
This path traverses points by a complex number base i-r for integer r. The default is base i-1 giving the "twindragon" shape.
26 27 10 11 3 24 25 8 9 2 18 19 30 31 2 3 14 15 1 16 17 28 29 0 1 12 13 <- Y=0 22 23 6 7 58 59 42 43 -1 20 21 4 5 56 57 40 41 -2 50 51 62 63 34 35 46 47 -3 48 49 60 61 32 33 44 45 -4 54 55 38 39 -5 52 53 36 37 -6 ^ -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7
In base b=i-1 a complex integer can be represented
X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
The digits a[n] to a[0] are all either 0 or 1. N is those a[i] as bits and X,Y is the resulting complex number. It can be shown that this is a one-to-one transformation so every integer point of the plane is visited.
The shape of an N=0 to N=2^level-1 range is repeated in the next N=2^level to N=(2*2^level)-1. For example N=0 to N=7 is repeated as N=8 to N=15, starting at X=2,Y=2 instead of the origin. That 2,2 is because b^3 = 2+2i. There's no rotations or mirroring etc in this replication, just the position.
N=0 to N=7 N=8 to N=15 repeat shape 2 3 10 11 0 1 8 9 6 7 14 15 4 5 12 13
For b=i-1 each N=2^level point starts at b^level. The powering of that b means the start rotates around by +135 degrees each time and outward by a radius factor sqrt(2) each time. So for example b^3 = 2+2i is followed by b^4 = -4, which is 135 degrees around, and radius |b^3|=sqrt(8) becomes |b^4|=sqrt(16).
The realpart => $r option gives a complex base b=i-r for a given r>=1. For example realpart => 2 is
realpart => $r
realpart => 2
20 21 22 23 24 4 15 16 17 18 19 3 10 11 12 13 14 2 5 6 7 8 9 1 45 46 47 48 49 0 1 2 3 4 <- Y=0 40 41 42 43 44 -1 35 36 37 38 39 -2 30 31 32 33 34 -3 70 71 72 73 74 25 26 27 28 29 -4 65 66 67 68 69 -5 60 61 62 63 64 -6 55 56 57 58 59 -7 50 51 52 53 54 -8 ^ -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9 10
N is broken into digits of base norm=r*r+1, ie. digits 0 to r*r inclusive. This makes horizontal runs of r*r+1 many points, such as N=0 to N=4 then N=5 to N=9 etc above. In the default r=1 these runs are 2 long, whereas for r=2 they're 2*2+1=5 long, or r=3 would be 3*3+1=10, etc.
The offset back for each run like N=5 shown is the r in i-r, then the next level is (i-r)^2 = (-2r*i + r^2-1) so N=25 begins at Y=-2*2=-4, X=2*2-1=3.
The successive replications tile the plane for any r, though the N values needed to rotate around and do so might become large if the norm=r*r+1 is large.
The i-1 twindragon is generally conceived as taking fractional N like 0.abcde in binary and giving fractional complex X+iY. The twindragon is then all the points of the complex plane reached by such fractional N. Those points can be shown to be connected and completely cover a certain radius around the origin.
The code here might be pressed into use for that for a finite number of bits of N by multiplying up to an integer
Nint = Nfrac * 256^k Xfrac = Xint / 16^k Yfrac = Yint / 16^k
256 is a good base because b^8=16 is a positive real and means there's no rotations to apply to the X,Y, just a division by (b^8)^k. b^4=-4 for multiplier 16^k and divisor (-4)^k would be almost as easy.
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::ComplexMinus->new ()
$path = Math::PlanePath::ComplexMinus->new (realpart => $r)
Create and return a new path object.
($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 should be an integer, it's unspecified yet what will be done for a fraction.
A given X,Y representing X+Yi can be broken into digits of N by complex division by i-r, with each digit being a remainder 0 to r*r inclusive.
As per the base formula above
and the target is the a[0] digit 0 to r*r. Taking that digit out and dividing down will be
(X+Yi - digit) / (i-r) = - (X-digit + Y*i) * (i+r) / norm = (Y - (X-digit)*r)/norm + i * - ((X-digit) + Y*r)/norm
ie.
X <- Y - (X-digit)*r)/norm Y <- -((X-digit) + Y*r)/norm
The digit must make both X and Y real and imaginary parts integers. The easiest to calculate from is the imaginary part,
- ((X-digit) + Y*r) == 0 mod norm
so
digit = X + Y*r mod norm
With that digit value the real part is a multiple of norm too,
Y - (X-digit)*r = Y - X*r - (X+Y*r)*r = Y - X*r - X*r + Y*r*r = Y*(r*r+1) = Y*norm
Notice the new Y is the quotient, rounded towards negative infinity, from (X+Y*r)/norm. Ie. in the division the quotient is the new Y and the remainder is the digit.
Math::PlanePath, Math::PlanePath::DragonCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011 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.