.\" 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::AR2W2Curve 3pm" .TH Math::PlanePath::AR2W2Curve 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::AR2W2Curve \-\- 2x2 self\-similar curve of four patterns .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::AR2W2Curve; \& my $path = Math::PlanePath::AR2W2Curve\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is an integer version of the \&\s-1AR2W2\s0 curve per .IX Xref "Asano Ranjan Roos Welzl Widmayer" .Sp .RS 4 Asano, Ranjan, Roos, Welzl and Widmayer \*(L"Space-Filling Curves and Their Use in the Design of Geometric Data Structures\*(R", Theoretical Computer Science, volume 181, issue 1, pages 3\-15, July 1997. .Sp And in \s-1LATIN\s0'95 Theoretical Informatics which is at Google Books .RE .PP It traverses the first quadrant in self-similar 2x2 blocks which are a mixture of \*(L"U\*(R" and \*(L"Z\*(R" shapes. The mixture is designed to improve some locality measures (how big the N range for a given region). .PP .Vb 10 \& | \& 7 42\-\-43\-\-44 47\-\-48\-\-49 62\-\-63 \& \e | | | | \& 6 40\-\-41 45\-\-46 51\-\-50 61\-\-60 \& | | | \& 5 39 36\-\-35\-\-34 52 55\-\-56 59 \& | | / | | | | \& 4 38\-\-37 33\-\-32 53\-\-54 57\-\-58 \& \e \& 3 6\-\- 7\-\- 8 10 31 28\-\-27\-\-26 \& | |/ | | | | \& 2 5\-\- 4 9 11 30\-\-29 24\-\-25 \& | | | \& 1 2\-\- 3 13\-\-12 17\-\-18 23\-\-22 \& \e | | | | \& Y=0 \-> 0\-\- 1 14\-\-15\-\-16 19\-\-20\-\-21 \& \& X=0 1 2 3 4 5 6 7 .Ve .SS "Shape Parts" .IX Subsection "Shape Parts" There's four base patterns A to D. A2 is a mirror image of A1, B2 a mirror of B1, etc. The start is A1, and above that D2, then A1 again, alternately. .PP .Vb 6 \& ^\-\-\-\-> ^ \& 2\-\-\-3 C1 | B2 1 3 C2 D1 | \& A1 \e | A2 | \e | \-\-\-\-> | \& 0\-\-\-1 ^ 0 2 ^ \-\-\-\-> \& D2 | B1 |B1 B2 \& \-\-\-\->| | \& \& \& 1\-\-\-2 C2 B1 1\-\-\-2 B2 C1 \& B1 | | \-\-\-\->\-\-\-\-> B2 | | \-\-\-\->\-\-\-\-> \& 0 3 ^ | 0 3 ^ | \& |D1 B2| |B1 D2| \& | v | v \& \& ^ \e ^ | \& 1\-\-\-2 B1| \eA1 1\-\-\-2 A2/ | B2 \& C1 | | | v C2 | | / v \& 0 3 ^ | 0 3 ^ \e \& /A2 B2| |B1 \eA1 \& / v | v \& \& ^ | ^ \e \& 1\-\-\-2 A2/ | C2 1\-\-\-2 C1| \eA1 \& D1 | | / v D2 | | | v \& 0 3 ^ \e 0 3 ^ | \& |D1 \eA2 /A1 D2| \& | v / v .Ve .PP For parts which fill on the right such as the B1 and B2 sub-parts of A1, the numbering must be reversed. This doesn't affect the shape of the curve as such, but it matters for enumerating it as done here. .SS "Start Shape" .IX Subsection "Start Shape" The default starting shape is the A1 \*(L"Z\*(R" part, and above it D2. Notice the starting sub-part of D2 is A1 and in turn the starting sub-part of A1 is D2, so those two alternate at successive higher levels. Their sub-parts reach all other parts (in all directions, and forward or reverse). .PP The \f(CW\*(C`start_shape => $str\*(C'\fR option can select a different starting shape. The choices are .PP .Vb 6 \& "A1" \e pair \& "D2" / \& "B2" \e pair \& "B1rev" / \& "D1rev" \e pair \& "A2rev" / .Ve .PP B2 begins with a reversed B1 and in turn a B1 reverse begins with B2 (no reverse), so those two alternate. Similarly D1 reverse starts with A2 reverse, and A2 reverse starts with D1 reverse. .PP The curve is conceived by the authors as descending into ever-smaller sub-parts and for that any of the patterns can be a top-level start. But to expand outwards as done here the starting part must be the start of the pattern above it, and that's so only for the 6 listed. The descent graph is .PP .Vb 2 \& D2rev \-\-\-\-\-> D2 <\-\-> A1 \& B2rev \-\-\-\-\-> \& \& C2rev \-\-> A1rev \-\-\-\-\-> B2 <\-\-> B1rev <\-\-\-\-\- C2 \& C1rev \-\-\-\-\-> <\-\-\-\-\- A2 <\-\- C1 \& \& B1 \-\-\-\-\-> D1rev <\-\-> A2rev \& D1 \-\-\-\-\-> .Ve .PP So for example B1 is not at the start of anything. Or A1rev is at the start of C2rev, but then nothing starts with C2rev. Of the 16 total only the three pairs shown \*(L"<\-\->\*(R" are cycles and can thus extend upwards indefinitely. .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::AR2W2Curve\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::AR2W2Curve\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::AR2W2Curve->new ()" Create and return a new path object. .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. .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 largest 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, 4**$level \- 1)\*(C'\fR. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoCurve .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 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 .