.\" 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::HilbertSpiral 3pm" .TH Math::PlanePath::HilbertSpiral 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::HilbertSpiral \-\- 2x2 self\-similar spiral .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::HilbertSpiral; \& my $path = Math::PlanePath::HilbertSpiral\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is a Hilbert curve variation which fills the plane by spiralling around into negative X,Y on every second replication level. .PP .Vb 10 \& ..\-\-63\-\-62 49\-\-48\-\-47 44\-\-43\-\-42 5 \& | | | | | \& 60\-\-61 50\-\-51 46\-\-45 40\-\-41 4 \& | | | \& 59 56\-\-55 52 33\-\-34 39\-\-38 3 \& | | | | | | | \& 58\-\-57 54\-\-53 32 35\-\-36\-\-37 2 \& | \& 5\-\- 4\-\- 3\-\- 2 31 28\-\-27\-\-26 1 \& | | | | | \& 6\-\- 7 0\-\- 1 30\-\-29 24\-\-25 <\- Y=0 \& | | \& 9\-\- 8 13\-\-14 17\-\-18 23\-\-22 \-1 \& | | | | | | \& 10\-\-11\-\-12 15\-\-16 19\-\-20\-\-21 \-2 \& \& \-2 \-1 X=0 1 2 3 4 5 .Ve .PP The curve starts with the same N=0 to N=3 as the \f(CW\*(C`HilbertCurve\*(C'\fR, then the following 2x2 blocks N=4 to N=15 go around in negative X,Y. The top-left corner for this negative direction is at Ntopleft=4^level\-1 for an odd numbered level. .PP The parts of the curve in the X,Y negative parts are the same as the plain \&\f(CW\*(C`HilbertCurve\*(C'\fR, just mirrored along the anti-diagonal. For example. N=4 to N=15 .PP .Vb 1 \& HilbertSpiral HilbertCurve \& \& \e 5\-\-\-6 9\-\-10 \& \e | | | | \& \e 4 7\-\-\-8 11 \& \e | \& 5\-\- 4 \e 13\-\-12 \& | \e | \& 6\-\- 7 \e 14\-\-15 \& | \e \& 9\-\- 8 13\-\-14 \e \& | | | \e \& 10\-\-11\-\-12 15 .Ve .PP This mirroring has the effect of mapping .PP .Vb 1 \& HilbertCurve X,Y \-> \-Y,\-X for HilbertSpiral .Ve .PP Notice the coordinate difference (\-Y)\-(\-X) = X\-Y so that difference, representing a projection onto the X=\-Y opposite diagonal, is the same in both paths. .SS "Level Ranges" .IX Subsection "Level Ranges" Reckoning the initial N=0 to N=3 as level 1, a replication level extends to .PP .Vb 2 \& Nstart = 0 \& Nlevel = 4^level \- 1 (inclusive) \& \& Xmin = Ymin = \- (4^floor(level/2) \- 1) * 2 / 3 \& = binary 1010...10 \& Xmax = Ymax = (4^ceil(level/2) \- 1) / 3 \& = binary 10101...01 \& \& width = height = Xmax \- Xmin \& = Ymax \- Ymin \& = 2^level \- 1 .Ve .PP The X,Y range doubles alternately above and below, so the result is a 1 bit going alternately to the max or min, starting with the max for level 1. .PP .Vb 10 \& level X,Ymin binary X,Ymax binary \& \-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\- \& 0 0 0 \& 1 0 0 1 = 1 \& 2 \-2 = \-10 1 = 01 \& 3 \-2 = \-010 5 = 101 \& 4 \-10 = \-1010 5 = 0101 \& 5 \-10 = \-01010 21 = 10101 \& 6 \-42 = \-101010 21 = 010101 \& 7 \-42 = \-0101010 85 = 1010101 .Ve .PP The power\-of\-4 formulas above for Ymin/Ymax have the effect of producing alternating bit patterns like this. .PP This is the same sort of level range as \f(CW\*(C`BetaOmega\*(C'\fR has on its Y coordinate, but on this \f(CW\*(C`HilbertSpiral\*(C'\fR it applies to both X and Y. .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::HilbertSpiral\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::HilbertSpiral\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::HilbertSpiral->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 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, 4**$level \- 1)\*(C'\fR. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include .Sp .RS 4 (etc) .RE .PP .Vb 1 \& A059285 X\-Y coordinate diff .Ve .PP The difference X\-Y is the same as the \f(CW\*(C`HilbertCurve\*(C'\fR, since the \*(L"negative\*(R" spiral parts are mirrored across the X=\-Y anti-diagonal, which means coordinates (\-Y,\-X) and \-Y\-(\-X) = X\-Y. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::BetaOmega .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 .