1Math::PlanePath::ZOrderUCsuerrveC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::ZOrderCurve(3)
2
6 Math::PlanePath::ZOrderCurve -- alternate digits to X and Y
7
9 use Math::PlanePath::ZOrderCurve;
10 my $path = Math::PlanePath::ZOrderCurve->new;
12 my ($x, $y) = $path->n_to_xy (123);
13 # or another radix digits ...
15 my $path3 = Math::PlanePath::ZOrderCurve->new (radix => 3);
16
18 This path puts points in a self-similar Z pattern described by G.M.
19 Morton,
20 7 | 42 43 46 47 58 59 62 63
22 6 | 40 41 44 45 56 57 60 61
23 5 | 34 35 38 39 50 51 54 55
24 4 | 32 33 36 37 48 49 52 53
25 3 | 10 11 14 15 26 27 30 31
26 2 | 8 9 12 13 24 25 28 29
27 1 | 2 3 6 7 18 19 22 23
28 Y=0 | 0 1 4 5 16 17 20 21 64 ...
29 +---------------------------------------
30 X=0 1 2 3 4 5 6 7 8
31 The first four points make a "Z" shape if written with Y going
33 downwards (inverted if drawn upwards as above),
34 0---1 Y=0
36 /
37 /
38 2---3 Y=1
39 Then groups of those are arranged as a further Z, etc, doubling in size
41 each time.
42 0 1 4 5 Y=0
44 2 3 --- 6 7 Y=1
45 /
46 /
47 /
48 8 9 --- 12 13 Y=2
49 10 11 14 15 Y=3
50 Within an power of 2 square 2x2, 4x4, 8x8, 16x16 etc (2^k)x(2^k), all
52 the N values 0 to 2^(2*k)-1 are within the square. The top right
53 corner 3, 15, 63, 255 etc of each is the 2^(2*k)-1 maximum.
54 Along the X axis N=0,1,4,5,16,17,etc is the integers with only digits
56 0,1 in base 4. Along the Y axis N=0,2,8,10,32,etc is the integers with
57 only digits 0,2 in base 4. And along the X=Y diagonal N=0,3,12,15,etc
58 is digits 0,3 in base 4.
59 In the base Z pattern it can be seen that transposing to Y,X means
61 swapping parts 1 and 2. This applies in the sub-parts too so in
62 general if N is at X,Y then changing base 4 digits 1<->2 gives the N at
63 the transpose Y,X. For example N=22 at X=6,Y=1 is base-4 "112", change
64 1<->2 is "221" for N=41 at X=1,Y=6.
65 Power of 2 Values
67 Plotting N values related to powers of 2 can come out as interesting
68 patterns. For example displaying the N's which have no digit 3 in
69 their base 4 representation gives
70 *
72 * *
73 * *
74 * * * *
75 * *
76 * * * *
77 * * * *
78 * * * * * * * *
79 * *
80 * * * *
81 * * * *
82 * * * * * * * *
83 * * * *
84 * * * * * * * *
85 * * * * * * * *
86 * * * * * * * * * * * * * * * *
87 The 0,1,2 and not 3 makes a little 2x2 "L" at the bottom left, then
89 repeating at 4x4 with again the whole "3" position undrawn, and so on.
90 This is the Sierpinski triangle (a rotated version of
91 Math::PlanePath::SierpinskiTriangle). The blanks are also a visual
92 representation of 1-in-4 cross-products saved by recursive use of the
93 Karatsuba multiplication algorithm.
94 Plotting the fibbinary numbers (eg. Math::NumSeq::Fibbinary) which are
96 N values with no adjacent 1 bits in binary makes an attractive tree-
97 like pattern,
98 *
100 **
101 *
102 ****
103 *
104 **
105 * *
106 ********
107 *
108 **
109 *
110 ****
111 * *
112 ** **
113 * * * *
114 ****************
115 * *
116 ** **
117 * *
118 **** ****
119 * *
120 ** **
121 * * * *
122 ******** ********
123 * * * *
124 ** ** ** **
125 * * * *
126 **** **** **** ****
127 * * * * * * * *
128 ** ** ** ** ** ** ** **
129 * * * * * * * * * * * * * * * *
130 ****************************************************************
131 The horizontals arise from N=...0a0b0c for bits a,b,c so Y=...000 and
133 X=...abc, making those N values adjacent. Similarly N=...a0b0c0 for a
134 vertical.
135 Radix
137 The "radix" parameter can do the same N <-> X/Y digit splitting in a
138 higher base. For example radix 3 makes 3x3 groupings,
139 radix => 3
141 5 | 33 34 35 42 43 44
143 4 | 30 31 32 39 40 41
144 3 | 27 28 29 36 37 38 45 ...
145 2 | 6 7 8 15 16 17 24 25 26
146 1 | 3 4 5 12 13 14 21 22 23
147 Y=0 | 0 1 2 9 10 11 18 19 20
148 +--------------------------------------
149 X=0 1 2 3 4 5 6 7 8
150 Along the X axis N=0,1,2,9,10,11,etc is integers with only digits 0,1,2
152 in base 9. Along the Y axis digits 0,3,6, and along the X=Y diagonal
153 digits 0,4,8. In general for a given radix it's base R*R with the R
154 many digits of the first RxR block.
155
157 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
158 classes.
159 "$path = Math::PlanePath::ZOrderCurve->new ()"
161 "$path = Math::PlanePath::ZOrderCurve->new (radix => $r)"
162 Create and return a new path object. The optional "radix"
163 parameter gives the base for digit splitting (the default is
164 binary, radix 2).
165 "($x,$y) = $path->n_to_xy ($n)"
167 Return the X,Y coordinates of point number $n on the path. Points
168 begin at 0 and if "$n < 0" then the return is an empty list.
169 Fractional positions give an X,Y position along a straight line
171 between the integer positions. The lines don't overlap, but the
172 lines between bit squares soon become rather long and probably of
173 very limited use.
174 "$n = $path->xy_to_n ($x,$y)"
176 Return an integer point number for coordinates "$x,$y". Each
177 integer N is considered the centre of a unit square and an "$x,$y"
178 within that square returns N.
179 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
181 The returned range is exact, meaning $n_lo and $n_hi are the
182 smallest and biggest in the rectangle.
183 Level Methods
185 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
186 Return "(0, $radix**(2*$level) - 1)".
187
189 N to X,Y
190 The coordinate calculation is simple. The bits of X and Y are every
191 second bit of N. So if N = binary 101010 then X=000 and Y=111 in
192 binary, which is the N=42 shown above at X=0,Y=7.
193 With the "radix" parameter the digits are treated likewise, in the
195 given radix rather than binary.
196 If N includes a fraction part then it's applied to a straight line
198 towards point N+1. The +1 of N+1 changes X and Y according to how many
199 low radix-1 digits there are in N, and thus in X and Y. In general if
200 the lowest non radix-1 is in X then
201 dX=1
203 dY = - (R^pos - 1) # pos=0 for lowest digit
204 The simplest case is when the lowest digit of N is not radix-1, so
206 dX=1,dY=0 across.
207 If the lowest non radix-1 is in Y then
209 dX = - (R^(pos+1) - 1) # pos=0 for lowest digit
211 dY = 1
212 If all digits of X and Y are radix-1 then the implicit 0 above the top
214 of X is considered the lowest non radix-1 and so the first case
215 applies. In the radix=2 above this happens for instance at N=15 binary
216 1111 so X = binary 11 and Y = binary 11. The 0 above the top of X is
217 at pos=2 so dX=1, dY=-(2^2-1)=-3.
218 Rectangle to N Range
220 Within each row the N values increase as X increases, and within each
221 column N increases with increasing Y (for all "radix" parameters).
222 So for a given rectangle the smallest N is at the lower left corner
224 (smallest X and smallest Y), and the biggest N is at the upper right
225 (biggest X and biggest Y).
226
228 This path is in Sloane's Online Encyclopedia of Integer Sequences in
229 various forms,
230 <http://oeis.org/A059905> (etc)
232 radix=2
234 A059905 X coordinate
235 A059906 Y coordinate
236 A000695 N on X axis (base 4 digits 0,1 only)
238 A062880 N on Y axis (base 4 digits 0,2 only)
239 A001196 N on X=Y diagonal (base 4 digits 0,3 only)
240 A057300 permutation N at transpose Y,X (swap bit pairs)
242 radix=3
244 A163325 X coordinate
245 A163326 Y coordinate
246 A037314 N on X axis, base 9 digits 0,1,2
247 A208665 N on X=Y diagonal, base 9 digits 0,3,6
248 A163327 permutation N at transpose Y,X (swap trit pairs)
249 radix=4
251 A126006 permutation N at transpose Y,X (swap digit pairs)
252 radix=10
254 A080463 X+Y of radix=10 (from N=1 onwards)
255 A080464 X*Y of radix=10 (from N=10 onwards)
256 A080465 abs(X-Y), from N=10 onwards
257 A051022 N on X axis (base 100 digits 0 to 9)
258 radix=16
260 A217558 permutation N at transpose Y,X (swap digit pairs)
261 And taking X,Y points in the Diagonals sequence then the value of the
263 following sequences is the N of the "ZOrderCurve" at those positions.
264 radix=2
266 A054238 numbering by diagonals, from same axis as first step
267 A054239 inverse permutation
268 radix=3
270 A163328 numbering by diagonals, same axis as first step
271 A163329 inverse permutation
272 A163330 numbering by diagonals, opp axis as first step
273 A163331 inverse permutation
274 "Math::PlanePath::Diagonals" numbers points from the Y axis down, which
276 is the opposite axis to the "ZOrderCurve" first step along the X axis,
277 so a transpose is needed to give A054238.
278
280 Math::PlanePath, Math::PlanePath::PeanoCurve,
281 Math::PlanePath::HilbertCurve, Math::PlanePath::ImaginaryBase,
282 Math::PlanePath::CornerReplicate, Math::PlanePath::DigitGroups
283 "http://www.jjj.de/fxt/#fxtbook" (section 1.31.2)
285 Algorithm::QuadTree, DBIx::SpatialKey
287
289 <http://user42.tuxfamily.org/math-planepath/index.html>
290
292 Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
293 This file is part of Math-PlanePath.
295 Math-PlanePath is free software; you can redistribute it and/or modify
297 it under the terms of the GNU General Public License as published by
298 the Free Software Foundation; either version 3, or (at your option) any
299 later version.
300 Math-PlanePath is distributed in the hope that it will be useful, but
302 WITHOUT ANY WARRANTY; without even the implied warranty of
303 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
304 General Public License for more details.
305 You should have received a copy of the GNU General Public License along
307 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
308perl v5.28.0 2017-12-03 Math::PlanePath::ZOrderCurve(3)