.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" 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 turned on, 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 .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::ZOrderCurve 3pm" .TH Math::PlanePath::ZOrderCurve 3pm "2014-09-03" "perl v5.20.1" "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 X=Y diagonal, base 9 digits 0,3,6 \& 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) \& \& 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::SpatialKeys .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2010, 2011, 2012, 2013, 2014 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 .