.\" 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::SierpinskiArrowheadCentres 3pm" .TH Math::PlanePath::SierpinskiArrowheadCentres 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::SierpinskiArrowheadCentres \-\- self\-similar triangular path traversal .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::SierpinskiArrowheadCentres; \& my $path = Math::PlanePath::SierpinskiArrowheadCentres\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path is variation on Sierpinski's curve from .IX Xref "Sierpinski, Waclaw" .Sp .RS 4 Waclaw Sierpinski, \*(L"Sur une Courbe Dont Tout Point est un Point de Ramification\*(R", Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, volume 160, January-June 1915, pages 302\-305. .RE .PP The path here takes the centres of each triangle represented by the arrowhead segments. The points visited are the same as the \&\f(CW\*(C`SierpinskiTriangle\*(C'\fR path, but traversing in a connected sequence (rather than across rows). .PP .Vb 10 \& ... ... \& / / \& . 30 . . . . . 65 . ... \& / \e / \& 28\-\-\-\-29 . . . . . . 66 68 9 \& \e \e / \& 27 . . . . . . . 67 8 \& \e \& 26\-\-\-\-25 19\-\-\-\-18\-\-\-\-17 15\-\-\-\-14\-\-\-\-13 7 \& / \e \e / / \& 24 . 20 . 16 . 12 6 \& \e / / \& 23 21 . . 10\-\-\-\-11 5 \& \e / \e \& 22 . . . 9 4 \& / \& 4\-\-\-\- 5\-\-\-\- 6 8 3 \& \e \e / \& 3 . 7 2 \& \e \& 2\-\-\-\- 1 1 \& / \& 0 <\- Y=0 \& \& \-9 \-8 \-7 \-6 \-5 \-4 \-3 \-2 \-1 X=0 1 2 3 4 5 6 7 .Ve .PP The base figure is the N=0 to N=2 shape. It's repeated up in mirror image as N=3 to N=6 then rotated across as N=6 to N=9. At the next level the same is done with N=0 to N=8 as the base, then N=9 to N=17 up mirrored, and N=18 to N=26 across, etc. .PP The X,Y coordinates are on a triangular lattice using every second integer X, per \*(L"Triangular Lattice\*(R" in Math::PlanePath. .PP The base pattern is a triangle like .PP .Vb 9 \& .\-\-\-\-\-\-\-.\-\-\-\-\-\-\-. \& \e / \e / \& \e 2 / \e 1 / \& \e / \e / \& .\- \- \- \-. \& \e / \& \e 0 / \& \e / \& . .Ve .PP Higher levels replicate this within the triangles 0,1,2 but the middle is not traversed. The result is the familiar Sierpinski triangle by connected steps of either 2 across or 1 diagonal. .PP .Vb 10 \& * * * * * * * * * * * * * * * * \& * * * * * * * * \& * * * * * * * * \& * * * * \& * * * * * * * * \& * * * * \& * * * * \& * * \& * * * * * * * * \& * * * * \& * * * * \& * * \& * * * * \& * * \& * * \& * .Ve .PP See the \f(CW\*(C`SierpinskiTriangle\*(C'\fR path to traverse by rows instead. .SS "Level Ranges" .IX Subsection "Level Ranges" Counting the N=0,1,2 part as level 1, each replication level goes from .PP .Vb 2 \& Nstart = 0 \& Nlevel = 3^level \- 1 inclusive .Ve .PP For example level 2 from N=0 to N=3^2\-1=9. Each level doubles in size, .PP .Vb 2 \& 0 <= Y <= 2^level \- 1 \& \- (2^level \- 1) <= X <= 2^level \- 1 .Ve .PP The Nlevel position is alternately on the right or left, .PP .Vb 2 \& Xlevel = / 2^level \- 1 if level even \& \e \- 2^level + 1 if level odd .Ve .PP The Y axis ie. X=0, is crossed just after N=1,5,17,etc which is is 2/3 through the level, which is after two replications of the previous level, .PP .Vb 2 \& Ncross = 2/3 * 3^level \- 1 \& = 2 * 3^(level\-1) \- 1 .Ve .SS "Align Parameter" .IX Subsection "Align Parameter" An optional \f(CW\*(C`align\*(C'\fR parameter controls how the points are arranged relative to the Y axis. The default shown above is \*(L"triangular\*(R". The choices are the same as for the \f(CW\*(C`SierpinskiTriangle\*(C'\fR path. .PP \&\*(L"right\*(R" means points to the right of the axis, packed next to each other and so using an eighth of the plane. .PP .Vb 1 \& align => "right" \& \& | | \& 7 | 26\-25 19\-18\-17 15\-14\-13 \& | / | |/ / \& 6 | 24 20 16 12 \& | | / / \& 5 | 23 21 10\-11 \& | |/ | \& 4 | 22 9 \& | / \& 3 | 4\-\-5\-\-6 8 \& | | |/ \& 2 | 3 7 \& | | \& 1 | 2\-\-1 \& | / \& Y=0 | 0 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP \&\*(L"left\*(R" is similar but skewed to the left of the Y axis, ie. into negative X. .PP .Vb 1 \& align => "left" \& \& \e | \& 26\-25 19\-18\-17 15\-14\-13 | 7 \& | \e \e | | | \& 24 20 16 12 | 6 \& \e | | | \& 23 21 10\-11 | 5 \& \e | \e | \& 22 9 | 4 \& | | \& 4\-\-5\-\-6 8 | 3 \& \e \e | | \& 3 7 | 2 \& \e | \& 2\-\-1 | 1 \& | | \& 0 | Y=0 \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ \& \& \-7 \-6 \-5 \-4 \-3 \-2 \-1 X=0 .Ve .PP \&\*(L"diagonal\*(R" puts rows on diagonals down from the Y axis to the X axis. This uses the whole of the first quadrant, with gaps. .PP .Vb 1 \& align => "diagonal" \& \& | | \& 7 | 26 \& | \e \& 6 | 24\-25 \& | | \& 5 | 23 19 \& | | |\e \& 4 | 22\-21\-20 18 \& | \e \& 3 | 4 17 \& | |\e | \& 2 | 3 5 16\-15 \& | | \e \e \& 1 | 2 6 10 14 \& | \e | |\e \e \& Y=0 | 0\-\-1 7\-\-8\-\-9 11\-12\-13 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP These diagonals visit all points X,Y where X and Y written in binary have no 1\-bits in the same places, ie. where X bitand Y = 0. This is the same as the \f(CW\*(C`SierpinskiTriangle\*(C'\fR with align=diagonal. .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::SierpinskiArrowheadCentres\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::SierpinskiArrowheadCentres\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::SierpinskiArrowheadCentres->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::SierpinskiArrowheadCentres\->new (align => $str)""" 4 .el .IP "\f(CW$path = Math::PlanePath::SierpinskiArrowheadCentres\->new (align => $str)\fR" 4 .IX Item "$path = Math::PlanePath::SierpinskiArrowheadCentres->new (align => $str)" .PD Create and return a new arrowhead path object. \f(CW\*(C`align\*(C'\fR is a string, one of the following as described above. .Sp .Vb 4 \& "triangular" the default \& "right" \& "left" \& "diagonal" .Ve .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 If \f(CW$n\fR is not an integer then the return is on a straight line between the integer points. .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 \- 1)\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "N to X,Y" .IX Subsection "N to X,Y" The align=\*(L"diagonal\*(R" style is the most convenient to calculate. Each ternary digit of N becomes a bit of X and Y. .PP .Vb 4 \& ternary digits of N, high to low \& xbit = state_to_xbit[state+digit] \& ybit = state_to_ybit[state+digit] \& state = next_state[state+digit] .Ve .PP There's a total of 6 states which are the permutations of 0,1,2 in the three triangular parts. The states are in pairs as forward and reverse, but that has no particular significance. Numbering the states by \*(L"3\*(R"s allows the digit 0,1,2 to be added to make an index into tables for X,Y bit and next state. .PP .Vb 10 \& state=0 state=3 \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ \& |^ 2 | | |\e 0 | | \& | \e | | | \e | | \& | \e | | | v | | \& |\-\-\-\-+\-\-\-\-| |\-\-\-\-+\-\-\-\-| \& | |^ | | || | \& | 0 || 1 | | 0 || 1 | \& |\-\-\->|| | |<\-\-\-|v | \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ \& \& state=6 state=9 \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ \& | | | | | | \& | 1 | | | 1 | | \& |\-\-\->| | |<\-\-\-| | \& |\-\-\-\-+\-\-\-\-| |\-\-\-\-+\-\-\-\-| \& |^ |\e 2 | || |^ | \& ||0 | \e | || 2 | \e0 | \& || | v | |v | \e | \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ \& \& state=12 state=15 \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ \& || 0 | | |^ | | \& || | | || 2 | | \& |v | | || | | \& |\-\-\-\-+\-\-\-\-| |\-\-\-\-+\-\-\-\-| \& |\e 1 | | |^ 1 | | \& | \e | 2 | | \e | 0 | \& | v |\-\-\->| | \e |<\-\-\-| \& +\-\-\-\-\-\-\-\-\-+ +\-\-\-\-\-\-\-\-\-+ .Ve .PP The initial state is 0 if an even number of ternary digits, or 6 if odd. In the samples above it can be seen for example that N=0 to N=8 goes upwards as per state 0, whereas N=0 to N=2 goes across as per state 6. .PP Having calculated an X,Y in align=\*(L"diagonal\*(R" style it can be mapped to the other alignments by .PP .Vb 5 \& align coordinates from diagonal X,Y \& \-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& triangular X\-Y, X+Y \& right X, X+Y \& left \-Y, X+Y .Ve .SS "N to dX,dY" .IX Subsection "N to dX,dY" For fractional N the direction of the curve towards the N+1 point can be found from the least significant digit 0 or 1 (ie. a non\-2 digit) and the state at that point. .PP This works because if the least significant ternary digit of N is a 2 then the direction of the curve is determined by the next level up, and so on for all trailing 2s until reaching a non\-2 digit. .PP If N is all 2s then the direction should be reckoned from an initial 0 digit above them, which means the opposite 6 or 0 of the initial state. .SS "Rectangle to N Range" .IX Subsection "Rectangle to N Range" An easy over-estimate of the range can be had from inverting the Nlevel formulas in \*(L"Level Ranges\*(R" above. .PP .Vb 2 \& level = floor(log2(Ymax)) + 1 \& Nmax = 3^level \- 1 .Ve .PP For example Y=5, level=floor(log2(11))+1=3, so Nmax=3^3\-1=26, which is the left end of the Y=7 row, ie. rounded up to the end of the Y=4 to Y=7 replication. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::SierpinskiTriangle .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .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 .