.\" 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::HilbertSides 3pm" .TH Math::PlanePath::HilbertSides 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::HilbertSides \-\- sides of Hilbert curve squares .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::HilbertSides; \& my $path = Math::PlanePath::HilbertSides\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path is segments along the sides of the Hilbert curve squares as per .Sp .RS 4 F. M. Dekking, \*(L"Recurrent Sets\*(R", Advances in Mathematics, volume 44, 1982, pages 79\-104, section 4.8 \*(L"Hilbert Curve\*(R" .RE .PP The base pattern is N=0 to N=4. That pattern repeats transposed as points N=0,4,8,12,16, etc. .PP .Vb 10 \& 9 | ... \& | | \& 8 | 64\-\-\-\-63 49\-\-\-\-48 44\-\-\-\-43 \& | | | | | | \& 7 | 62 50 47\-\-\-\-46\-\-\-\-45 42 \& | | | | \& 6 | 60\-\-\-\-61 56 51\-\-\-\-52 40\-\-\-39,41 \& | | | | | \& 5 | 59\-\-\-\-58\-\-\-57,55\-\-54\-\-\-53,33\-\-34\-\-\-\-35 38 \& | | | | \& 4 | 32 36,28\-\-37,27 \& | | | | \& 3 | 5\-\-\-\-\-6\-\-\-\-7,9\-\-\-10\-\-\-11,31\-\-30\-\-\-\-29 26 \& | | | | | \& 2 | 4\-\-\-\-\-3 8 13\-\-\-\-12 24\-\-\-23,25 \& | | | | \& 1 | 2 14 17\-\-\-\-18\-\-\-\-19 22 \& | | | | | | \& Y=0 | 0\-\-\-\-\-1 15\-\-\-\-16 20\-\-\-\-21 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP If each point of the \f(CW\*(C`HilbertCurve\*(C'\fR path is taken to be a unit square the effect here is to go along the sides of those squares. The square for a segment is on the left or right, .PP .Vb 9 \& \-\-\-\-\-\-\-3. . \& v | \& |> \& | \& 2 . \& | \& |> \& ^ | \& 0\-\-\-\-\-\-\-1 . .Ve .PP Some points are visited twice. The first is at X=2,Y=3 which is N=7 and N=9 where the two segments N=7to8 and N=8to9 overlap. These are consecutive segments, and non-consecutive segments can overlap too, as for example N=27to28 and N=36to37. Double-visited points occur also as corners touching, for example at X=4,Y=3 the two N=11 N=31 touch without overlapping segments. .PP The HilbertCurve squares fall within 2^k x 2^k blocks and so likewise the segments here. The right side 1 to 2 and 2 to 3 don't touch the 2^k side. This is so of the base figure N=0 to N=4 which doesn't touch X=2 and higher levels are unrotated replications so for example in the N=0 to N=64 shown above X=8 is not touched. This creates rectangular columns up from the X axis. Likewise rectangular rows across from the Y axis, and both columns and rows inside. .PP The sides which are N=0 to N=1 and N=3 to N=4 of the base pattern variously touch in higher levels giving interesting patterns of squares, shapes, notches, etc. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for the behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::HilbertSides\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::HilbertSides\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::HilbertSides->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 = $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 the point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. If there's nothing at \&\f(CW\*(C`$x,$y\*(C'\fR then return \f(CW\*(C`undef\*(C'\fR. .Sp The curve visits an \f(CW\*(C`$x,$y\*(C'\fR twice for various points. The smaller of the two N values is returned. .ie n .IP """@n_list = $path\->xy_to_n_list ($x,$y)""" 4 .el .IP "\f(CW@n_list = $path\->xy_to_n_list ($x,$y)\fR" 4 .IX Item "@n_list = $path->xy_to_n_list ($x,$y)" Return a list of N point numbers for coordinates \f(CW\*(C`$x,$y\*(C'\fR. Points may have up to two Ns for a given \f(CW\*(C`$x,$y\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "Coordinates" .IX Subsection "Coordinates" Difference X\-Y is the same here as in the \f(CW\*(C`HilbertCurve\*(C'\fR. The base pattern here has N=3 at 1,2 whereas the HilbertCurve is 0,1 so X\-Y is the same. The two then have the same pattern of rotate 180 and/or transpose in subsequent replications. .PP .Vb 5 \& 3 \& | \& HilbertSides 2 3\-\-\-\-2 HilbertCurve \& | | \& 0\-\-\-\-1 0\-\-\-\-1 .Ve .SS "Abs dX,dY" .IX Subsection "Abs dX,dY" abs(dY) is 1 for a vertical segment and 0 for a horizontal segment. For the curve here it is .PP .Vb 2 \& abs(dY) = count 1\-bits of N, mod 2 = Thue\-Morse binary parity \& abs(dX) = 1 \- abs(dY) = opposite .Ve .PP This is so for the base pattern N=0,1,2, and also at N=3 turning towards N=4. Replication parts 1 and 2 are transposes where there is a single extra 1\-bit in N and dX,dY are swapped. Replication part 3 is a 180 degree rotation where there are two extra 1\-bits in N and dX,dY are negated so abs(dX),abs(dY) unchanged. .SS "Turn" .IX Subsection "Turn" The path can turn left or right or go straight forward or 180 degree reverse. Straight,reverse vs left,right is given by .PP .Vb 4 \& N num trailing 0 bits turn \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& odd straight or 180 reverse (A096268) \& even left or right (A035263) .Ve .PP The path goes straight ahead at 2 and reverses 180 at 8 and all subsequent 2*4^k. .SS "Segments on Axes" .IX Subsection "Segments on Axes" The number of line segments on the X and Y axes 0 to 2^k, which is N=0 to 4^k, is .PP .Vb 3 \& Xsegs[k] = 1/3*2^k + 1/2 + 1/6*(\-1)^k \& = 1, 1, 2, 3, 6, 11, 22, 43, 86 (A005578) \& = Ysegs[k] + 1 \& \& Ysegs[k] = 1/3*2^k \- 1/2 + 1/6*(\-1)^k \& = 0, 0, 1, 2, 5, 10, 21, 42, 85,... (A000975) \& = binary 101010... k\-1 many bits alternating .Ve .PP These counts can be calculated from the curve sub-parts .PP .Vb 1 \& k odd k even \& \& +\-\-\-+ . . . . \& R |>T T T \& . . . +\-\-\-+\-\-\-+ \& |>T |> R<| \& o\-\-\-+ . o . + .Ve .PP The block at the origin is X and Y segments of the k\-1 level. For k odd, the X axis then has a transposed block which means the Y segments of k\-1. The Y axis has a 180 degree rotated block R. The curve is symmetric in mirror image across its start to end so the count of segments it puts on the Y axis is the same as Y of level k\-1. .PP .Vb 2 \& Xsegs[k] = Xsegs[k\-1] + Ysegs[k\-1] for k odd \& Ysegs[k] = 2*Ysegs[k\-1] .Ve .PP Then similarly for k even, but the other way around the 2*Y. .PP .Vb 2 \& Xsegs[k] = 2*Xsegs[k\-1] for k even \& Ysegs[k] = Xsegs[k\-1] + Ysegs[k\-1] .Ve .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 3 \& A059285 X\-Y \& A010059 abs(dX), 1 \- Thue\-Morse binary parity \& A010060 abs(dY), Thue\-Morse binary parity \& \& A096268 turn 1=straight or reverse, 0=left or right \& A035263 turn 0=straight or reverse, 1=left or right \& \& A062880 N values on diagonal X=Y (digits 0,2 in base 4) \& \& A005578 count segments on X axis, level k \& A000975 count segments on Y axis, level k .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoDiagonals .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 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 .