1Math::PlanePath::SquareURseeprliCcoantter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::SquareReplicate(3)
2
6 Math::PlanePath::SquareReplicate -- replicating squares
7
9 use Math::PlanePath::SquareReplicate;
10 my $path = Math::PlanePath::SquareReplicate->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path is a self-similar replicating square,
15 40--39--38 31--30--29 22--21--20 4
17 | | | | | |
18 41 36--37 32 27--28 23 18--19 3
19 | | |
20 42--43--44 33--34--35 24--25--26 2
21 49--48--47 4-- 3-- 2 13--12--11 1
23 | | | | | |
24 50 45--46 5 0-- 1 14 9--10 <- Y=0
25 | | |
26 51--52--53 6-- 7-- 8 15--16--17 -1
27 58--57--56 67--66--65 76--75--74 -2
29 | | | | | |
30 59 54--55 68 63--64 77 72--73 -3
31 | | |
32 60--61--62 69--70--71 78--79--80 -4
33 ^
35 -4 -3 -2 -1 X=0 1 2 3 4
36 The base shape is the initial N=0 to N=8 section,
38 4 3 2
40 5 0 1
41 6 7 8
42 It then repeats with 3x3 blocks arranged in the same pattern, then 9x9
44 blocks, etc.
45 36 --- 27 --- 18
47 | |
48 | |
49 45 0 --- 9
50 |
51 |
52 54 --- 63 --- 72
53 The replication means that the values on the X axis are those using
55 only digits 0,1,5 in base 9. Those to the right have a high 1 digit
56 and those to the left a high 5 digit. These digits are the values in
57 the initial N=0 to N=8 figure which fall on the X axis.
58 Similarly on the Y axis digits 0,3,7 in base 9, or the leading diagonal
60 X=Y 0,2,6 and opposite diagonal 0,4,8. The opposite diagonal digits
61 0,4,8 are 00,11,22 in base 3, so is all the values in base 3 with
62 doubled digits aabbccdd, etc.
63 Level Ranges
65 A given replication extends to
66 Nlevel = 9^level - 1
68 - (3^level - 1) <= X <= (3^level - 1)
69 - (3^level - 1) <= Y <= (3^level - 1)
70 Complex Base
72 This pattern corresponds to expressing a complex integer X+i*Y with
73 axis powers of base b=3,
74 X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
76 using complex digits a[i] encoded in N in integer base 9,
78 a[i] digit N digit
80 ---------- -------
81 0 0
82 1 1
83 i+1 2
84 i 3
85 i-1 4
86 -1 5
87 -i-1 6
88 -i 7
89 -i+1 8
90 Numbering Rotate-4
92 Parameter "numbering_type => 'rotate-4'" applies a rotation to 4
93 directions E,N,W,S for each sub-part according to its position around
94 the preceding level.
95 ^ ^
97 | |
98 +---+---+---+
99 | 4 3 | 2 |-->
100 +---+---+ +
101 <--| 5 | 0>| 1 |-->
102 + +---+---+
103 <--| 6 | 7 8 |
104 +---+---+---+
105 | |
106 v v
107 The effect can be illustrated by writing N in base-9.
109 42--41 48 32--31 38 24--23--22
111 | | | | | | | |
112 43 40 47 33 30 37 25 20--21 numbering_type => 'rotate-4'
113 | | | | | N shown in base-9
114 44--45--46 34--35--36 26--27--28
115 58--57--56 4---3---2 14--13--12
117 | | | | |
118 51--50 55 5 0---1 15 10--11
119 | | | |
120 52--53--54 6---7---8 16--17--18
121 68--67--66 76--75--74 86--85--84
123 | | | | |
124 61--60 65 77 70 73 87 80 83
125 | | | | | | | |
126 62--63--64 78 71--72 88 81--82
127 Parts 10-18 and 20-28 are the same as the middle 0-8. Parts 30-38 and
129 40-48 have a rotation by +90 degrees. Parts 50-58 and 60-68 rotation
130 by +180 degrees, and so on.
131 Notice this means in each part the base-9 points 11, 21, 31, points are
133 directed away from the middle in the same way, relative to the sub-part
134 locations. This gives a reasonably simple way to characterize points
135 on the boundary of a given expansion level.
136 Working through the directions and boundary sides gives a state machine
138 for which unit squares are on the boundary. For level >= 1 a given
139 unit square has one of both of two sides on the boundary.
140 B
142 +-----+
143 | | unit square with expansion direction,
144 | |-> A one or both of sides A,B on the boundary
145 | |
146 +-----+
147 A further low base-9 digit expands the square to a block of 9, with
149 squares then boundary or not. The result is 4 states, which can be
150 expressed by pairs of digits
151 write N in base-9 using level many digits,
153 delete all 2s in 2nd or later digit
154 non-boundary =
155 0 anywhere
156 5 or 6 or 7 in 2nd or later digit
157 pair 13,33,53,73, 14,34,54,74 anywhere
158 pair 43,44, 81,88 at 2nd or later digit
159 Pairs 53,73,54,74 can be checked just at the start of the digits, since
161 5 or 7 anywhere later are non-boundary alone irrespective of what (if
162 any) pair they might make.
163 Numbering Rotate 8
165 Parameter "numbering_type => 'rotate-8'" applies a rotation to 8
166 directions for each sub-part according to its position around the
167 preceding level.
168 ^ ^ ^
170 \ | /
171 +---+---+---+
172 | 4 | 3 | 2 |
173 +---+---+---+
174 <--| 5 | 0>| 1 |-->
175 +---+---+---+
176 | 6 | 7 | 8 |
177 +---+---+---+
178 / | \
179 v v v
180 The effect can be illustrated again by N in base-9.
182 41 48-47 32-31 38 23-22-21
184 |\ | | | | | /
185 42 40 46 33 30 37 24 20 28 numbering_type => 'rotate'
186 | | | | | | N shown in base-9
187 43-44-45 34-35-36 25-26-27
188 58-57-56 4--3--2 14-13-12
190 | | | | |
191 51-50 55 5 0--1 15 10-11
192 | | | |
193 52-53-54 6--7--8 16-17-18
194 67-66-65 76-75-74 85-84-83
196 | | | | | |
197 68 60 64 77 70 73 86 80 82
198 / | | | | | \ |
199 61-62-63 78 71-72 87-88 81
200 Notice this means in each part the 11, 21, 31, etc, points are directed
202 away from the middle in the same way, relative to the sub-part
203 locations.
204
206 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
207 classes.
208 "$path = Math::PlanePath::SquareReplicate->new ()"
210 Create and return a new path object.
211 "($x,$y) = $path->n_to_xy ($n)"
213 Return the X,Y coordinates of point number $n on the path. Points
214 begin at 0 and if "$n < 0" then the return is an empty list.
215 Level Methods
217 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
218 Return "(0, 9**$level - 1)".
219
221 Math::PlanePath, Math::PlanePath::CornerReplicate,
222 Math::PlanePath::LTiling, Math::PlanePath::GosperReplicate,
223 Math::PlanePath::QuintetReplicate
224
226 <http://user42.tuxfamily.org/math-planepath/index.html>
227
229 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
230 This file is part of Math-PlanePath.
232 Math-PlanePath is free software; you can redistribute it and/or modify
234 it under the terms of the GNU General Public License as published by
235 the Free Software Foundation; either version 3, or (at your option) any
236 later version.
237 Math-PlanePath is distributed in the hope that it will be useful, but
239 WITHOUT ANY WARRANTY; without even the implied warranty of
240 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
241 General Public License for more details.
242 You should have received a copy of the GNU General Public License along
244 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
245perl v5.30.1 2020-01-30Math::PlanePath::SquareReplicate(3)