--- name: "Math::PlanePath::AlternateTerdragon" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::AlternateTerdragon" --- # Math::PlanePath::AlternateTerdragon(3pm) ## NAME Math::PlanePath::AlternateTerdragon -- alternate terdragon curve ## SYNOPSIS ``` use Math::PlanePath::AlternateTerdragon; my $path = Math::PlanePath::AlternateTerdragon->new; my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This is the alternate terdragon curve by Davis and Knuth, Chandler Davis and Donald Knuth, "Number Representations and Dragon Curves -- I", Journal Recreational Mathematics, volume 3, number 2 (April 1970), pages 66-81 and "Number Representations and Dragon Curves -- II", volume 3, number 3 (July 1970), pages 133-149. Reprinted with addendum in Knuth "Selected Papers on Fun and Games", 2010, pages 571--614. \ Points are a triangular grid using every second integer X,Y as per "Triangular Lattice" in Math::PlanePath, beginning ``` \ / \ / Y=2 14,17 --- 15,24,33 -- \ / \ \ / \ / Y=1 2 ------- 3,12 ---- 10,13,34 -- 32,35,38 \ / \ / \ / \ \ / \ / \ / Y=0 0 -------- 1,4 ----- 5,8,11 ----- 9,36 ---- / \ / \ Y=-1 6 --------- 7 ^ ^ ^ ^ ^ ^ ^ ^ X=0 1 2 3 4 5 6 7 ``` A segment 0 to 1 is unfolded to ``` 2-----3 \ \ 0-----1 ``` Then 0 to 3 is unfolded likewise, but the folds are the opposite way. Where 1-2 went on the left, for 3-6 goes to the right. ``` 2-----3 2-----3 \ / \ / \ / \ / 0----1,4----5 0----1,4---5,8----9 / / \ / / \ 6 6-----7 ``` Successive unfolds go alternate ways. Taking two unfold at a time is segment replacement by the 0 to 9 figure (rotated as necessary). The curve never crosses itself. Vertices touch at triangular corners. Points can be visited 1, 2 or 3 times. The two triangles have segment 4-5 between. In general points to a level N=3^k have a single segment between two blobs, for example N=0 to N=3^6=729 below. But as the curve continues it comes back to put further segments there (and a single segment between bigger blobs). ``` * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * O * * * * * * * * * * * * * * * * * * * * * * * * * * E * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ``` The top boundary extent is at an angle +60 degrees and the bottom at -30 degrees, ``` / 60 deg / / O------------------- --__ --__ 30 deg ``` An even expansion level is within a rectangle with endpoint at X=2\*3^(k/2),Y=0. ### Arms The curve fills a sixth of the plane and six copies rotated by 60, 120, 180, 240 and 300 degrees mesh together perfectly. The `"arms"` parameter can choose 1 to 6 such curve arms successively advancing. For example `"arms => 6"` begins as follows. N=0,6,12,18,etc is the first arm (the same shape as the plain curve above), then N=1,7,13,19 the second, N=2,8,14,20 the third, etc. ``` \ / \ / \ / \ / --- 7,8,26 ----------------- 1,12,19 --- / \ / \ \ / \ / \ / \ / \ / \ / --- 3,14,21 ------------- 0,1,2,3,4,5 -------------- 6,11,24 --- / \ / \ / \ / \ / \ / \ \ / \ / ---- 9,10,28 ---------------- 5,16,23 --- / \ / \ / \ / \ ``` With six arms every X,Y point is visited three times, except the origin 0,0 where all six begin. Every edge between points is traversed once. ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. - "$path = Math::PlanePath::AlternateTerdragon-\>new ()" - "$path = Math::PlanePath::AlternateTerdragon-\>new (arms =\> 6)" Create and return a new path object. The optional `"arms"` parameter can make 1 to 6 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 positions give 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"` up to three times. `"xy_to_n()"` returns the smallest of the these N values. - "@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 3 Ns for a given `"$x,$y"`. If arms=6 then every even `"$x,$y"` except the origin has exactly 3 Ns. ### Descriptive Methods - "$n = $path-\>n\_start()" Return 0, the first N in the path. - "$dx = $path-\>dx\_minimum()" - "$dx = $path-\>dx\_maximum()" - "$dy = $path-\>dy\_minimum()" - "$dy = $path-\>dy\_maximum()" The dX,dY values on the first arm take three possible combinations, being 120 degree angles. ``` dX,dY for arms=1 ----- 2, 0 dX minimum = -1, maximum = +2 -1, 1 dY minimum = -1, maximum = +1 1,-1 ``` For 2 or more arms the second arm is rotated by 60 degrees so giving the following additional combinations, for a total six. This changes the dX minimum. ``` dX,dY for arms=2 or more ----- -2, 0 dX minimum = -2, maximum = +2 1, 1 dY minimum = -1, maximum = +1 -1,-1 ``` - "$sum = $path-\>sumxy\_minimum()" - "$sum = $path-\>sumxy\_maximum()" Return the minimum or maximum values taken by coordinate sum X+Y reached by integer N values in the path. If there's no minimum or maximum then return `"undef"`. S=X+Y is an anti-diagonal. The first arm is entirely above a line 135deg -- -45deg, per the +60deg to -30deg extents shown above. Likewise the second arm which is to 60+60=120deg. They have `"sumxy_minimum = 0"`. More arms and all `"sumxy_maximum"` are unbounded so `"undef"`. - "$diffxy = $path-\>diffxy\_minimum()" - "$diffxy = $path-\>diffxy\_maximum()" Return the minimum or maximum values taken by coordinate difference X-Y reached by integer N values in the path. If there's no minimum or maximum then return `"undef"`. D=X-Y is a leading diagonal. The first arm is entirely right of a line 45deg -- -135deg, per the +60deg to -30deg extents shown above, so it has `"diffxy_minimum = 0"`. More arms and all `"diffxy_maximum"` are unbounded so `"undef"`. ### Level Methods - "($n\_lo, $n\_hi) = $path-\>level\_to\_n\_range($level)" Return `"(0, 3**$level)"`, or for multiple arms return `"(0, $arms *` `3**$level + ($arms-1))"`. There are 3^level segments in a curve level, so 3^level+1 points numbered from 0. For multiple arms there are arms\*(3^level+1) points, numbered from 0 so n\_hi = arms\*(3^level+1)-1. ## FORMULAS ### Turn At each point N the curve always turns 120 degrees either to the left or right, it never goes straight ahead. If N is written in ternary then the lowest non-zero digit at its position gives the turn. Positions are counted from 0 for the least significant digit and up from there. ``` turn ternary lowest non-zero digit ----- --------------------------------------- left 1 at even position or 2 at odd position right 2 at even position or 1 at odd position ``` The flip of turn at odd positions is the "alternating" in the curve. ``` next turn ternary lowest non-2 digit --------- --------------------------------------- left 0 at even position or 1 at odd position right 1 at even position or 0 at odd position ``` ### Total Turn The direction at N, ie. the total cumulative turn, is given by the 1 digits of N written in ternary. ``` direction = 120deg * sum / +1 if digit=1 at even position \ -1 if digit=1 at odd position ``` This is used mod 3 for `"n_to_dxdy()"`. ### X,Y to N The current code is roughly the same as `"TerdragonCurve"` `"xy_to_n()"`, but with a conjugate (negate Y, reverse direction d) after each digit low to high. ### X,Y Visited When arms=6 all "even" points of the plane are visited. As per the triangular representation of X,Y this means ``` X+Y mod 2 == 0 "even" points ``` ## OEIS Sequences in Sloane's Online Encyclopedia of Integer Sequences related to the alternate terdragon include, \ (etc) ``` A156595 next turn 0=left, 1=right (morphism) A189715 N positions of left turns A189716 N positions of right turns A189717 count right turns so far ``` ## HOUSE OF GRAPHS House of Graphs entries for the alternate terdragon curve as a graph include \ etc ``` 19655 level=0 (1-segment path) 594 level=1 (3-segment path) 30397 level=2 30399 level=3 33575 level=4 33577 level=5 ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::TerdragonCurve Math::PlanePath::DragonCurve, Math::PlanePath::AlternatePaper ## HOME PAGE \ ## LICENSE Copyright 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 \.