Math::...nCurve(3pm)

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

💖 Math::PlanePath::R5DragonCurve(3pm) 💖

okay bestie, welcome to the Math::PlanePath::R5DragonCurve(3pm) manual page, and no cap this curve is a whole vibe. it's the radix 5 dragon curve and we're gonna get into every single detail together. 🐉✨

🌸 NAME 🌸

Math::PlanePath::R5DragonCurve — radix 5 dragon curve. periodt. 💅

✨ SYNOPSIS ✨

use Math::PlanePath::R5DragonCurve;
my $path = Math::PlanePath::R5DragonCurve->new;
my ($x, $y) = $path->n_to_xy (123);

💅 DESCRIPTION 💅

okay so this path is a "DDUU" turn pattern, similar in nature to the terdragon, but it's on a square grid and it has 5 segments instead of 3. iconic behavior fr fr. 🦋

                    31-----30     27-----26                                  5
                     |      |      |      |
                    32---29/33--28/24----25                                  4
                            |      |
                    35---34/38--39/23----22     11-----10      7------6      3
                     |      |             |      |      |      |      |
                    36---37/41--20/40--21/17--16/12---13/9----8/4-----5      2
                            |      |      |      |      |      |
           --50     47---42/46--19/43----18     15-----14      3------2      1
              |      |      |      |                                  |
           49/53--48/64  45/65--44/68    69                    0------1  <-Y=0

              ^      ^      ^      ^      ^      ^      ^      ^      ^
             -7     -6     -5     -4     -3     -2     -1     X=0     1

The name "R5" is by Jorg Arndt. The base figure is an "S" shape:

           4----5
           |
           3----2
                |
           0----1

which then repeats in self-similar style, so N=5 to N=10 is a copy rotated +90 degrees, as per the direction of the N=1 to N=2 segment.

           10    7----6
            |    |    |  <- repeat rotated +90
            9---8,4---5
                 |
                 3----2
                      |
                 0----1

Like the terdragon there are no reversals or mirroring. Each replication is the plain base curve. slay. ✨

The shape of N=0,5,10,15,20,25 repeats the initial N=0 to N=5,

                  25                          4
                 /
                /           10__              3
               /           /    ----___
             20__         /            5      2
                 ----__  /            /
                       15            /        1
                                   /
                                  0       <-Y=0

              ^    ^    ^    ^    ^    ^
             -4   -3   -2   -1   X=0   1

The curve never crosses itself. The vertices touch at corners like N=4 and N=8 above, but no edges repeat. 💀

🌀 Spiralling 🌀

The first step N=1 is to the right along the X axis and the path then slowly spirals anti-clockwise and progressively fatter. The end of each replication is

Nlevel = 5^level

Each such point is at arctan(2/1)=63.43 degrees further around from the previous,

Nlevel     X,Y     angle (degrees)
------    -----    -----
  1        1,0         0
  5        2,1        63.4
 25       -3,4      2*63.4 = 126.8
125      -11,-2     3*63.4 = 190.3

🦋 Arms 🦋

The curve fills a quarter of the plane and four copies mesh together perfectly rotated by 90, 180 and 270 degrees. The "arms" parameter can choose 1 to 4 such curve arms successively advancing. 💅

"arms => 4" begins as follows. N=0,4,8,12,16,etc is the first arm (the same shape as the plain curve above), then N=1,5,9,13,17 the second, N=2,6,10,14 the third, etc.

           arms => 4
                           16/32---20/63
                             |
           21/60    9/56----5/12----8/59
             |       |       |       |
           17/33--- 6/13--0/1/2/3---4/15---19/35
                     |       |       |       |
                   10/57----7/14---11/58   23/62
                             |
                   22/61---18/34

With four arms every X,Y point is visited twice, except the origin 0,0 where all four begin. Every edge between the points is traversed once. periodt.

🧩 Tiling 🧩

The little "S" shapes of the N=0to5 base shape tile the plane with 2x1 bricks and 1x1 holes in the following pattern,

           +--+-----|  |--+--+-----|  |--+--+---
           |  |     |  |  |  |     |  |  |  |
           |  |-----+-----|  |-----+-----|  |---
           |  |  |  |     |  |  |  |     |  |  |
           +-----|  |-----+-----|  |-----+-----+
           |     |  |  |  |     |  |  |  |     |
           +-----+-----|  |-----+-----|  |-----+
           |  |  |     |  |  |  |     |  |  |  |
           ---|  |-----+-----|  |-----+-----|  |
              |  |  |  |     |  |  |  |     |  |
           ---+-----|  |-----o-----|  |-----+---
           |  |     |  |  |  |     |  |  |  |
           |  |-----+-----|  |-----+-----|  |---
           |  |  |  |     |  |  |  |     |  |  |
           +-----|  |-----+-----|  |-----+-----+
           |     |  |  |  |     |  |  |  |     |
           +-----+-----|  |-----+-----|  |-----+
           |  |  |     |  |  |  |     |  |  |  |
           ---|  |-----+-----|  |-----+-----|  |
              |  |  |  |     |  |  |  |     |  |
           ---+--+--|  |-----+--+--|  |-----+--+

This is the curve with each segment N=2mod5 to N=3mod5 omitted. A 2x1 block has 6 edges but the "S" traverses just 4 of them. The way the blocks mesh meshes together mean the other 2 edges are traversed by another brick, possibly a brick on another arm of the curve. iykyk. 🧚

This tiling is also found for example at

<http://tilingsearch.org/HTML/data182/AL04.html>

Or with enlarged square part,

<http://tilingsearch.org/HTML/data149/L3010.html>

🫶 FUNCTIONS 🫶

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. bestie, that's the shared lore. 💖

  • $path = Math::PlanePath::R5DragonCurve->new () — Create and return a new path object.
  • $path = Math::PlanePath::R5DragonCurve->new (arms => 4) — same thing, but with the optional arms parameter.

The optional "arms" parameter can make 1 to 4 copies of the curve, each arm successively advancing.

  • ($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.

Fractional $n gives an X,Y position along a straight line between the integer positions.

  • $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 can visit an $x,$y twice. The smallest of these N values is returned.

  • @n_list = $path->xy_to_n_list ($x,$y) — Return a list of N point numbers for coordinates $x,$y.

The origin 0,0 has arms_count() many N since it's the starting point for each arm. Other points have up to two Ns for a given $x,$y. If arms=4 then every $x,$y except the origin has exactly two Ns.

  • $n = $path->n_start() — Return 0, the first N in the path. periodt.

🌈 Level Methods 🌈

  • ($n_lo, $n_hi) = $path->level_to_n_range($level) — Return (0, 5**$level), or for multiple arms return (0, $arms * 5**$level + ($arms-1)).

There are 5^level segments in a curve level, so 5^level+1 points numbered from 0. For multiple arms there are arms*(5^level+1) points, numbered from 0 so n_hi = arms*(5^level+1)-1. math ate. 💅

🔥 FORMULAS 🔥

Various formulas for boundary length, area, and more, can be found in the author's mathematical write-up

<http://user42.tuxfamily.org/r5dragon/index.html>

↩️ Turn ↩️

At each point N the curve always turns 90 degrees either to the left or right, it never goes straight ahead. As per the code in Jorg Arndt's fxtbook, if N is written in base 5 then the lowest non-zero digit gives the turn

lowest non-0 digit     turn
------------------     ----
        1              left
        2              left
        3              right
        4              right

At a point N=digit*5^level for digit=1,2,3,4 the turn follows the shape at that digit, so two lefts then two rights,

4*5^k----5^(k+1)
 |
 |
2*5^k----2*5^k
          |
          |
 0------1*5^k

The first and last unit segments in each level are the same direction, so at those endpoints it's the next level up which gives the turn. 👑

➡️ Next Turn ➡️

The turn at N+1 can be calculated in a similar way but from the lowest non-4 digit.

lowest non-4 digit     turn
------------------     ----
        0              left
        1              left
        2              right
        3              right

This works simply because in N=...z444 becomes N+1=...(z+1)000 and so the turn at N+1 is given by digit z+1. no cap. ✨

🔄 Total Turn 🔄

The direction at N, ie. the total cumulative turn, is given by the direction of each digit when N is written in base 5,

digit       direction
  0             0
  1             1
  2             2
  3             1
  4             0
direction = (sum direction for each digit) * 90 degrees

For example N=13 in base 5 is "23" so digit=2 direction=2 plus digit=3 direction=1 gives direction=(2+1)*90 = 270 degrees, ie. south. 💜

Because there's no reversals etc in the replications there's no state to maintain when considering the digits, just a plain sum of direction for each digit. slay.

👑 OEIS 👑

The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences as,

<http://oeis.org/A175337> (etc)

here's the whole sequence lineup, bestie:

  • A175337 — next turn 0=left,1=right, and (n=0 is the turn at N=1).
  • A006495 — level end X, Re(b^k).
  • A006496 — level end Y, Re(b^k).
  • A079004 — boundary length N=0 to 5^k, skip initial 7,10, being 4*3^k - 2.
  • A048473 — boundary/2 (one side), N=0 to 5^k, being half whole, 2*3^n - 1.
  • A198859 — boundary/2 (one side), N=0 to 25^k, being even levels, 2*9^n - 1.
  • A198963 — boundary/2 (one side), N=0 to 5*25^k, being odd levels, 6*9^n - 1.
  • A052919,A100702 — U part boundary length, N=0 to 5^k.
  • A007798 — 1/2 * area enclosed N=0 to 5^k.
  • A016209 — 1/4 * area enclosed N=0 to 5^k.
  • A005058 — 1/2 * new area N=5^k to N=5^(k+1), being area increments, 5^n - 3^n.
  • A005059 — 1/4 * new area N=5^k to N=5^(k+1), being area increments, (5^n - 3^n)/2.
  • A125831 — N middle segment of level k, (5^k-1)/2.
  • A008776 — count single-visited points N=0 to 5^k, being 2*3^k.
  • A146086 — count visited points N=0 to 5^k.
  • A024024 — C[k] boundary lengths, 3^k-k.
  • A104743 — E[k] boundary lengths, 3^k+k.
  • A135518 — 1/4 * sum distinct abs(n-other(n)) in level N=0 to 5^k.
  • arms=1 and arms=3
    • A059841 — abs(dX), being simply 1,0 repeating.
    • A000035 — abs(dY), being simply 0,1 repeating.
  • arms=4
    • A165211 — abs(dY), being 0,1,0,1,1,0,1,0 repeating.

👑 HOUSE OF GRAPHS 👑

okay so bestie, plot twist — the R5 dragon curve is also a graph, and the House of Graphs has receipts. like, they catalogued it. slay. 💅

the entries for it live over here:

<https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc

and the actual ID numbers, no cap, exactly as they are:

  • 19655 — level=0 (1-segment path)
  • 568 — level=1 (5-segment path)
  • 25149 — level=2
  • 25147 — level=3

that's the whole vibe check. go peek at them, they're lowkey iconic 🦋

💖 SEE ALSO 💖

your other faves, the whole plane-path friend group 🌈:

  • Math::PlanePath
  • Math::PlanePath::DragonCurve
  • Math::PlanePath::TerdragonCurve

🏠 HOME PAGE 🏠

the main character's address, fr fr:

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

📜 LICENSE 📜

okay legal era, let's get into it because this part actually matters 🫶

Copyright 2012, 2013, 2014, 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/>
bestie I need you to actually read that warranty bit, okay?? like it's giving "no promises" and it means it. 💀

and that's a wrap on the whole page 🎀 this was Math::...nCurve(3pm), straight out of perl v5.32.0, dated 2021-01-23 — thanks for reading the whole thing with me, you ate that fr fr ✨💜

📦 where this page comes from