.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::ZOrderCurve 3pm" .TH Math::PlanePath::ZOrderCurve 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::ZOrderCurve \-\- alternate digits to X and Y .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 1 \& use Math::PlanePath::ZOrderCurve; \& \& my $path = Math::PlanePath::ZOrderCurve\->new; \& my ($x, $y) = $path\->n_to_xy (123); \& \& # or another radix digits ... \& my $path3 = Math::PlanePath::ZOrderCurve\->new (radix => 3); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path puts points in a self-similar Z pattern described by G.M. Morton, .PP .Vb 10 \& 7 | 42 43 46 47 58 59 62 63 \& 6 | 40 41 44 45 56 57 60 61 \& 5 | 34 35 38 39 50 51 54 55 \& 4 | 32 33 36 37 48 49 52 53 \& 3 | 10 11 14 15 26 27 30 31 \& 2 | 8 9 12 13 24 25 28 29 \& 1 | 2 3 6 7 18 19 22 23 \& Y=0 | 0 1 4 5 16 17 20 21 64 ... \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .PP The first four points make a \*(L"Z\*(R" shape if written with Y going downwards (inverted if drawn upwards as above), .PP .Vb 4 \& 0\-\-\-1 Y=0 \& / \& / \& 2\-\-\-3 Y=1 .Ve .PP Then groups of those are arranged as a further Z, etc, doubling in size each time. .PP .Vb 7 \& 0 1 4 5 Y=0 \& 2 3 \-\-\- 6 7 Y=1 \& / \& / \& / \& 8 9 \-\-\- 12 13 Y=2 \& 10 11 14 15 Y=3 .Ve .PP Within an power of 2 square 2x2, 4x4, 8x8, 16x16 etc (2^k)x(2^k), all the N values 0 to 2^(2*k)\-1 are within the square. The top right corner 3, 15, 63, 255 etc of each is the 2^(2*k)\-1 maximum. .PP Along the X axis N=0,1,4,5,16,17,etc is the integers with only digits 0,1 in base 4. Along the Y axis N=0,2,8,10,32,etc is the integers with only digits 0,2 in base 4. And along the X=Y diagonal N=0,3,12,15,etc is digits 0,3 in base 4. .PP In the base Z pattern it can be seen that transposing to Y,X means swapping parts 1 and 2. This applies in the sub-parts too so in general if N is at X,Y then changing base 4 digits 1<\->2 gives the N at the transpose Y,X. For example N=22 at X=6,Y=1 is base\-4 \*(L"112\*(R", change 1<\->2 is \&\*(L"221\*(R" for N=41 at X=1,Y=6. .SS "Power of 2 Values" .IX Subsection "Power of 2 Values" Plotting N values related to powers of 2 can come out as interesting patterns. For example displaying the N's which have no digit 3 in their base 4 representation gives .PP .Vb 10 \& * \& * * \& * * \& * * * * \& * * \& * * * * \& * * * * \& * * * * * * * * \& * * \& * * * * \& * * * * \& * * * * * * * * \& * * * * \& * * * * * * * * \& * * * * * * * * \& * * * * * * * * * * * * * * * * .Ve .PP The 0,1,2 and not 3 makes a little 2x2 \*(L"L\*(R" at the bottom left, then repeating at 4x4 with again the whole \*(L"3\*(R" position undrawn, and so on. This is the Sierpinski triangle (a rotated version of Math::PlanePath::SierpinskiTriangle). The blanks are also a visual representation of 1\-in\-4 cross-products saved by recursive use of the Karatsuba multiplication algorithm. .PP Plotting the fibbinary numbers (eg. Math::NumSeq::Fibbinary) which are N values with no adjacent 1 bits in binary makes an attractive tree-like pattern, .PP .Vb 10 \& * \& ** \& * \& **** \& * \& ** \& * * \& ******** \& * \& ** \& * \& **** \& * * \& ** ** \& * * * * \& **************** \& * * \& ** ** \& * * \& **** **** \& * * \& ** ** \& * * * * \& ******** ******** \& * * * * \& ** ** ** ** \& * * * * \& **** **** **** **** \& * * * * * * * * \& ** ** ** ** ** ** ** ** \& * * * * * * * * * * * * * * * * \& **************************************************************** .Ve .PP The horizontals arise from N=...0a0b0c for bits a,b,c so Y=...000 and X=...abc, making those N values adjacent. Similarly N=...a0b0c0 for a vertical. .SS "Radix" .IX Subsection "Radix" The \f(CW\*(C`radix\*(C'\fR parameter can do the same N <\-> X/Y digit splitting in a higher base. For example radix 3 makes 3x3 groupings, .PP .Vb 1 \& radix => 3 \& \& 5 | 33 34 35 42 43 44 \& 4 | 30 31 32 39 40 41 \& 3 | 27 28 29 36 37 38 45 ... \& 2 | 6 7 8 15 16 17 24 25 26 \& 1 | 3 4 5 12 13 14 21 22 23 \& Y=0 | 0 1 2 9 10 11 18 19 20 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .PP Along the X axis N=0,1,2,9,10,11,etc is integers with only digits 0,1,2 in base 9. Along the Y axis digits 0,3,6, and along the X=Y diagonal digits 0,4,8. In general for a given radix it's base R*R with the R many digits of the first RxR block. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::ZOrderCurve\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::ZOrderCurve\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::ZOrderCurve->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::ZOrderCurve\->new (radix => $r)""" 4 .el .IP "\f(CW$path = Math::PlanePath::ZOrderCurve\->new (radix => $r)\fR" 4 .IX Item "$path = Math::PlanePath::ZOrderCurve->new (radix => $r)" .PD Create and return a new path object. The optional \f(CW\*(C`radix\*(C'\fR parameter gives the base for digit splitting (the default is binary, radix 2). .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .Sp Fractional positions give an X,Y position along a straight line between the integer positions. The lines don't overlap, but the lines between bit squares soon become rather long and probably of very limited use. .ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4 .el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4 .IX Item "$n = $path->xy_to_n ($x,$y)" Return an integer point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. Each integer N is considered the centre of a unit square and an \f(CW\*(C`$x,$y\*(C'\fR within that square returns N. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest and biggest in the rectangle. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, $radix**(2*$level) \- 1)\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "N to X,Y" .IX Subsection "N to X,Y" The coordinate calculation is simple. The bits of X and Y are every second bit of N. So if N = binary 101010 then X=000 and Y=111 in binary, which is the N=42 shown above at X=0,Y=7. .PP With the \f(CW\*(C`radix\*(C'\fR parameter the digits are treated likewise, in the given radix rather than binary. .PP If N includes a fraction part then it's applied to a straight line towards point N+1. The +1 of N+1 changes X and Y according to how many low radix\-1 digits there are in N, and thus in X and Y. In general if the lowest non radix\-1 is in X then .PP .Vb 2 \& dX=1 \& dY = \- (R^pos \- 1) # pos=0 for lowest digit .Ve .PP The simplest case is when the lowest digit of N is not radix\-1, so dX=1,dY=0 across. .PP If the lowest non radix\-1 is in Y then .PP .Vb 2 \& dX = \- (R^(pos+1) \- 1) # pos=0 for lowest digit \& dY = 1 .Ve .PP If all digits of X and Y are radix\-1 then the implicit 0 above the top of X is considered the lowest non radix\-1 and so the first case applies. In the radix=2 above this happens for instance at N=15 binary 1111 so X = binary 11 and Y = binary 11. The 0 above the top of X is at pos=2 so dX=1, dY=\-(2^2\-1)=\-3. .SS "Rectangle to N Range" .IX Subsection "Rectangle to N Range" Within each row the N values increase as X increases, and within each column N increases with increasing Y (for all \f(CW\*(C`radix\*(C'\fR parameters). .PP So for a given rectangle the smallest N is at the lower left corner (smallest X and smallest Y), and the biggest N is at the upper right (biggest X and biggest Y). .SH "OEIS" .IX Header "OEIS" This path is in Sloane's Online Encyclopedia of Integer Sequences in various forms, .Sp .RS 4 (etc) .RE .PP .Vb 3 \& radix=2 \& A059905 X coordinate \& A059906 Y coordinate \& \& A000695 N on X axis (base 4 digits 0,1 only) \& A062880 N on Y axis (base 4 digits 0,2 only) \& A001196 N on X=Y diagonal (base 4 digits 0,3 only) \& \& A057300 permutation N at transpose Y,X (swap bit pairs) \& \& radix=3 \& A163325 X coordinate \& A163326 Y coordinate \& A037314 N on X axis, base 9 digits 0,1,2 \& A208665 N on Y axis, base 9 digits 0,3,6 \& A338086 N on X=Y diagonal, base 9 digits 0,4,8 \& A163327 permutation N at transpose Y,X (swap trit pairs) \& \& radix=4 \& A126006 permutation N at transpose Y,X (swap digit pairs) \& \& radix=10 \& A080463 X+Y of radix=10 (from N=1 onwards) \& A080464 X*Y of radix=10 (from N=10 onwards) \& A080465 abs(X\-Y), from N=10 onwards \& A051022 N on X axis (base 100 digits 0 to 9) \& A338754 N on X=Y diagonal (double\-digits 00 to 99) \& \& radix=16 \& A217558 permutation N at transpose Y,X (swap digit pairs) .Ve .PP And taking X,Y points in the Diagonals sequence then the value of the following sequences is the N of the \f(CW\*(C`ZOrderCurve\*(C'\fR at those positions. .PP .Vb 3 \& radix=2 \& A054238 numbering by diagonals, from same axis as first step \& A054239 inverse permutation \& \& radix=3 \& A163328 numbering by diagonals, same axis as first step \& A163329 inverse permutation \& A163330 numbering by diagonals, opp axis as first step \& A163331 inverse permutation .Ve .PP \&\f(CW\*(C`Math::PlanePath::Diagonals\*(C'\fR numbers points from the Y axis down, which is the opposite axis to the \f(CW\*(C`ZOrderCurve\*(C'\fR first step along the X axis, so a transpose is needed to give A054238. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::ImaginaryBase, Math::PlanePath::CornerReplicate, Math::PlanePath::DigitGroups .PP \&\f(CW\*(C`http://www.jjj.de/fxt/#fxtbook\*(C'\fR (section 1.31.2) .IX Xref "Arndt, Jorg fxtbook" .PP Algorithm::QuadTree, DBIx::SpatialKey .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .