.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" 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 turned on, 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 .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::FlowsnakeCentres 3pm" .TH Math::PlanePath::FlowsnakeCentres 3pm "2014-09-03" "perl v5.20.1" "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::FlowsnakeCentres \-\- self\-similar path of hexagon centres .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::FlowsnakeCentres; \& my $path = Math::PlanePath::FlowsnakeCentres\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path is a variation of the flowsnake curve by William Gosper which follows the flowsnake tiling the same way but the centres of the hexagons instead of corners across. The result is the same overall shape, but a symmetric base figure. .IX Xref "Gosper, William" .PP .Vb 10 \& 39\-\-\-\-40 8 \& / \e \& 32\-\-\-\-33 38\-\-\-\-37 41 7 \& / \e \e \e \& 31\-\-\-\-30 34\-\-\-\-35\-\-\-\-36 42 47 6 \& \e / / \e \& 28\-\-\-\-29 16\-\-\-\-15 43 46 48\-\-... 5 \& / / \e \e \e \& 27 22 17\-\-\-\-18 14 44\-\-\-\-45 4 \& / / \e \e \e \& 26 23 21\-\-\-\-20\-\-\-\-19 13 10 3 \& \e \e / / \e \& 25\-\-\-\-24 4\-\-\-\- 5 12\-\-\-\-11 9 2 \& / \e / \& 3\-\-\-\- 2 6\-\-\-\- 7\-\-\-\- 8 1 \& \e \& 0\-\-\-\- 1 <\- Y=0 \& \& \-5 \-4 \-3 \-2 \-1 X=0 1 2 3 4 5 6 7 8 9 .Ve .PP The points are spread out on every second X coordinate to make little triangles with integer coordinates, per \*(L"Triangular Lattice\*(R" in Math::PlanePath. .PP The base pattern is the seven points 0 to 6, .PP .Vb 5 \& 4\-\-\-\- 5 \& / \e \& 3\-\-\-\- 2 6\-\-\- \& \e \& 0\-\-\-\- 1 .Ve .PP This repeats at 7\-fold increasing scale, with sub-sections rotated according to the edge direction, and the 1, 2 and 6 sub-sections in reverse. Eg. N=7 to N=13 is the \*(L"1\*(R" part taking the base figure in reverse and rotated so the end points towards the \*(L"2\*(R". .PP The next level can be seen at the midpoints of each such group, being N=2,11,18,23,30,37,46. .PP .Vb 10 \& \-\-\-\- 37 \& \-\-\-\- \-\-\- \& 30\-\-\-\- \-\-\- \& | \-\-\- \& | 46 \& | \& | \-\-\-\-18 \& | \-\-\-\-\- \-\-\- \& 23\-\-\- \-\-\- \& \-\-\- \& \-\-\- 11 \& \-\-\-\-\- \& 2 \-\-\- .Ve .SS "Arms" .IX Subsection "Arms" The optional \f(CW\*(C`arms\*(C'\fR parameter can give up to three copies of the curve, each advancing successively. For example \f(CW\*(C`arms=>3\*(C'\fR is as follows. Notice the N=3*k points are the plain curve, and N=3*k+1 and N=3*k+2 are rotated copies of it. .PP .Vb 10 \& 84\-\-\-... 48\-\-\-\-45 5 \& / / \e \& 81 66 51\-\-\-\-54 42 4 \& / / \e \e \e \& 28\-\-\-\-25 78 69 63\-\-\-\-60\-\-\-\-57 39 30 3 \& / \e \e \e / / \e \& 31\-\-\-\-34 22 75\-\-\-\-72 12\-\-\-\-15 36\-\-\-\-33 27 2 \& \e \e / \e / \& 40\-\-\-\-37 19 4 9\-\-\-\- 6 18\-\-\-\-21\-\-\-\-24 1 \& / / / \e \e \& 43 58 16 7 1 0\-\-\-\- 3 77\-\-\-\-80 <\- Y=0 \& / / \e \e \e / \e \& 46 55 61 13\-\-\-\-10 2 11 74\-\-\-\-71 83 \-1 \& \e \e \e / / \e \e \e \& 49\-\-\-\-52 64 73 5\-\-\-\- 8 14 65\-\-\-\-68 86 \-2 \& / / \e / / / \& ... 67\-\-\-\-70 76 20\-\-\-\-17 62 53 ... \-3 \& \e / / / / \e \& 85\-\-\-\-82\-\-\-\-79 23 38 59\-\-\-\-56 50 \-4 \& / / \e / \& 26 35 41\-\-\-\-44\-\-\-\-47 \-5 \& \e \e \& 29\-\-\-\-32 \-6 \& \& ^ \& \-9 \-8 \-7 \-6 \-5 \-4 \-3 \-2 \-1 X=0 1 2 3 4 5 6 7 8 9 .Ve .PP As described in \*(L"Arms\*(R" in Math::PlanePath::Flowsnake the flowsnake essentially fills a hexagonal shape with wiggly sides. For this Centres variation the start of each arm corresponds to the centre of a little hexagon. The N=0 little hexagon is at the origin, and the 1 and 2 beside and below, .PP .Vb 12 \& ^ / \e / \e \& \e \e / \e \& | \e | | \& | 1 | 0\-\-\-> \& | | | \& \e / \e / \& \e / \e / \& | | \& | 2 | \& | / | \& / / \& v \e / .Ve .PP Like the main Flowsnake the sides of the arms mesh perfectly and three arms fill the plane. .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::FlowsnakeCentres\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::FlowsnakeCentres\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::FlowsnakeCentres->new ()" Create and return a new path object. .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_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" In the current code the returned range is exact, meaning \f(CW$n_lo\fR and \&\f(CW$n_hi\fR are the smallest and biggest in the rectangle, but don't rely on that yet since finding the exact range is a touch on the slow side. (The advantage of which though is that it helps avoid very big ranges from a simple over-estimate.) .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, 7**$level \- 1)\*(C'\fR, or for multiple arms return \f(CW\*(C`(0, $arms * 7**$level \- 1)\*(C'\fR. .Sp There are 7^level points in a level, or arms*7^level for multiple arms, numbered starting from 0. .SH "FORMULAS" .IX Header "FORMULAS" .SS "N to X,Y" .IX Subsection "N to X,Y" The \f(CW\*(C`n_to_xy()\*(C'\fR calculation follows Ed Schouten's method .Sp .RS 4 .RE .PP breaking N into base\-7 digits, applying reversals from high to low according to digits 1, 2, or 6, then applying rotation and position according to the resulting digits. .PP Unlike Ed's code, the path here starts from N=0 at the edge of the Gosper island shape and for that reason doesn't cover the plane. An offset of N\-2*7^21 and suitable X,Y offset can be applied to get the same result. .SS "X,Y to N" .IX Subsection "X,Y to N" The \f(CW\*(C`xy_to_n()\*(C'\fR calculation also follows Ed Schouten's method. It's based on a nice observation that the seven cells of the base figure can be identified from their X,Y coordinates, and the centre of those seven cell figures then shrunk down a level to be a unit apart, thus generating digits of N from low to high. .PP In triangular grid X,Y a remainder is formed .PP .Vb 1 \& m = (x + 2*y) mod 7 .Ve .PP Taking the base figure's N=0 at 0,0 the remainders are .PP .Vb 5 \& 4\-\-\-\- 6 \& / \e \& 1\-\-\-\- 3 5 \& \e \& 0\-\-\-\- 2 .Ve .PP The remainders are unchanged when the shape is moved by some multiple of the next level X=5,Y=1 or the same at 120 degrees X=1,Y=3 or 240 degrees X=\-4,Y=1. Those vectors all have X+2*Y==0 mod 7. .PP From the m remainder an offset can be applied to move X,Y to the 0 position, leaving X,Y a multiple of the next level vectors X=5,Y=1 etc. Those vectors can then be shrunk down with .PP .Vb 2 \& Xshrunk = (3*Y + 5*X) / 14 \& Yshrunk = (5*Y \- X) / 14 .Ve .PP This gives integers since 3*Y+5*X and 5*Y\-X are always multiples of 14. For example the N=35 point at X=2,Y=6 reduces to X = (3*6+5*2)/14 = 2 and Y = (5*6\-2)/14 = 2, which is then the \*(L"5\*(R" part of the base figure. .PP The remainders can be mapped to digits and then reversals and rotations applied, from high to low, according to the edge orientation. Those steps can be combined in a single lookup table with 6 states (three rotations, and each one forward or reverse). .PP For the main curve the reduction ends at 0,0. For the multi-arm form the second arm ends to the right at \-2,0 and the third below at \-1,\-1. Notice the modulo and shrink procedure maps those three points back to themselves unchanged. The calculation can be done without paying attention to which arms are supposed to be in use. On reaching one of the three ends the \*(L"arm\*(R" is determined and the original X,Y can be rejected or accepted accordingly. .PP The key to this approach is that the base figure is symmetric around a central point, so the tiling can be broken down first, and the rotations or reversals in the path applied afterwards. Can it work on a non-symmetric base figure like the \*(L"across\*(R" style of the main Flowsnake, or something like the \f(CW\*(C`DragonCurve\*(C'\fR for that matter? .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::Flowsnake, Math::PlanePath::GosperIslands .PP Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve .PP \*(-- Ed Schouten's code .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 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 .