--- name: "Math::PlanePath::HilbertSides" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::HilbertSides" --- # Math::PlanePath::HilbertSides(3pm) ## NAME Math::PlanePath::HilbertSides -- sides of Hilbert curve squares ## SYNOPSIS ``` use Math::PlanePath::HilbertSides; my $path = Math::PlanePath::HilbertSides->new; my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This path is segments along the sides of the Hilbert curve squares as per F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages 79-104, section 4.8 "Hilbert Curve" The base pattern is N=0 to N=4. That pattern repeats transposed as points N=0,4,8,12,16, etc. ``` 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 ``` If each point of the `"HilbertCurve"` 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, ``` -------3. . v | |> | 2 . | |> ^ | 0-------1 . ``` 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. 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. 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. ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes. - "$path = Math::PlanePath::HilbertSides-\>new ()" Create and return a new path object. - "($x,$y) = $path-\>n\_to\_xy ($n)" Return the X,Y coordinates of point number `$n` on the path. Points begin at 0 and if `"$n < 0"` then the return is an empty list. - "$n = $path-\>xy\_to\_n ($x,$y)" Return the point number for coordinates `"$x,$y"`. If there's nothing at `"$x,$y"` then return `"undef"`. The curve visits an `"$x,$y"` twice for various points. The smaller of the two N values is returned. - "@n\_list = $path-\>xy\_to\_n\_list ($x,$y)" Return a list of N point numbers for coordinates `"$x,$y"`. Points may have up to two Ns for a given `"$x,$y"`. ## FORMULAS ### Coordinates Difference X-Y is the same here as in the `"HilbertCurve"`. 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. ``` 3 | HilbertSides 2 3----2 HilbertCurve | | 0----1 0----1 ``` ### Abs dX,dY abs(dY) is 1 for a vertical segment and 0 for a horizontal segment. For the curve here it is ``` abs(dY) = count 1-bits of N, mod 2 = Thue-Morse binary parity abs(dX) = 1 - abs(dY) = opposite ``` 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. ### Turn The path can turn left or right or go straight forward or 180 degree reverse. Straight,reverse vs left,right is given by ``` N num trailing 0 bits turn --------------------- ----------------------- odd straight or 180 reverse (A096268) even left or right (A035263) ``` The path goes straight ahead at 2 and reverses 180 at 8 and all subsequent 2\*4^k. ### 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 ``` 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 ``` These counts can be calculated from the curve sub-parts ``` k odd k even +---+ . . . . R |>T T T . . . +---+---+ |>T |> R<| o---+ . o . + ``` 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. ``` Xsegs[k] = Xsegs[k-1] + Ysegs[k-1] for k odd Ysegs[k] = 2*Ysegs[k-1] ``` Then similarly for k even, but the other way around the 2\*Y. ``` Xsegs[k] = 2*Xsegs[k-1] for k even Ysegs[k] = Xsegs[k-1] + Ysegs[k-1] ``` ## OEIS Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include \ (etc) ``` 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 ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoDiagonals ## HOME PAGE \ ## LICENSE Copyright 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde This file is part of Math-PlanePath. Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see \.