1Math::PlanePath::ZOrderUCsuerrveC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::ZOrderCurve(3)
2
3
4

NAME

6       Math::PlanePath::ZOrderCurve -- alternate digits to X and Y
7

SYNOPSIS

9        use Math::PlanePath::ZOrderCurve;
10
11        my $path = Math::PlanePath::ZOrderCurve->new;
12        my ($x, $y) = $path->n_to_xy (123);
13
14        # or another radix digits ...
15        my $path3 = Math::PlanePath::ZOrderCurve->new (radix => 3);
16

DESCRIPTION

18       This path puts points in a self-similar Z pattern described by G.M.
19       Morton,
20
21             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
32       The first four points make a "Z" shape if written with Y going
33       downwards (inverted if drawn upwards as above),
34
35            0---1       Y=0
36               /
37             /
38            2---3       Y=1
39
40       Then groups of those are arranged as a further Z, etc, doubling in size
41       each time.
42
43            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
51       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
55       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
60       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
66   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
71           *
72           * *
73           *   *
74           * * * *
75           *       *
76           * *     * *
77           *   *   *   *
78           * * * * * * * *
79           *               *
80           * *             * *
81           *   *           *   *
82           * * * *         * * * *
83           *       *       *       *
84           * *     * *     * *     * *
85           *   *   *   *   *   *   *   *
86           * * * * * * * * * * * * * * * *
87
88       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
95       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
99           *
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
132       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
136   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
140            radix => 3
141
142             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
151       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

FUNCTIONS

157       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
158       classes.
159
160       "$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
166       "($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
170           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
175       "$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
180       "($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
184   Level Methods
185       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
186           Return "(0, $radix**(2*$level) - 1)".
187

FORMULAS

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
194       With the "radix" parameter the digits are treated likewise, in the
195       given radix rather than binary.
196
197       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
202           dX=1
203           dY = - (R^pos - 1)           # pos=0 for lowest digit
204
205       The simplest case is when the lowest digit of N is not radix-1, so
206       dX=1,dY=0 across.
207
208       If the lowest non radix-1 is in Y then
209
210           dX = - (R^(pos+1) - 1)       # pos=0 for lowest digit
211           dY = 1
212
213       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
219   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
223       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

OEIS

228       This path is in Sloane's Online Encyclopedia of Integer Sequences in
229       various forms,
230
231           <http://oeis.org/A059905> (etc)
232
233           radix=2
234             A059905    X coordinate
235             A059906    Y coordinate
236
237             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
241             A057300    permutation N at transpose Y,X (swap bit pairs)
242
243           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 Y axis, base 9 digits 0,3,6
248             A338086    N on X=Y diagonal, base 9 digits 0,4,8
249             A163327    permutation N at transpose Y,X (swap trit pairs)
250
251           radix=4
252             A126006    permutation N at transpose Y,X (swap digit pairs)
253
254           radix=10
255             A080463    X+Y of radix=10 (from N=1 onwards)
256             A080464    X*Y of radix=10 (from N=10 onwards)
257             A080465    abs(X-Y), from N=10 onwards
258             A051022    N on X axis (base 100 digits 0 to 9)
259             A338754    N on X=Y diagonal (double-digits 00 to 99)
260
261           radix=16
262             A217558    permutation N at transpose Y,X (swap digit pairs)
263
264       And taking X,Y points in the Diagonals sequence then the value of the
265       following sequences is the N of the "ZOrderCurve" at those positions.
266
267           radix=2
268             A054238    numbering by diagonals, from same axis as first step
269             A054239      inverse permutation
270
271           radix=3
272             A163328    numbering by diagonals, same axis as first step
273             A163329      inverse permutation
274             A163330    numbering by diagonals, opp axis as first step
275             A163331      inverse permutation
276
277       "Math::PlanePath::Diagonals" numbers points from the Y axis down, which
278       is the opposite axis to the "ZOrderCurve" first step along the X axis,
279       so a transpose is needed to give A054238.
280

SEE ALSO

282       Math::PlanePath, Math::PlanePath::PeanoCurve,
283       Math::PlanePath::HilbertCurve, Math::PlanePath::ImaginaryBase,
284       Math::PlanePath::CornerReplicate, Math::PlanePath::DigitGroups
285
286       "http://www.jjj.de/fxt/#fxtbook" (section 1.31.2)
287
288       Algorithm::QuadTree, DBIx::SpatialKey
289

HOME PAGE

291       <http://user42.tuxfamily.org/math-planepath/index.html>
292

LICENSE

294       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
295       2020 Kevin Ryde
296
297       This file is part of Math-PlanePath.
298
299       Math-PlanePath is free software; you can redistribute it and/or modify
300       it under the terms of the GNU General Public License as published by
301       the Free Software Foundation; either version 3, or (at your option) any
302       later version.
303
304       Math-PlanePath is distributed in the hope that it will be useful, but
305       WITHOUT ANY WARRANTY; without even the implied warranty of
306       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
307       General Public License for more details.
308
309       You should have received a copy of the GNU General Public License along
310       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
311
312
313
314perl v5.34.0                      2021-07-22   Math::PlanePath::ZOrderCurve(3)
Impressum