--- name: "Math::PlanePath::R5DragonCurve" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::R5DragonCurve" --- # Math::PlanePath::R5DragonCurve(3pm) ## NAME Math::PlanePath::R5DragonCurve -- radix 5 dragon curve ## SYNOPSIS ``` use Math::PlanePath::R5DragonCurve; my $path = Math::PlanePath::R5DragonCurve->new; my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This path is a "DDUU" turn pattern similar in nature to the terdragon but on a square grid and with 5 segments instead of 3. ``` 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. 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. ### 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. This tiling is also found for example at \ Or with enlarged square part, \ ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. - "$path = Math::PlanePath::R5DragonCurve-\>new ()" - "$path = Math::PlanePath::R5DragonCurve-\>new (arms =\> 4)" Create and return a new path object. 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 the 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. ### 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. ## FORMULAS Various formulas for boundary length, area, and more, can be found in the author's mathematical write-up \ ### 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. ### 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. ## OEIS The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences as, \ (etc) ``` A175337 next turn 0=left,1=right (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 House of Graphs entries for the R5 dragon curve as a graph include \ etc ``` 19655 level=0 (1-segment path) 568 level=1 (5-segment path) 25149 level=2 25147 level=3 ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::TerdragonCurve ## HOME PAGE \ ## LICENSE 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 \.