Math::...rtSides(3pm)

📦
version 129 · 3 versions
, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble, ubuntu resolute, ubuntu stonking

💖 Math::PlanePath::HilbertSides 💖

okay bestie, so this is a page from the User Contributed Perl Documentation (that's the manual name, section 3pm if you're keeping track), and it's all about Math::PlanePath::HilbertSides — the sides of Hilbert curve squares. yes you read that right. squares. sides. iconic behavior. let's get into it 🦋

✨ 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);

that's it that's the whole vibe. copy paste and slay 💅

💜 DESCRIPTION 💜

so this path is segments along the sides of the Hilbert curve squares, straight up per:

F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages 79-104, section 4.8 "Hilbert Curve"

(the academic citation ate, ngl)

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, like so:

    -------3.       .
       v   |
           |>
           |
           2        .
           |
           |>
       ^   |
   0-------1        .

🙈 some points get visited TWICE

The first one 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 — for example N=27to28 and N=36to37. Double-visited points also happen as corners touching, for example at X=4,Y=3 the two N=11 N=31 touch without overlapping segments.

🌈 blocks & columns

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. your lil baby path, born fresh 💖
  • ($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. (no negativity allowed bestie)
  • $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

    <http://oeis.org/A059285> (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 🌈

<http://user42.tuxfamily.org/math-planepath/index.html>

💅 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 <http://www.gnu.org/licenses/>.

okay that's the whole page bestie, and just so you know who to thank: this was perl v5.32.0, dated 2021-01-23, filed under Math::...rtSides(3pm). stay mathematical, drink water, and go touch some 2^k x 2^k grass 🫶💖✨

📦 where this page comes from