--- name: "Math::PlanePath::GosperReplicate" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::GosperReplicate" --- # Math::PlanePath::GosperReplicate(3pm) ## NAME Math::PlanePath::GosperReplicate -- self-similar hexagon replications ## SYNOPSIS ``` use Math::PlanePath::GosperReplicate; my $path = Math::PlanePath::GosperReplicate->new; my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This is a self-similar hexagonal tiling of the plane. At each level the shape is the Gosper island. ``` 17----16 4 / \ 24----23 18 14----15 3 / \ \ 25 21----22 19----20 10---- 9 2 \ / \ 26----27 3---- 2 11 7---- 8 1 / \ \ 31----30 4 0---- 1 12----13 <- Y=0 / \ \ 32 28----29 5---- 6 45----44 -1 \ / \ 33----34 38----37 46 42----43 -2 / \ \ 39 35----36 47----48 -3 \ 40----41 -4 ^ -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 ``` Points are spread out on every second X coordinate to make a triangular lattice in integer coordinates (see "Triangular Lattice" in Math::PlanePath). The base pattern is the inner N=0 to N=6, then six copies of that shape are arranged around as the blocks N=7,14,21,28,35,42. Then six copies of the resulting N=0 to N=48 shape are replicated around, etc. Each point can be taken as a little hexagon, so that all points tile the plane with hexagons. The innermost N=0 to N=6 are for instance, ``` * * / \ / \ / \ / \ * * * | 3 | 2 | * * * / \ / \ / \ / \ / \ / \ * * * * | 4 | 0 | 1 | * * * * \ / \ / \ / \ / \ / \ / * * * | 5 | 6 | * * * \ / \ / \ / \ / * * ``` The further replications are the same arrangement, but the sides become ever wigglier and the centres rotate around. The rotation can be seen N=7 at X=5,Y=1 which is up from the X axis. The `"FlowsnakeCentres"` path is this same replicating shape, but starting from a side instead of the middle and traversing in such as way as to make each N adjacent. The `"Flowsnake"` curve itself is this replication too, but segments across hexagons. ### Complex Base The path corresponds to expressing complex integers X+i\*Y in a base ``` b = 5/2 + i*sqrt(3)/2 ``` with coordinates scaled to put equilateral triangles on a square grid. So for integer X,Y on the triangular grid (X,Y either both odd or both even), ``` X/2 + i*Y*sqrt(3)/2 = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0] ``` where each digit a\[i\] is either 0 or a sixth root of unity encoded into base-7 digits of N, ``` w6 = e^(i*pi/3) sixth root of unity, b = 2 + w6 = 1/2 + i*sqrt(3)/2 N digit a[i] complex number ------- ------------------- 0 0 1 w6^0 = 1 2 w6^1 = 1/2 + i*sqrt(3)/2 3 w6^2 = -1/2 + i*sqrt(3)/2 4 w6^3 = -1 5 w6^4 = -1/2 - i*sqrt(3)/2 6 w6^5 = 1/2 - i*sqrt(3)/2 ``` 7 digits suffice because ``` norm(b) = (5/2)^2 + (sqrt(3)/2)^2 = 7 ``` ### Rotate Numbering Parameter `"numbering_type => 'rotate'"` applies a rotation in each sub-part according to its location around the preceding level. The effect can be illustrated by writing N in base-7. Part 10-16 is the same as the middle 0-6. Part 20-26 has a rotation by +60 degrees. Part 30-36 has rotation by +120 degrees, and so on. ``` 22----21 / / numbering_type => 'rotate' 31 36 23 20 26 N shown in base-7 / \ \ \ / 32 30 35 24----25 13----12 \ / / \ 33----34 3---- 2 14 10----11 / \ \ 46----45 4 0---- 1 15----16 \ \ 41----40 44 5---- 6 64----63 \ / / \ 42----43 55----54 65 60 62 / \ \ \ / 56 50 53 66 61 / / 51----52 ``` Notice this means in each part the 11, 21, 31, etc, points are directed away from the middle in the same way, relative to the sub-part locations. Working through the expansions gives the following rule for when an N is on the boundary of level k, ``` write N in k many base-7 digits (empty string if k=0) if any 0 digit then non-boundary ignore high digit and all 1 digits if any 4 or 5 digit then non-boundary if any 32, 33, 66 pair then non-boundary ``` A 0 digit is the middle of a block, or 4 or 5 digit the inner side of a block, for k\>=1, hence non-boundary. After that the 6,1,2,3 parts variously expand with rotations so that a 66 is enclosed on the clockwise side and 32 and 33 on the anti-clockwise side. ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. - "$path = Math::PlanePath::GosperReplicate-\>new ()" - "$path = Math::PlanePath::GosperReplicate-\>new (numbering\_type =\> $str)" Create and return a new path object. The `"numbering_type"` parameter can be ``` "fixed" (default) "rotate" ``` - "($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. ### Level Methods - "($n\_lo, $n\_hi) = $path-\>level\_to\_n\_range($level)" Return `"(0, 7**$level - 1)"`. ## FORMULAS ### Axis Rotations In the fixed numbering, digit positions 1,2,3,4,5,6 go around +60deg each, so the N for rotation of X,Y by +60 degrees is each digit +1. ``` N = 0, 1, 2, 3, 4, 5, 6, 10, 11, 12 rot+60(N) = 0, 2, 3, 4, 5, 6, 1, 14, 16, 17, ... decimal = 0, 2, 3, 4, 5, 6, 1, 20, 22, 23, ... base7 rot+120(N) = 0, 3, 4, 5, 6, 1, 2, 21, 24, 25, ... decimal = 0, 3, 4, 5, 6, 1, 2, 30, 33, 34, ... base7 etc ``` In the rotate numbering, just adding +1 (etc) at the high digit alone is rotation. ### X,Y Extents The maximum X in a given level N=0 to 7^k-1 can be calculated from the replications. A given high digit 1 to 6 has sub-parts located at b^k\*w6^(d-1). Those sub-parts are all the same, so the one with maximum real(b^k\*w6^(d-1)) contains the maximum X. ``` N_xmax_digit(j) = d=1to6 where real(w6^(d-1) * b^j) is maximum = 1,1,6,6,6,5,5,5,4,4,4,3,3,3,3,2,2, ... k-1 N_xmax(k) = digits N_xmax_digit(j) low digit j=0 j=0 = 0, 1, 8, 302, 2360, 16766, 100801, ... decimal = 0, 1, 11, 611, 6611, 66611, 566611, ... base7 k-1 z_xmax(k) = sum w6^d[j] * b^j j=0 each d[j] with real(w6^d[j] * b^j) maximum = 0, 1, 7/2+1/2*sqrt3*i, 10-sqrt3*i, 57/2-3/2*sqrt3*i,... xmax(k) = 2*real(z_xmax(k)) = 0, 2, 7, 20, 57, 151, 387, 1070, 2833, 7106, ... ``` For computer calculation these maximums can be calculated from the powers. The parts resulting can also be written in terms of the angle ``` arg(b) = atan(sqrt(3)/5) = 19.106... degrees ``` For successive k, if adding this pushes the b^k angle past +30deg then the preceding digit goes past -30deg and becomes the new maximum X. Write the angle as a fraction of 60deg (pi/3), ``` F = atan(sqrt(3)/5) / (pi/3) = 0.318443 ... ``` This is irrational since b^k is never on the X or Y axes. That can be seen since 2/sqrt3\*imag(b^k) mod 7 goes in a repeating pattern 1,5,4,6,2,3. Similarly 2\*real(b^k) mod 7 so not on the Y axis, and also anything on the Y axis would have 3\*k fall on the X axis. Digits low to high are successive steps back cyclically 6,5,4,3,2,1 so that (with mod giving 0 to 5), ``` N_xmax_digit(j) = (-floor(F*j+1/2) mod 6) + 1 ``` The +1/2 is since initial direction b^0=1 is angle 0 which is half way between -30 and +30 deg. Similarly for the location, using conj(w6) for rotation back ``` z_xmax_exp(j) = floor(F*j+1/2) = 0,0,1,1,1,2,2,2,3,3,3,4,4,4,4,5,5,5, ... z_xmax(k) = sum(j=0,k-1, conj(w6)^z_xmax_exp(j) * b^j) ``` By symmetry the maximum extent is the same in 60deg, 120deg, etc directions, suitably rotated. The N in those cases has the digits 1,2,3,4,5,6 cycled around for the rotation. In PlanePath triangular X,Y coordinates direction 60deg means when sum X+3\*Y is a maximum, etc. If the +1/2 in the floor is omitted then the effect is to find the maximum point in direction +30deg. In the PlanePath coordinates this means maximum sum S = X+Y. ``` N_smax_digit(j) = (-floor(F*j) mod 6) + 1 = 1,1,1,1,6,6,6,5,5,5,4,4,4,3,3, ... k-1 N_smax(k) = digits N_smax_digit(j) low digit j=0 j=0 = 0, 1, 8, 57, 400, 14806, 115648, ... decimal = 0, 1, 11, 111, 1111, 61111, 661111, ... base7 and also N_smax() + 1 z_smax_exp(j) = floor(F*j) = 0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6, ... z_smax(k) = sum(j=0,k-1, conj(w6)^z_smax_exp(j) * b^j) = 0, 1, 7/2+1/2*sqrt3*i, 9+3*sqrt3*i, 19+12*sqrt3*i, ... and also z_smax() + w6^2 smax(k) = 2*real(z_smax(k)) + imag(z_smax(k))*2/sqrt3 = 0, 2, 8, 24, 62, 172, 470, 1190, 3202, 8740, ... coordinate sum X+Y max ``` In the base figure, points 1 and 2 have the same X+Y=2 and this remains so in subsequent levels, so that for k\>=1 N\_smax(k) and N\_smax(k)+1 are equal maximums. ## SEE ALSO Math::PlanePath, Math::PlanePath::GosperIslands, Math::PlanePath::Flowsnake, Math::PlanePath::FlowsnakeCentres, Math::PlanePath::QuintetReplicate, Math::PlanePath::ComplexPlus ## HOME PAGE \ ## LICENSE Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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 \.