Math::PlanePath::SquareReplicate -- replicating squares
use Math::PlanePath::SquareReplicate; my $path = Math::PlanePath::SquareReplicate->new; my ($x, $y) = $path->n_to_xy (123);
This path is a self-similar replicating square,
40--39--38 31--30--29 22--21--20 4 | | | | | | 41 36--37 32 27--28 23 18--19 3 | | | 42--43--44 33--34--35 24--25--26 2 49--48--47 4-- 3-- 2 13--12--11 1 | | | | | | 50 45--46 5 0-- 1 14 9--10 <- Y=0 | | | 51--52--53 6-- 7-- 8 15--16--17 -1 58--57--56 67--66--65 76--75--74 -2 | | | | | | 59 54--55 68 63--64 77 72--73 -3 | | | 60--61--62 69--70--71 78--79--80 -4 ^ -4 -3 -2 -1 X=0 1 2 3 4
The base shape is the initial N=0 to N=8 section,
4 3 2 5 0 1 6 7 8
It then repeats with 3x3 blocks arranged in the same pattern, then 9x9 blocks, etc.
36 --- 27 --- 18 | | | | 45 0 --- 9 | | 54 --- 63 --- 72
The replication means that the values on the X axis are those using only digits 0,1,5 in base 9. Those to the right have a high 1 digit and those to the left a high 5 digit. These digits are the values in the initial N=0 to N=8 figure which fall on the X axis.
Similarly on the Y axis digits 0,3,7 in base 9, or the leading diagonal X=Y 0,2,6 and opposite diagonal 0,4,8. The opposite diagonal digits 0,4,8 are 00,11,22 in base 3, so is all the values in base 3 with doubled digits aabbccdd, etc.
A given replication extends to
Nlevel = 9^level - 1 - (3^level - 1) <= X <= (3^level - 1) - (3^level - 1) <= Y <= (3^level - 1)
This pattern corresponds to expressing a complex integer X+i*Y with axis powers of base b=3,
X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
using complex digits a[i] encoded in N in integer base 9,
a[i] digit N digit ---------- ------- 0 0 1 1 i+1 2 i 3 i-1 4 -1 5 -i-1 6 -i 7 -i+1 8
Parameter numbering_type => 'rotate-4'
applies a rotation to 4 directions E,N,W,S for each sub-part according to its position around the preceding level.
^ ^ | | +---+---+---+ | 4 3 | 2 |--> +---+---+ + <--| 5 | 0>| 1 |--> + +---+---+ <--| 6 | 7 8 | +---+---+---+ | | v v
The effect can be illustrated by writing N in base-9.
42--41 48 32--31 38 24--23--22 | | | | | | | | 43 40 47 33 30 37 25 20--21 numbering_type => 'rotate-4' | | | | | N shown in base-9 44--45--46 34--35--36 26--27--28 58--57--56 4---3---2 14--13--12 | | | | | 51--50 55 5 0---1 15 10--11 | | | | 52--53--54 6---7---8 16--17--18 68--67--66 76--75--74 86--85--84 | | | | | 61--60 65 77 70 73 87 80 83 | | | | | | | | 62--63--64 78 71--72 88 81--82
Parts 10-18 and 20-28 are the same as the middle 0-8. Parts 30-38 and 40-48 have a rotation by +90 degrees. Parts 50-58 and 60-68 rotation by +180 degrees, and so on.
Notice this means in each part the base-9 points 11, 21, 31, points are directed away from the middle in the same way, relative to the sub-part locations. This gives a reasonably simple way to characterize points on the boundary of a given expansion level.
Working through the directions and boundary sides gives a state machine for which unit squares are on the boundary. For level >= 1 a given unit square has one of both of two sides on the boundary.
B +-----+ | | unit square with expansion direction, | |-> A one or both of sides A,B on the boundary | | +-----+
A further low base-9 digit expands the square to a block of 9, with squares then boundary or not. The result is 4 states, which can be expressed by pairs of digits
write N in base-9 using level many digits, delete all 2s in 2nd or later digit non-boundary = 0 anywhere 5 or 6 or 7 in 2nd or later digit pair 13,33,53,73, 14,34,54,74 anywhere pair 43,44, 81,88 at 2nd or later digit
Pairs 53,73,54,74 can be checked just at the start of the digits, since 5 or 7 anywhere later are non-boundary alone irrespective of what (if any) pair they might make.
Parameter numbering_type => 'rotate-8'
applies a rotation to 8 directions for each sub-part according to its position around the preceding level.
^ ^ ^ \ | / +---+---+---+ | 4 | 3 | 2 | +---+---+---+ <--| 5 | 0>| 1 |--> +---+---+---+ | 6 | 7 | 8 | +---+---+---+ / | \ v v v
The effect can be illustrated again by N in base-9.
41 48-47 32-31 38 23-22-21 |\ | | | | | / 42 40 46 33 30 37 24 20 28 numbering_type => 'rotate' | | | | | | N shown in base-9 43-44-45 34-35-36 25-26-27 58-57-56 4--3--2 14-13-12 | | | | | 51-50 55 5 0--1 15 10-11 | | | | 52-53-54 6--7--8 16-17-18 67-66-65 76-75-74 85-84-83 | | | | | | 68 60 64 77 70 73 86 80 82 / | | | | | \ | 61-62-63 78 71-72 87-88 81
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.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::SquareReplicate->new ()
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_lo, $n_hi) = $path->level_to_n_range($level)
Return (0, 9**$level - 1)
.
Math::PlanePath, Math::PlanePath::CornerReplicate, Math::PlanePath::LTiling, Math::PlanePath::GosperReplicate, Math::PlanePath::QuintetReplicate
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 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 <http://www.gnu.org/licenses/>.