Math::PlanePath::Flowsnake -- self-similar path through hexagons
use Math::PlanePath::Flowsnake; my $path = Math::PlanePath::Flowsnake->new; my ($x, $y) = $path->n_to_xy (123);
This path is an integer version of the flowsnake curve by William Gosper,
39----40----41 8 \ \ 32----33----34 38----37 42 7 \ \ / / 31----30 35----36 43 47----48 6 / \ \ \ 28----29 17----16----15 44 46 49--.. 5 / \ \ \ / 27 23----22 18----19 14 45 4 \ \ \ / / 26 24 21----20 13 11----10 3 \ / \ / / 25 4---- 5---- 6 12 9 2 \ \ / 3---- 2 7---- 8 1 / 0---- 1 y=0 x=-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
The points are spread out on every second X coordinate to make little triangles with integer coordinates, per "Triangular Lattice" in Math::PlanePath.
The basic pattern is the seven points 0 to 6,
4---- 5---- 6 \ \ 3---- 2 / 0---- 1
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. The next level can be seen at the multiple-of-7 points N=0,7,14,21,28,35,42,49.
42 ----------- --- 35 --- ----------- --- 28 49 --- --- ---- 14 --- ----------- | 21 | | | | ---- 7 ----- 0 ---
Notice this is the same shape as N=0 to N=6, but rotated by atan(1/sqrt(7)) = 20.68 degrees anti-clockwise. Each level rotates further and for example after about 18 levels it goes all the way around and back to the first quadrant.
The rotation doesn't fill the plane though, only 1/3 of it. The shape fattens as it curls around, but leaves a spiral gap beneath (see "Arms" below).
The base pattern corresponds to a tiling by hexagons as follows, with the "***" lines being the base figure.
. . / \ / \ / \ / \ . . . | | | | | | 4*****5*****6 /*\ / \ /*\ / * \ / \ / * \ . * . . * . | * | | *| | *| | *| . 3*****2 7... \ / \ /*\ / \ / \ / * \ / . . * . | | * | | |* | 0*****1 . \ / \ / \ / \ / . .
In the next level the parts corresponding to 1, 2 and 6 are reversed because they have their hexagon to the right of the line segment, rather than to the left.
The optional arms parameter can give up to three copies of the flowsnake, each advancing successively. For example arms=>3 is as follows. Notice the N=3*k points are the plain curve, N=3*k+1 is a copy rotated by 120 degrees (1/3 around), and N=3*k+2 is a copy rotated by 240 degrees (2/3 around).
arms
arms=>3
arms => 3 51----48----45 5 \ \ ... 69----66 54----57 42 4 \ \ \ / / 28----25----22 78 72 63----60 39 33----30 3 \ \ \ / \ / / 31----34 19 75 12----15----18 36 27 2 / / \ \ / 40----37 16 4---- 1 9---- 6 21----24 1 / \ \ / 43 55----58 13 7 0---- 3 74----77---... <- Y=0 \ \ \ \ / \ 46 52 61 10 2 8----11 71----68 -1 \ / / \ / / / 49 64 70----73 5 14 62----65 -2 \ / / / / 67 76 20----17 59 53----50 -3 / / \ / / ... 23 35----38 56 47 -4 \ \ \ / 26 32 41----44 -5 \ / 29 -6 ^ -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
Essentially the flowsnake fills an ever expanding hexagon with one corner at the origin. In the following picture the plain curve fills "A" and there's room for two more arms to fill B and C, rotated 120 and 240 degrees respectively.
*---* / \ *---* A * / \ / * B O---* \ / \ *---* C * \ / *---*
But the sides of these "hexagons" are not straight lines, they're wild wiggly spiralling S shapes, and the endpoints rotate around (by the angle described above) at each level. But opposing sides are symmetric, so they mesh perfectly and with three arms fill the plane.
The flowsnake can also be thought of as successively subdividing line segments with suitably scaled copies of the 0 to 7 figure (or its reversal).
The code here could be used for that by taking points N=0 to N=7^level. The Y coordinates should be multiplied by sqrt(3) to make proper equilateral triangles, then a rotation and scaling to make the endpoint come out at some desired point, such as X=1,Y=0. With such a scaling the path is confined to a finite fractal boundary.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::Flowsnake->new ()
$path = Math::PlanePath::Flowsnake->new (arms => $a)
Create and return a new flowsnake path object.
The optional arms parameter gives between 1 and 3 copies of the curve 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.
$n
$n < 0
Fractional positions give an X,Y position along a straight line between the integer positions.
($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)
In the current code the returned range is exact, meaning $n_lo and $n_hi 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.)
$n_lo
$n_hi
The current approach presses the FlowsnakeCentres code into use. Because the tiling in Flowsnake and FlowsnakeCentres is the same, the X,Y coordinates for a given N are no more than 1 away in the grid.
The way the two lowest shapes are arranged in fact means that if the Flowsnake N is at X,Y then the same N in FlowsnakeCentres is at one of three locations
X, Y same X-2, Y left X-1, Y-1 left down
This is true even when the "arms" multiple paths are in use (the same arms in both coordinates).
Is there an easy way to know which of the three offsets is right? The current approach is to put each through FlowsnakeCentres to make an N, and put that N back through Flowsnake n_to_xy() to see if it's the target $n.
n_to_xy()
The current code calculates an exact rect_to_n_range() by searching for the highest and lowest Ns which are in the rectangle.
rect_to_n_range()
The curve at a given level is bounded by the Gosper island shape but the wiggly sides make it difficult to calculate, so a bounding radius sqrt(7)^level, plus a bit, is used. The portion of the curve comprising a given set of high digits of N can be excluded if the N point is more than that radius away from the rectangle.
When a part of the curve is excluded it prunes a whole branch of the digits tree. When the lowest digit is reached then a check for that point being actually within the rectangle is made. The radius calculation is a bit rough, and it doesn't take into account the direction of the curve, so it's a rather large over-estimate, but it works.
The same sort of search can be applied for highest and lowest N in a non-rectangular shapes, calculating a radial distance away from the shape. The distance calculation doesn't have to be exact either, it can go from something bounding the shape until the lowest digit is reached and an individual X,Y is considered as a candidate for high or low N.
Math::PlanePath, Math::PlanePath::FlowsnakeCentres, Math::PlanePath::GosperIslands
Math::PlanePath::KochCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoCurve, Math::PlanePath::ZOrderCurve
"New Gosper Space Filling Curves" by Fukuda, Shimizu and Nakamura, on flowsnake variations in bigger hexagons (with wiggly sides too).
http://kilin.clas.kitasato-u.ac.jp/museum/gosperex/343-024.pdf or if down then at archive.org http://web.archive.org/web/20070630031400/http://kilin.u-shizuoka-ken.ac.jp/museum/gosperex/343-024.pdf
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2010, 2011, 2012 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 <http://www.gnu.org/licenses/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.