.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::AlternateTerdragon 3pm" .TH Math::PlanePath::AlternateTerdragon 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::AlternateTerdragon \-\- alternate terdragon curve .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::AlternateTerdragon; \& my $path = Math::PlanePath::AlternateTerdragon\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is the alternate terdragon curve by Davis and Knuth, .IX Xref "Davis Knuth, Donald" .Sp .RS 4 Chandler Davis and Donald Knuth, \*(L"Number Representations and Dragon Curves \&\*(-- I\*(R", Journal Recreational Mathematics, volume 3, number 2 (April 1970), pages 66\-81 and \*(L"Number Representations and Dragon Curves \*(-- \s-1II\*(R",\s0 volume 3, number 3 (July 1970), pages 133\-149. .Sp Reprinted with addendum in Knuth \*(L"Selected Papers on Fun and Games\*(R", 2010, pages 571\-\-614. .RE .PP Points are a triangular grid using every second integer X,Y as per \&\*(L"Triangular Lattice\*(R" in Math::PlanePath, beginning .PP .Vb 11 \& \e / \e / \& Y=2 14,17 \-\-\- 15,24,33 \-\- \& \e / \e \& \e / \e / \& Y=1 2 \-\-\-\-\-\-\- 3,12 \-\-\-\- 10,13,34 \-\- 32,35,38 \& \e / \e / \e / \e \& \e / \e / \e / \& Y=0 0 \-\-\-\-\-\-\-\- 1,4 \-\-\-\-\- 5,8,11 \-\-\-\-\- 9,36 \-\-\-\- \& / \e \& / \e \& Y=\-1 6 \-\-\-\-\-\-\-\-\- 7 \& \& ^ ^ ^ ^ ^ ^ ^ ^ \& X=0 1 2 3 4 5 6 7 .Ve .PP A segment 0 to 1 is unfolded to .PP .Vb 4 \& 2\-\-\-\-\-3 \& \e \& \e \& 0\-\-\-\-\-1 .Ve .PP 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. .PP .Vb 7 \& 2\-\-\-\-\-3 2\-\-\-\-\-3 \& \e / \e / \& \e / \e / \& 0\-\-\-\-1,4\-\-\-\-5 0\-\-\-\-1,4\-\-\-5,8\-\-\-\-9 \& / / \e \& / / \e \& 6 6\-\-\-\-\-7 .Ve .PP 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. .PP 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). .PP .Vb 10 \& * * \& * * * * \& * * * * \& * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * * * * * * * * * \& O * * * * * * * * * * * * * * * * * * * * * * * * * * E \& * * * * * * * * * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * * * \& * * * * * * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * * * * \& * * * * * * * \& * * * * \& * * * * \& * * .Ve .PP The top boundary extent is at an angle +60 degrees and the bottom at \-30 degrees, .PP .Vb 6 \& / 60 deg \& / \& / \& O\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& \-\-_\|_ \& \-\-_\|_ 30 deg .Ve .PP An even expansion level is within a rectangle with endpoint at X=2*3^(k/2),Y=0. .SS "Arms" .IX Subsection "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 \f(CW\*(C`arms\*(C'\fR parameter can choose 1 to 6 such curve arms successively advancing. .PP For example \f(CW\*(C`arms => 6\*(C'\fR 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. .PP .Vb 10 \& \e / \e / \& \e / \e / \& \-\-\- 7,8,26 \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- 1,12,19 \-\-\- \& / \e / \e \& \e / \e / \e / \& \e / \e / \e / \& \-\-\- 3,14,21 \-\-\-\-\-\-\-\-\-\-\-\-\- 0,1,2,3,4,5 \-\-\-\-\-\-\-\-\-\-\-\-\-\- 6,11,24 \-\-\- \& / \e / \e / \e \& / \e / \e / \e \& \e / \e / \& \-\-\-\- 9,10,28 \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- 5,16,23 \-\-\- \& / \e / \e \& / \e / \e .Ve .PP 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. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::AlternateTerdragon\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::AlternateTerdragon\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::AlternateTerdragon->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::AlternateTerdragon\->new (arms => 6)""" 4 .el .IP "\f(CW$path = Math::PlanePath::AlternateTerdragon\->new (arms => 6)\fR" 4 .IX Item "$path = Math::PlanePath::AlternateTerdragon->new (arms => 6)" .PD Create and return a new path object. .Sp The optional \f(CW\*(C`arms\*(C'\fR parameter can make 1 to 6 copies of the curve, each arm successively advancing. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .Sp Fractional positions give an X,Y position along a straight line between the integer positions. .ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4 .el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4 .IX Item "$n = $path->xy_to_n ($x,$y)" Return the point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. If there's nothing at \&\f(CW\*(C`$x,$y\*(C'\fR then return \f(CW\*(C`undef\*(C'\fR. .Sp The curve can visit an \f(CW\*(C`$x,$y\*(C'\fR up to three times. \f(CW\*(C`xy_to_n()\*(C'\fR returns the smallest of the these N values. .ie n .IP """@n_list = $path\->xy_to_n_list ($x,$y)""" 4 .el .IP "\f(CW@n_list = $path\->xy_to_n_list ($x,$y)\fR" 4 .IX Item "@n_list = $path->xy_to_n_list ($x,$y)" Return a list of N point numbers for coordinates \f(CW\*(C`$x,$y\*(C'\fR. .Sp The origin 0,0 has \f(CW\*(C`arms_count()\*(C'\fR many N since it's the starting point for each arm. Other points have up to 3 Ns for a given \f(CW\*(C`$x,$y\*(C'\fR. If arms=6 then every even \f(CW\*(C`$x,$y\*(C'\fR except the origin has exactly 3 Ns. .SS "Descriptive Methods" .IX Subsection "Descriptive Methods" .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .ie n .IP """$dx = $path\->dx_minimum()""" 4 .el .IP "\f(CW$dx = $path\->dx_minimum()\fR" 4 .IX Item "$dx = $path->dx_minimum()" .PD 0 .ie n .IP """$dx = $path\->dx_maximum()""" 4 .el .IP "\f(CW$dx = $path\->dx_maximum()\fR" 4 .IX Item "$dx = $path->dx_maximum()" .ie n .IP """$dy = $path\->dy_minimum()""" 4 .el .IP "\f(CW$dy = $path\->dy_minimum()\fR" 4 .IX Item "$dy = $path->dy_minimum()" .ie n .IP """$dy = $path\->dy_maximum()""" 4 .el .IP "\f(CW$dy = $path\->dy_maximum()\fR" 4 .IX Item "$dy = $path->dy_maximum()" .PD The dX,dY values on the first arm take three possible combinations, being 120 degree angles. .Sp .Vb 5 \& dX,dY for arms=1 \& \-\-\-\-\- \& 2, 0 dX minimum = \-1, maximum = +2 \& \-1, 1 dY minimum = \-1, maximum = +1 \& 1,\-1 .Ve .Sp 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. .Sp .Vb 5 \& dX,dY for arms=2 or more \& \-\-\-\-\- \& \-2, 0 dX minimum = \-2, maximum = +2 \& 1, 1 dY minimum = \-1, maximum = +1 \& \-1,\-1 .Ve .ie n .IP """$sum = $path\->sumxy_minimum()""" 4 .el .IP "\f(CW$sum = $path\->sumxy_minimum()\fR" 4 .IX Item "$sum = $path->sumxy_minimum()" .PD 0 .ie n .IP """$sum = $path\->sumxy_maximum()""" 4 .el .IP "\f(CW$sum = $path\->sumxy_maximum()\fR" 4 .IX Item "$sum = $path->sumxy_maximum()" .PD 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 \&\f(CW\*(C`undef\*(C'\fR. .Sp 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 \f(CW\*(C`sumxy_minimum = 0\*(C'\fR. More arms and all \f(CW\*(C`sumxy_maximum\*(C'\fR are unbounded so \f(CW\*(C`undef\*(C'\fR. .ie n .IP """$diffxy = $path\->diffxy_minimum()""" 4 .el .IP "\f(CW$diffxy = $path\->diffxy_minimum()\fR" 4 .IX Item "$diffxy = $path->diffxy_minimum()" .PD 0 .ie n .IP """$diffxy = $path\->diffxy_maximum()""" 4 .el .IP "\f(CW$diffxy = $path\->diffxy_maximum()\fR" 4 .IX Item "$diffxy = $path->diffxy_maximum()" .PD 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 \f(CW\*(C`undef\*(C'\fR. .Sp 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 \&\f(CW\*(C`diffxy_minimum = 0\*(C'\fR. More arms and all \f(CW\*(C`diffxy_maximum\*(C'\fR are unbounded so \&\f(CW\*(C`undef\*(C'\fR. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 3**$level)\*(C'\fR, or for multiple arms return \f(CW\*(C`(0, $arms * 3**$level + ($arms\-1))\*(C'\fR. .Sp 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. .SH "FORMULAS" .IX Header "FORMULAS" .SS "Turn" .IX Subsection "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. .PP .Vb 4 \& 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 .Ve .PP The flip of turn at odd positions is the \*(L"alternating\*(R" in the curve. .PP .Vb 4 \& 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 .Ve .SS "Total Turn" .IX Subsection "Total Turn" The direction at N, ie. the total cumulative turn, is given by the 1 digits of N written in ternary. .PP .Vb 2 \& direction = 120deg * sum / +1 if digit=1 at even position \& \e \-1 if digit=1 at odd position .Ve .PP This is used mod 3 for \f(CW\*(C`n_to_dxdy()\*(C'\fR. .SS "X,Y to N" .IX Subsection "X,Y to N" The current code is roughly the same as \f(CW\*(C`TerdragonCurve\*(C'\fR \f(CW\*(C`xy_to_n()\*(C'\fR, but with a conjugate (negate Y, reverse direction d) after each digit low to high. .SS "X,Y Visited" .IX Subsection "X,Y Visited" When arms=6 all \*(L"even\*(R" points of the plane are visited. As per the triangular representation of X,Y this means .PP .Vb 1 \& X+Y mod 2 == 0 "even" points .Ve .SH "OEIS" .IX Header "OEIS" Sequences in Sloane's Online Encyclopedia of Integer Sequences related to the alternate terdragon include, .Sp .RS 4 (etc) .RE .PP .Vb 4 \& 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 .Ve .SH "HOUSE OF GRAPHS" .IX Header "HOUSE OF GRAPHS" House of Graphs entries for the alternate terdragon curve as a graph include .Sp .RS 4 etc .RE .PP .Vb 6 \& 19655 level=0 (1\-segment path) \& 594 level=1 (3\-segment path) \& 30397 level=2 \& 30399 level=3 \& 33575 level=4 \& 33577 level=5 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::TerdragonCurve .PP Math::PlanePath::DragonCurve, Math::PlanePath::AlternatePaper .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .