NAME
Math::PlanePath  points on a path through the 2D plane
SYNOPSIS
use Math::PlanePath;
# only a base class, see the subclasses for actual operation
DESCRIPTION
This is the base class for some mathematical paths which map an integer position $n
into coordinates $x,$y
in the plane. The current classes include
SquareSpiral foursided spiral
PyramidSpiral square based pyramid
TriangleSpiral equilateral triangle spiral
TriangleSpiralSkewed equilateral skewed for compactness
DiamondSpiral foursided spiral, looping faster
PentSpiral fivesided spiral
PentSpiralSkewed fivesided spiral, compact
HexSpiral sixsided spiral
HexSpiralSkewed sixsided spiral skewed for compactness
HeptSpiralSkewed sevensided spiral, compact
OctagramSpiral eight pointed star
KnightSpiral an infinite knight's tour
SquareArms fourarm square spiral
DiamondArms fourarm diamond spiral
HexArms sixarm hexagonal spiral
AztecDiamondRings foursided rings
GreekKeySpiral spiral with Greek key motif
SacksSpiral quadratic on an Archimedean spiral
VogelFloret seeds in a sunflower
TheodorusSpiral unit steps at right angles
ArchimedeanChords chords on an Archimedean spiral
MultipleRings concentric circles
PixelRings concentric circles of pixels
Hypot points by distance
HypotOctant first octant points by distance
TriangularHypot points by triangular lattice distance
PythagoreanTree primitive triples by tree
RationalsTree rationals X/Y by tree
PeanoCurve selfsimilar base3 quadrant traversal
HilbertCurve selfsimilar base2 quadrant traversal
ZOrderCurve replicating Z shapes
BetaOmega selfsimilar halfplane traversal
ImaginaryBase replicating in four directions
SquareReplicate replicating squares 3x3
CornerReplicate replicating squares 2x2
DigitGroups digit groups with high zero
FibonacciWordFractal turns by Fibonacci word bits
Flowsnake selfsimilar hexagonal tile traversal
FlowsnakeCentres likewise, but centres of hexagons
GosperReplicate selfsimilar hexagonal tiling
GosperIslands concentric island rings
GosperSide single side/radial
QuintetCurve selfsimilar "+" shape
QuintetCentres likewise, but centres of squares
QuintetReplicate selfsimilar "+" tiling
DragonCurve paper folding
DragonRounded same but roundingoff vertices
DragonMidpoint paper folding midpoints
ComplexMinus twindragon and other base ir
SierpinskiCurve selfsimilar pattern by righttriangles
HIndexing selfsimilar righttriangle pairs
KochCurve replicating triangular notches
KochPeaks two replicating notches
KochSnowflakes concentric notched snowflake rings
KochSquareflakes concentric notched 4sided rings
QuadricCurve eight segment zigzag
QuadricIslands rings of those zigzags
SierpinskiTriangle selfsimilar triangle by rows
SierpinskiArrowhead selfsimilar triangle connectedly
SierpinskiArrowheadCentres likewise, but centres of triangles
Rows fixedwidth rows
Columns fixedheight columns
Diagonals diagonals down from the Y to X axes
Staircase stairs down from the Y to X axes
Corner expanding stripes around a corner
PyramidRows expanding stacked rows pyramid
PyramidSides along the sides of a 45degree pyramid
CellularRule54 cellular automaton rows pattern
CellularRule190 cellular automaton rows pattern
UlamWarburton cellular automaton diamonds
UlamWarburtonQuarter cellular automaton quarterplane
CoprimeColumns coprime X,Y
DivisibleColumns X divisible by Y
File points from a disk file
The paths are object oriented to allow parameters, though many have none as yet. See examples/numbers.pl
in the MathPlanePath sources for a cute sample printout of selected paths or all paths.
Number Types
The $n
and $x,$y
parameters can be either integers or floating point. The paths are meant to do something sensible with floating point fractions. Expect roundingoff for big exponents.
Floating point infinities (when available system) are meant to give nan or infinite returns of some kind (some unspecified kind as yet). n_to_xy()
on negative infinity $n
is generally an empty return, the same as other negative $n
. Calculations which break an input into digits of some base are meant not to loop infinitely on infinities.
Floating point nans (when available) are meant to give nan, infinite, or empty/undef returns, but again of some unspecified kind as yet but in any case again not going into infinite loops.
A few of the classes can operate on Math::BigInt
, Math::BigRat
and Math::BigFloat
inputs and give corresponding outputs, but this is experimental and many classes might truncate a bignum to a float as yet. In general the intention is to make the code generic enough that it can act on overloaded number types. Note that new enough versions of the bignum modules might be required, perhaps Perl 5.8 and up so for instance the **
exponentiation operator is available.
Also, for reference, an undef
input $n
, $x,$y
, etc, is meant to provoke an uninitialized value warning (when warnings are enabled), but doesn't croak etc. Perhaps that will change, but the warning at least prevents bad inputs going unnoticed.
FUNCTIONS
$path = Math::PlanePath::Foo>new (key=>value, ...)

Create and return a new path object. Optional key/value parameters may control aspects of the object.
Foo
here is one of the various subclasses, see the list above and under "SEE ALSO". ($x,$y) = $path>n_to_xy ($n)

Return x,y coordinates of point
$n
on the path. If there's no point$n
then the return is an empty list, so for examplemy ($x,$y) = $path>n_to_xy (123) or next; # usually no negatives in $path
Paths start from
$path>n_start
below, though some will give a position for N=0 or N=0.5 too. $n = $path>xy_to_n ($x,$y)

Return the point number for coordinates
$x,$y
. If there's nothing at$x,$y
then returnundef
.my $n = $path>xy_to_n(20,20); if (! defined $n) { next; # nothing at this x,y }
$x
and$y
can be fractional and the path classes will give an integer$n
which contains$x,$y
within a unit square, circle, or intended figure centred on the integer$n
.For paths which completely tile the plane there's always an
$n
to return, but for the spreadout paths an$x,$y
position may fall in between (no$n
close enough). ($n_lo, $n_hi) = $path>rect_to_n_range ($x1,$y1, $x2,$y2)

Return a range of N values which occur in a rectangle with corners at
$x1
,$y1
and$x2
,$y2
. The range is inclusive. For example,my ($n_lo, $n_hi) = $path>rect_to_n_range (5,5, 5,5); foreach my $n ($n_lo .. $n_hi) { my ($x, $y) = $path>n_to_xy ($n) or next; print "$n $x,$y"; }
The return may be an overestimate of the range, and many of the points between
$n_lo
and$n_hi
might be outside the rectangle, but the range at least bounds N in the rectangle. Classes which can guarantee an exact range say so in their docs.$n_hi
is usually no more than an extra partial row, revolution, or selfsimilar level.$n_lo
is often merely the starting point$path>n_start()
below, which is fine if the origin is in the rectangle, but something away from the origin might actually start higher.$x1
,$y1
and$x2
,$y2
can be fractional and if they partly overlap some N figures then those N's are included in the return. If there's no points in the rectangle then the return may be a "crossed" range like$n_lo=1
,$n_hi=0
(and which makes aforeach
do no loops). Butrect_to_n_range()
might not notice there's no points in the rectangle and instead overestimate the range. $bool = $path>x_negative()
$bool = $path>y_negative()

Return true if the path extends into negative X coordinates and/or negative Y coordinates respectively.
$n = $path>n_start()

Return the first N in the path. In the current classes this is either 0 or 1.
Some classes have secret dubious undocumented support for N values below this (zero or negative), but
n_start
is the intended starting point. $arms = $path>arms_count()

Return the number of arms in a "multiarm" path.
For example in SquareArms this is 4 and each arm increments in turn, so the first arm is N=1,5,9,13, etc, incrementing by 4 each time.
$str = $path>figure()

Return a string name of the figure (shape) intended to be drawn at each
$n
position. This is currently either"square" side 1 centred on $x,$y "circle" diameter 1 centred on $x,$y
Of course this is only a suggestion since PlanePath doesn't draw anything itself. A figure like a diamond for instance can look good too.
$aref = Math::PlanePath::Foo>parameter_info_array()
@list = Math::PlanePath::Foo>parameter_info_list()

Return an arrayref of list describing the parameters taken by a given class. This meant to help making widgets etc for user interaction in a GUI. Each element is a hashref
{ name => parameter key arg for new() description => human readable string type => string "integer","boolean","enum" etc default => value minimum => number, or undef maximum => number, or undef width => integer, suggested display size choices => for enum, an arrayref }
type
is a string, one of"integer" "enum" "boolean" "string" "filename"
"filename" is separate from "string" since it might require subtly different handling to ensure it reaches Perl as a byte string, whereas a "string" type might in principle take Perl wide chars.
For "enum" the
choices
field is the possible values, such as{ name => "flavour", type => "enum", choices => ["strawberry","chocolate"], }
minimum
andmaximum
are omitted if there's no hard limit on the parameter.
GENERAL CHARACTERISTICS
The classes are mostly based on integer $n
positions and those designed for a square grid turn an integer $n
into integer $x,$y
. Usually they give inbetween positions for fractional $n
too. Classes not on a square grid but instead giving fractional X,Y such as SacksSpiral and VogelFloret are designed for a unit circle at each $n
but they too can give inbetween positions on request.
All X,Y positions are calculated by separate n_to_xy()
calls. To follow a path use successive $n
values starting from $path>n_start
.
The separate n_to_xy()
calls were motivated by plotting just some points on a path, such as just the primes or the perfect squares. Perhaps successive positions in some paths could be done in an iterator style more efficiently. The paths with a quadratic "step" are not much worse than a sqrt()
to break N into a segment and offset, but the selfsimilar paths which chop into digits of some radix might increment instead of recalculate.
But when interested in a particular region an iterator will often stray outside for a long time, and going by X,Y in rows or similar may be better, for the squaregrid paths.
Scaling and Orientation
The paths generally make a first move horizontally to the right, or from the X axis anticlockwise, unless there's some more natural orientation. There's no parameters for scaling, offset or reflection as those things are thought better left to a general coordinate transformer to expand or invert for display. But some easy transformations can be had just from the X,Y with
X,Y flip horizontally (mirror image)
X,Y flip vertically (across the X axis)
Y,X rotate +90 degrees (anticlockwise)
Y,X rotate 90 degrees
X,Y rotate 180 degrees
A vertical flip makes the spirals go clockwise instead of anticlockwise, or a horizontal flip the same but starting on the left at the negative X axis.
The Rows and Columns paths are slight exceptions to the rule of not having rotated versions of paths. They started as ways to pass in width and height as generic parameters, and have the path use the one or the other.
For scaling and shifting see for example Transform::Canvas, or for rotating as well see Geometry::AffineTransform.
Loop Step
The paths can be characterized by how much longer each loop or repetition is than the preceding one. For example each cycle around the SquareSpiral is 8 more N points than the preceding.
Step Path
 
0 Rows, Columns (fixed widths)
1 Diagonals
2 SacksSpiral, PyramidSides, Corner, PyramidRows (default)
4 DiamondSpiral, AztecDiamondRings, Staircase
4/2 CellularRule54 (2 rows for +4)
5 PentSpiral, PentSpiralSkewed
5.65 PixelRings (average about 4*sqrt(2))
6 HexSpiral, HexSpiralSkewed, MultipleRings (default)
6/2 CellularRule190 (2 rows for +6)
6.28 ArchimedeanChords (approaching 2*pi)
7 HeptSpiralSkewed
8 SquareSpiral, PyramidSpiral
9 TriangleSpiral, TriangleSpiralSkewed
16 OctagramSpiral
19.74 TheodorusSpiral (approaching 2*pi^2)
32/4 KnightSpiral (4 loops 2wide for +32)
64 DiamondArms (each arm)
72 GreekKeySpiral
128 SquareArms (each arm)
216 HexArms (each arm)
parameter MultipleRings, PyramidRows
totient CoprimeColumns
divcount DivisibleColumns
The step determines which quadratic number sequences make straight lines. For example the gap between successive perfect squares increases by 2 each time (4 to 9 is +5, 9 to 16 is +7, 16 to 25 is +9, etc), so the perfect squares make a straight line in the paths of step 2.
In general straight lines on the stepped paths are quadratics a*k^2+b*k+c with a=step/2. The polygonal numbers are like this, with the (step+2)gonal numbers making a straight line on a "step" path. For example the 7gonals (heptagonals) are 5/2*k^23/2*k and make a straight line on the step=5 PentSpiral. Or the 8gonal octagonal numbers 6/2*k^24/2*k on the step=6 HexSpiral.
There are various interesting properties of primes in quadratic progressions. Some quadratics seem to have more primes than others, see for example "Lucky Numbers of Euler" in Math::PlanePath::PyramidSides. Many quadratics have no primes at all, or none above a certain point, either trivially if always a multiple of 2 etc, or by a more sophisticated reasoning. See "Step 3 Pentagonals" in Math::PlanePath::PyramidRows for a factorization on the roots making a noprimes gap.
A step factor 4 splits a straight line in two, so for example the perfect squares are a straight line on the step=2 "Corner" path, and then on the step=8 SquareSpiral they instead fall on two lines (lower left and upper right). Effectively in that bigger step it's one line of the even squares (2k)^2 == 4*k^2 and another of the odd squares (2k+1)^2. The gap between successive even squares increases by 8 each time and likewise between odd squares.
SelfSimilar Powers
The selfsimilar patterns such as PeanoCurve generally have a base pattern which repeats at powers N=base^level, or some multiple or relation to such a power for things like KochPeaks and GosperIslands.
Base Path
 
2 HilbertCurve, ZOrderCurve (default),
BetaOmega, SierpinskiCurve, HIndexing
ImaginaryBase (default), ComplexMinus (default)
DragonCurve, DragonRounded, DragonMidpoint,
DigitGroups (default), CornerReplicate
3 PeanoCurve (default), GosperIslands, GosperSide
SierpinskiTriangle, SierpinskiArrowhead,
SierpinskiArrowheadCentres,
UlamWarburton, UlamWarburtonQuarter (per level)
4 KochCurve, KochPeaks, KochSnowflakes, KochSquareflakes
5 QuintetCurve, QuintetCentres, QuintetReplicate
7 Flowsnake, FlowsnakeCentres, GosperReplicate
8 QuadricCurve, QuadricIslands
9 SquareReplicate
Fibonacci FibonacciWordFractal
parameter PeanoCurve, ZOrderCurve, ImaginaryBase, DigitGroups
Many number sequences on these paths tend to come out fairly random, or merely show the tiling or nature of the path layout rather than much about the number sequence. Number sequences related to the base can make holes or patterns picking out parts of the path. For example numbers without a particular digit (or digits) in the relevant base show up as holes, eg. "Power of 2 Values" in Math::PlanePath::ZOrderCurve.
Triangular Lattice
Some paths are on triangular or "A2" lattice points like
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
These are done in integer X,Y on a square grid using every second square,
. * . * . * . * . * . *
* . * . * . * . * . * .
. * . * . * . * . * . *
* . * . * . * . * . * .
. * . * . * . * . * . *
* . * . * . * . * . * .
In these coordinates X and Y are either both even or both odd. The X axis and the diagonals X=Y and X=Y divide the plane into six parts.
X=Y X=Y
\ /
\ /
\ /
 X=0
/ \
/ \
/ \
The diagonal X=3*Y is the middle of the first sixth, representing a twelfth of the plane.
The resulting triangles are a little flatter than they should be. The base is width=2 and top height=1, whereas height=sqrt(3) would be equilateral triangles. That sqrt(3) factor can be applied if desired,
X, Y*sqrt(3) side length 2
or
X/2, Y*sqrt(3)/2 side length 1
Integer Y values have the advantage of fitting pixels of the usual kind of raster screen, and not losing precision in floating point results.
If doing a generalpurpose coordinate rotation then be sure to apply the sqrt(3) scale factor first, or the rotation is wrong. Rotations can be made within the integer X,Y coordinates directly as follows (all resulting in integers),
(X3Y)/2, (X+Y)/2 rotate +60 (anticlockwise)
(X+3Y)/2, (YX)/2 rotate 60
(X+3Y)/2, (XY)/2 rotate +120
(3YX)/2, (X+Y)/2 rotate 120
X,Y rotate 180
(X+3Y)/2, (XY)/2 mirror across the X=3*Y twelfth line
The sqrt(3) factor can be worked into a hypotenuse radial distance calculation as follows if comparing distances from the origin.
hypot = sqrt(X*X + 3*Y*Y)
See for instance TriangularHypot taking triangular points in order of this radial distance.
FORMULAS
Triangular Calculations
For a triangular lattice the rotation formulas above allow calculations to be done in the rectangular X,Y which are the inputs and outputs of the PlanePath functions. But an alternative is to number vertically on an angle with coordinates i,j
...
* * * 2
* * * 1
* * * j=0
i=0 1 2
This is usual for hex grid games, and using this internally can simplify the rotations a little,
j, i+j rotate +60 (anticlockwise)
i+j, i rotate 60
ij, i rotate +120
j, ij rotate 120
i, j rotate 180
The conversions between i,j and the rectangular X,Y are
X = 2*i + j i = (XY)/2
Y = j j = Y
A third coordinate k at a +120 angle can be used too,
k=0 k=1 k=2
* * *
* * *
* * *
0 1 2
This is redundant, but has the advantage of making rotations just sign changes and swaps,
k, i, j rotate +60
j, k, i rotate 60
j, k, i rotate +120
k, i, j rotate 120
i, j, k rotate 180
The conversions between i,j and the rectangular X,Y are as above with k worked into the X,Y.
X = 2i + j  k i = (XY)/2 i = (X+Y)/2
Y = j + k j = Y or j = 0
k = 0 k = Y
SEE ALSO
Math::PlanePath::SquareSpiral, Math::PlanePath::PyramidSpiral, Math::PlanePath::TriangleSpiral, Math::PlanePath::TriangleSpiralSkewed, Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiral, Math::PlanePath::PentSpiralSkewed, Math::PlanePath::HexSpiral, Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed, Math::PlanePath::OctagramSpiral, Math::PlanePath::KnightSpiral
Math::PlanePath::HexArms, Math::PlanePath::SquareArms, Math::PlanePath::DiamondArms, Math::PlanePath::AztecDiamondRings, Math::PlanePath::GreekKeySpiral
Math::PlanePath::SacksSpiral, Math::PlanePath::VogelFloret, Math::PlanePath::TheodorusSpiral, Math::PlanePath::ArchimedeanChords, Math::PlanePath::MultipleRings, Math::PlanePath::PixelRings, Math::PlanePath::Hypot, Math::PlanePath::HypotOctant, Math::PlanePath::TriangularHypot
Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::ZOrderCurve, Math::PlanePath::BetaOmega, Math::PlanePath::ImaginaryBase, Math::PlanePath::SquareReplicate, Math::PlanePath::CornerReplicate, Math::PlanePath::DigitGroups, Math::PlanePath::FibonacciWordFractal
Math::PlanePath::Flowsnake, Math::PlanePath::FlowsnakeCentres, Math::PlanePath::GosperReplicate, Math::PlanePath::GosperIslands, Math::PlanePath::GosperSide
Math::PlanePath::QuintetCurve, Math::PlanePath::QuintetCentres, Math::PlanePath::QuintetReplicate
Math::PlanePath::KochCurve, Math::PlanePath::KochPeaks, Math::PlanePath::KochSnowflakes, Math::PlanePath::KochSquareflakes
Math::PlanePath::QuadricCurve, Math::PlanePath::QuadricIslands
Math::PlanePath::SierpinskiCurve, Math::PlanePath::HIndexing
Math::PlanePath::SierpinskiTriangle, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::SierpinskiArrowheadCentres
Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded, Math::PlanePath::DragonMidpoint, Math::PlanePath::ComplexMinus
Math::PlanePath::Rows, Math::PlanePath::Columns, Math::PlanePath::Diagonals, Math::PlanePath::Staircase, Math::PlanePath::Corner
Math::PlanePath::PyramidRows, Math::PlanePath::PyramidSides, Math::PlanePath::CellularRule54, Math::PlanePath::CellularRule190, Math::PlanePath::UlamWarburton, Math::PlanePath::UlamWarburtonQuarter
Math::PlanePath::PythagoreanTree, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns, Math::PlanePath::DivisibleColumns, Math::PlanePath::File
mathimage, displaying various sequences on these paths.
examples/numbers.pl in the MathPlanePath source code, to print all the paths.
Math::Fractal::Curve, Math::Curve::Hilbert, Algorithm::SpatialIndex::Strategy::QuadTree
PerlMagick (Image::Magick) demo scripts lsys.pl and tree.pl
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
http://user42.tuxfamily.org/mathplanepath/gallery.html
LICENSE
Copyright 2010, 2011 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.