1Math::PlanePath(3)    User Contributed Perl Documentation   Math::PlanePath(3)
2
3
4

NAME

6       Math::PlanePath -- points on a path through the 2-D plane
7

SYNOPSIS

9        use Math::PlanePath;
10        # only a base class, see the subclasses for actual operation
11

DESCRIPTION

13       This is a base class for some mathematical paths which map an integer
14       position $n to and from coordinates "$x,$y" in the 2D plane.
15
16       The current classes include the following.  The intention is that any
17       "Math::PlanePath::Something" is a PlanePath, and supporting base
18       classes or related things are further down like
19       "Math::PlanePath::Base::Xyzzy".
20
21           SquareSpiral           four-sided spiral
22           PyramidSpiral          square base pyramid
23           TriangleSpiral         equilateral triangle spiral
24           TriangleSpiralSkewed   equilateral skewed for compactness
25           DiamondSpiral          four-sided spiral, looping faster
26           PentSpiral             five-sided spiral
27           PentSpiralSkewed       five-sided spiral, compact
28           HexSpiral              six-sided spiral
29           HexSpiralSkewed        six-sided spiral skewed for compactness
30           HeptSpiralSkewed       seven-sided spiral, compact
31           AnvilSpiral            anvil shape
32           OctagramSpiral         eight pointed star
33           KnightSpiral           an infinite knight's tour
34           CretanLabyrinth        7-circuit extended infinitely
35
36           SquareArms             four-arm square spiral
37           DiamondArms            four-arm diamond spiral
38           AztecDiamondRings      four-sided rings
39           HexArms                six-arm hexagonal spiral
40           GreekKeySpiral         square spiral with Greek key motif
41           MPeaks                 "M" shape layers
42
43           SacksSpiral            quadratic on an Archimedean spiral
44           VogelFloret            seeds in a sunflower
45           TheodorusSpiral        unit steps at right angles
46           ArchimedeanChords      unit chords on an Archimedean spiral
47           MultipleRings          concentric circles
48           PixelRings             concentric rings of midpoint pixels
49           FilledRings            concentric rings of pixels
50           Hypot                  points by distance
51           HypotOctant            first octant points by distance
52           TriangularHypot        points by triangular distance
53           PythagoreanTree        X^2+Y^2=Z^2 by trees
54
55           PeanoCurve             3x3 self-similar quadrant
56           PeanoDiagonals         across unit squares
57           WunderlichSerpentine   transpose parts of PeanoCurve
58           HilbertCurve           2x2 self-similar quadrant
59           HilbertSides           along sides of unit squares
60           HilbertSpiral          2x2 self-similar whole-plane
61           ZOrderCurve            replicating Z shapes
62           GrayCode               Gray code splits
63           WunderlichMeander      3x3 "R" pattern quadrant
64           BetaOmega              2x2 self-similar half-plane
65           AR2W2Curve             2x2 self-similar of four parts
66           KochelCurve            3x3 self-similar of two parts
67           DekkingCurve           5x5 self-similar, edges
68           DekkingCentres         5x5 self-similar, centres
69           CincoCurve             5x5 self-similar
70
71           ImaginaryBase          replicate in four directions
72           ImaginaryHalf          half-plane replicate three directions
73           CubicBase              replicate in three directions
74           SquareReplicate        3x3 replicating squares
75           CornerReplicate        2x2 replicating "U"
76           LTiling                self-similar L shapes
77           DigitGroups            digits grouped by zeros
78           FibonacciWordFractal   turns by Fibonacci word bits
79
80           Flowsnake              self-similar hexagonal tile traversal
81           FlowsnakeCentres         likewise but centres of hexagons
82           GosperReplicate        self-similar hexagonal tiling
83           GosperIslands          concentric island rings
84           GosperSide             single side or radial
85
86           QuintetCurve           self-similar "+" traversal
87           QuintetCentres           likewise but centres of squares
88           QuintetReplicate       self-similar "+" tiling
89
90           DragonCurve            paper folding
91           DragonRounded          paper folding rounded corners
92           DragonMidpoint         paper folding segment midpoints
93           AlternatePaper         alternating direction folding
94           AlternatePaperMidpoint alternating direction folding, midpoints
95           TerdragonCurve         ternary dragon
96           TerdragonRounded       ternary dragon rounded corners
97           TerdragonMidpoint      ternary dragon segment midpoints
98           AlternateTerdragon     alternate ternary dragon
99           R5DragonCurve          radix-5 dragon curve
100           R5DragonMidpoint       radix-5 dragon curve midpoints
101           CCurve                 "C" curve
102           ComplexPlus            base i+realpart
103           ComplexMinus           base i-realpart, including twindragon
104           ComplexRevolving       revolving base i+1
105
106           SierpinskiCurve        self-similar right-triangles
107           SierpinskiCurveStair   self-similar right-triangles, stair-step
108           HIndexing              self-similar right-triangles, squared up
109
110           KochCurve              replicating triangular notches
111           KochPeaks              two replicating notches
112           KochSnowflakes         concentric notched 3-sided rings
113           KochSquareflakes       concentric notched 4-sided rings
114           QuadricCurve           eight segment zig-zag
115           QuadricIslands           rings of those zig-zags
116           SierpinskiTriangle     self-similar triangle by rows
117           SierpinskiArrowhead    self-similar triangle connectedly
118           SierpinskiArrowheadCentres  likewise but centres of triangles
119
120           Rows                   fixed-width rows
121           Columns                fixed-height columns
122           Diagonals              diagonals between X and Y axes
123           DiagonalsAlternating   diagonals Y to X and back again
124           DiagonalsOctant        diagonals between Y axis and X=Y centre
125           Staircase              stairs down from the Y to X axes
126           StaircaseAlternating   stairs Y to X and back again
127           Corner                 expanding stripes around a corner
128           CornerAlternating      expanding up and down around a corner
129           PyramidRows            expanding stacked rows pyramid
130           PyramidSides           along the sides of a 45-degree pyramid
131           CellularRule           cellular automaton by rule number
132           CellularRule54         cellular automaton rows pattern
133           CellularRule57         cellular automaton (rule 99 mirror too)
134           CellularRule190        cellular automaton (rule 246 mirror too)
135           UlamWarburton          cellular automaton diamonds
136           UlamWarburtonQuarter   cellular automaton quarter-plane
137
138           DiagonalRationals      rationals X/Y by diagonals
139           FactorRationals        rationals X/Y by prime factorization
140           GcdRationals           rationals X/Y by rows with GCD integer
141           RationalsTree          rationals X/Y by tree
142           FractionsTree          fractions 0<X/Y<1 by tree
143           ChanTree               rationals X/Y multi-child tree
144           CfracDigits            continued fraction 0<X/Y<1 by digits
145           CoprimeColumns         coprime X,Y
146           DivisibleColumns       X divisible by Y
147           WythoffArray           Fibonacci recurrences
148           WythoffPreliminaryTriangle
149           PowerArray             powers in rows
150           File                   points from a disk file
151
152       And in the separate Math-PlanePath-Toothpick distribution
153
154           ToothpickTree          pattern of toothpicks
155           ToothpickReplicate     same by replication rather than tree
156           ToothpickUpist         toothpicks only growing upwards
157           ToothpickSpiral        toothpicks around the origin
158
159           LCornerTree            L-shape corner growth
160           LCornerReplicate       same by replication rather than tree
161           OneOfEight
162           HTree                  H shapes replicated
163
164       The paths are object oriented to allow parameters, though many have
165       none.  See "examples/numbers.pl" in the Math-PlanePath sources for a
166       sample printout of numbers from selected paths or all paths.
167
168   Number Types
169       The $n and "$x,$y" parameters can be either integers or floating point.
170       The paths are meant to do something sensible with fractions but expect
171       round-off for big floating point exponents.
172
173       Floating point infinities (when available) give NaN or infinite returns
174       of some kind (some unspecified kind as yet).  "n_to_xy()" on negative
175       infinity is an empty return the same as other negative $n.
176
177       Floating point NaNs (when available) give NaN, infinite, or empty/undef
178       returns, but again of some unspecified kind as yet.
179
180       Most of the classes can operate on overloaded number types as inputs
181       and give corresponding outputs.
182
183           Math::BigInt        maybe perl 5.8 up for ** operator
184           Math::BigRat
185           Math::BigFloat
186           Number::Fraction    1.14 or higher for abs()
187
188       A few classes might truncate a bignum or a fraction to a float as yet.
189       In general the intention is to make the calculations generic enough to
190       act on any sensible number type.  Recent enough versions of the bignum
191       modules might be required, perhaps "BigInt" of Perl 5.8 or higher for
192       "**" exponentiation operator.
193
194       For reference, an "undef" input as $n, $x, $y, etc, is designed to
195       provoke an uninitialized value warning when warnings are enabled.
196       Perhaps that will change, but the warning at least prevents bad inputs
197       going unnoticed.
198

FUNCTIONS

200       In the following "Foo" is one of the various subclasses, see the list
201       above and under "SEE ALSO".
202
203   Constructor
204       "$path = Math::PlanePath::Foo->new (key=>value, ...)"
205           Create and return a new path object.  Optional key/value parameters
206           may control aspects of the object.
207
208   Coordinate Methods
209       "($x,$y) = $path->n_to_xy ($n)"
210           Return X,Y coordinates of point $n on the path.  If there's no
211           point $n then the return is an empty list.  For example
212
213               my ($x,$y) = $path->n_to_xy (-123)
214                 or next;   # no negatives in $path
215
216           Paths start from "$path->n_start()" below, though some will give a
217           position for N=0 or N=-0.5 too.
218
219       "($dx,$dy) = $path->n_to_dxdy ($n)"
220           Return the change in X and Y going from point $n to point "$n+1",
221           or for paths with multiple arms from $n to "$n+$arms_count" (thus
222           advancing one point along the arm of $n).
223
224               +  $n+1 == $next_x,$next_y
225               ^
226               |
227               |                    $dx = $next_x - $x
228               +  $n == $x,$y       $dy = $next_y - $y
229
230           $n can be fractional and in that case the dX,dY is from that
231           fractional $n position to "$n+1" (or "$n+$arms").
232
233                      frac $n+1 == $next_x,$next_y
234                           v
235               integer *---+----
236                       |  /
237                       | /
238                       |/                 $dx = $next_x - $x
239                  frac +  $n == $x,$y     $dy = $next_y - $y
240                       |
241               integer *
242
243           In both cases "n_to_dxdy()" is the difference "$dx=$next_x-$x,
244           $dy=$next_y-$y".  Currently for most paths it's merely two
245           "n_to_xy()" calls to calculate the two points, but some paths can
246           calculate a dX,dY with a little less work.
247
248       "$rsquared = $path->n_to_radius ($n)"
249       "$rsquared = $path->n_to_rsquared ($n)"
250           Return the radial distance R=sqrt(X^2+Y^2) of point $n, or the
251           radius squared R^2=X^2+Y^2.  If there's no point $n then the return
252           is "undef".
253
254           For a few paths, these might be calculated with less work than
255           "n_to_xy()".  For example the "SacksSpiral" is simply R^2=N, or the
256           "MultipleRings" path with its default step=6 has an integer radius
257           for integer $n whereas "$x,$y" are fractional (and so inexact).
258
259       "$n = $path->xy_to_n ($x,$y)"
260           Return the N point number at coordinates "$x,$y".  If there's
261           nothing at "$x,$y" then return "undef".
262
263               my $n = $path->xy_to_n(20,20);
264               if (! defined $n) {
265                 next;   # nothing at this X,Y
266               }
267
268           $x and $y can be fractional and the path classes will give an
269           integer $n which contains "$x,$y" within a unit square, circle, or
270           intended figure centred on the integer $n.
271
272           For paths which completely fill the plane there's always an $n to
273           return, but for the spread-out paths an "$x,$y" position may fall
274           in between (no $n close enough) and give "undef".
275
276       "@n_list = $path->xy_to_n_list ($x,$y)"
277           Return a list of N point numbers at coordinates "$x,$y".  If
278           there's nothing at "$x,$y" then return an empty list.
279
280               my @n_list = $path->xy_to_n(20,20);
281
282           Most paths have just a single N for a given X,Y but some such as
283           "DragonCurve" and "TerdragonCurve" have multiple N's and this
284           method returns all of them.
285
286           Currently all paths have a finite number of N at a given location.
287           It's unspecified what might happen for an infinite list, if that
288           ever occurred.
289
290       "@n_list = $path->n_to_n_list ($n)"
291           Return a list of all N point numbers at the location of $n.  This
292           is equivalent to "xy_to_n_list(n_to_xy($n))".
293
294           The return list includes $n itself.  If there is no $n in the path
295           then return an empty list.
296
297           This function is convenient for paths like "DragonCurve" or
298           "TerdragonCurve" with double or triple visited points so an N may
299           have other N at the same location.
300
301       "$bool = $path->xy_is_visited ($x,$y)"
302           Return true if "$x,$y" is visited.  This is equivalent to
303
304               defined($path->xy_to_n($x,$y))
305
306           Some paths cover the plane and for them "xy_is_visited()" is always
307           true.  For others it might be less work to test a point than to
308           calculate its $n.
309
310       "$n = $path->xyxy_to_n($x1,$y1, $x2,$y2)"
311       "$n = $path->xyxy_to_n_either($x1,$y1, $x2,$y2)"
312       "@n_list = $path->xyxy_to_n_list($x1,$y1, $x2,$y2)"
313       "@n_list = $path->xyxy_to_n_list_either($x1,$y1, $x2,$y2)"
314           Return <$n> which goes from "$x1,$y1" to "$x2,$y2".  <$n> is at
315           "$x1,$y1" and "$n+1" is at "$x2,$y2", or for a multi-arm path
316           "$n+$arms", so a step along the same arm.  If there's no such $n
317           then return "undef".
318
319           The "either()" forms allow <$n> in either direction, so "$x1,$y1"
320           to "$x2,$y2" or the other way "$x2,$y2" to "$x1,$y1".
321
322           The "n_list()" forms return a list of all $n going between
323           "$x1,$y1" and "$x2,$y2".  For example in "Math::PlanePath::CCurve"
324           some segments are traversed twice, once in each direction.
325
326           The possible N values at each X,Y are determined the same way as
327           for "xy_to_n()".
328
329       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
330           Return a range of N values covering the rectangle with corners at
331           $x1,$y1 and $x2,$y2.  The range is inclusive.  For example,
332
333                my ($n_lo, $n_hi) = $path->rect_to_n_range (-5,-5, 5,5);
334                foreach my $n ($n_lo .. $n_hi) {
335                  my ($x, $y) = $path->n_to_xy($n) or next;
336                  print "$n  $x,$y";
337                }
338
339           The return might be an over-estimate of the N range required to
340           cover the rectangle.  Even if the range is exact, the nature of the
341           path may mean many points between $n_lo and $n_hi are outside the
342           rectangle.  But the range is at least a lower and upper bound on
343           the N values which occur in the rectangle.  Classes which guarantee
344           an exact lo/hi say so in their docs.
345
346           $n_hi is usually no more than an extra partial row, revolution, or
347           self-similar level.  $n_lo might be merely the starting
348           "$path->n_start()", which is fine if the origin is in the desired
349           rectangle but away from the origin could actually start higher.
350
351           $x1,$y1 and $x2,$y2 can be fractional.  If they partly overlap some
352           N figures then those N's are included in the return.
353
354           If there's no points in the rectangle then the return can be a
355           "crossed" range like "$n_lo=1", "$n_hi=0" (which makes a "foreach"
356           do no loops).  But "rect_to_n_range()" may not always notice
357           there's no points in the rectangle and might instead return an
358           over-estimate.
359
360   Descriptive Methods
361       "$n = $path->n_start()"
362           Return the first N in the path.  The start is usually either 0 or 1
363           according to what is most natural for the path.  Some paths have an
364           "n_start" parameter to control the numbering.
365
366           Some classes have secret dubious undocumented support for N values
367           below this start (zero or negative), but "n_start()" is the
368           intended starting point.
369
370       "$f = $path->n_frac_discontinuity()"
371           Return the fraction of N at which there may be discontinuities in
372           the path.  For example if there's a jump in the coordinates between
373           N=7.4999 and N=7.5 then the returned $f is 0.5.  Or $f is 0 if
374           there's a discontinuity between 6.999 and 7.0.
375
376           If there's no discontinuities in the path then the return is
377           "undef".  That means for example fractions between N=7 to N=8 give
378           smooth continuous X,Y values (of some kind).
379
380           This is mainly of interest for drawing line segments between N
381           points.  If there's discontinuities then the idea is to draw from
382           say N=7.0 to N=7.499 and then another line from N=7.5 to N=8.
383
384       "$arms = $path->arms_count()"
385           Return the number of arms in a "multi-arm" path.
386
387           For example in "SquareArms" this is 4 and each arm increments in
388           turn, so the first arm is N=1,5,9,13,etc starting from
389           "$path->n_start()" and incrementing by 4 each time.
390
391       "$bool = $path->x_negative()"
392       "$bool = $path->y_negative()"
393           Return true if the path extends into negative X coordinates and/or
394           negative Y coordinates respectively.
395
396       "$bool = Math::PlanePath::Foo->class_x_negative()"
397       "$bool = Math::PlanePath::Foo->class_y_negative()"
398       "$bool = $path->class_x_negative()"
399       "$bool = $path->class_y_negative()"
400           Return true if any paths made by this class extend into negative X
401           coordinates and/or negative Y coordinates, respectively.
402
403           For some classes the X or Y extent may depend on parameter values.
404
405       "$n = $path->x_negative_at_n()"
406       "$n = $path->y_negative_at_n()"
407           Return the integer N where X or Y respectively first goes negative,
408           or return "undef" if it does not go negative ("x_negative()" or
409           "y_negative()" respectively is false).
410
411       "$x = $path->x_minimum()"
412       "$y = $path->y_minimum()"
413       "$x = $path->x_maximum()"
414       "$y = $path->y_maximum()"
415           Return the minimum or maximum of the X or Y coordinate reached by
416           integer N values in the path.  If there's no minimum or maximum
417           then return "undef".
418
419       "$dx = $path->dx_minimum()"
420       "$dx = $path->dx_maximum()"
421       "$dy = $path->dy_minimum()"
422       "$dy = $path->dy_maximum()"
423           Return the minimum or maximum change dX, dY occurring in the path
424           for integer N to N+1.  For a multi-arm path the change is N to
425           N+arms so it's the change along the same arm.
426
427           Various paths which go by rows have non-decreasing Y.  For them
428           "dy_minimum()" is 0.
429
430       "$adx = $path->absdx_minimum()"
431       "$adx = $path->absdx_maximum()"
432       "$ady = $path->absdy_minimum()"
433       "$ady = $path->absdy_maximum()"
434           Return the minimum or maximum change abs(dX) or abs(dY) occurring
435           in the path for integer N to N+1.  For a multi-arm path, the change
436           is N to N+arms so it's the change along the same arm.
437
438           "absdx_maximum()" is simply max(dXmax,-dXmin), the biggest change
439           either positive or negative.  "absdy_maximum()" similarly.
440
441           "absdx_minimum()" is 0 if dX=0 occurs anywhere in the path, which
442           means any vertical step.  If X always changes then
443           "absdx_minimum()" will be something bigger than 0.
444           "absdy_minimum()" likewise 0 if any horizontal dY=0, or bigger if Y
445           always changes.
446
447       "$sum = $path->sumxy_minimum()"
448       "$sum = $path->sumxy_maximum()"
449           Return the minimum or maximum values taken by coordinate sum X+Y
450           reached by integer N values in the path.  If there's no minimum or
451           maximum then return "undef".
452
453           S=X+Y is an anti-diagonal.  A path which is always right and above
454           some anti-diagonal has a minimum.  Some paths might be entirely
455           left and below and so have a maximum, though that's unusual.
456
457                                     \        Path always above
458                                      \ |     has minimum S=X+Y
459                                       \|
460                                     ---o----
461                 Path always below      |\
462                 has maximum S=X+Y      | \
463                                           \  S=X+Y
464
465       "$sum = $path->sumabsxy_minimum()"
466       "$sum = $path->sumabsxy_maximum()"
467           Return the minimum or maximum values taken by coordinate sum
468           abs(X)+abs(Y) reached by integer N values in the path.  A minimum
469           always exists but if there's no maximum then return "undef".
470
471           SumAbs=abs(X)+abs(Y) is sometimes called the "taxi-cab" or
472           "Manhattan" distance, being how far to travel through a square-grid
473           city to get to X,Y.  "sumabsxy_minimum()" is then how close to the
474           origin the path extends.
475
476           SumAbs can also be interpreted geometrically as numbering the anti-
477           diagonals of the quadrant containing X,Y, which is equivalent to
478           asking which diamond shape X,Y falls on.  "sumabsxy_minimum()" is
479           then the smallest such diamond reached by the path.
480
481                    |
482                   /|\       SumAbs = which diamond X,Y falls on
483                  / | \
484                 /  |  \
485               -----o-----
486                 \  |  /
487                  \ | /
488                   \|/
489                    |
490
491       "$diffxy = $path->diffxy_minimum()"
492       "$diffxy = $path->diffxy_maximum()"
493           Return the minimum or maximum values taken by coordinate difference
494           X-Y reached by integer N values in the path.  If there's no minimum
495           or maximum then return "undef".
496
497           D=X-Y is a leading diagonal.  A path which is always right and
498           below such a diagonal has a minimum, for example "HypotOctant".  A
499           path which is always left and above some diagonal has a maximum
500           D=X-Y.  For example various wedge-like paths such as "PyramidRows"
501           in its default step=2, and "upper octant" paths have a maximum.
502
503                                            /   D=X-Y
504                   Path always below     | /
505                   has maximum D=X-Y     |/
506                                      ---o----
507                                        /|
508                                       / |      Path always above
509                                      /         has minimum D=X-Y
510
511       "$absdiffxy = $path->absdiffxy_minimum()"
512       "$absdiffxy = $path->absdiffxy_maximum()"
513           Return the minimum or maximum values taken by abs(X-Y) for integer
514           N in the path.  The minimum is 0 or more.  If there's maximum then
515           return "undef".
516
517           abs(X-Y) can be interpreted geometrically as the distance away from
518           the X=Y diagonal and measured at right-angles to that line.
519
520                d=abs(X-Y)  X=Y line
521                      ^    /
522                       \  /
523                        \/
524                        /\
525                       /  \
526                      /    \
527                     o      v
528                    /         d=abs(X-Y)
529
530           Paths which visit the X=Y line (or approach it as an infimum) have
531           "absdiffxy_minimum() = 0".  Otherwise "absdiffxy_minimum()" is how
532           close they come to the line.
533
534           If the path is entirely below the X=Y line so X>=Y then X-Y>=0 and
535           "absdiffxy_minimum()" is the same as "diffxy_minimum()".  If the
536           path is entirely below the X=Y line then "absdiffxy_minimum()" is
537           "- diffxy_maximum()".
538
539       "$dsumxy = $path->dsumxy_minimum()"
540       "$dsumxy = $path->dsumxy_maximum()"
541       "$ddiffxy = $path->ddiffxy_minimum()"
542       "$ddiffxy = $path->ddiffxy_maximum()"
543           Return the minimum or maximum change dSum or dDiffXY occurring in
544           the path for integer N to N+1.  For a multi-arm path, the change is
545           N to N+arms so it's the change along the same arm.
546
547       "$rsquared = $path->rsquared_minimum()"
548       "$rsquared = $path->rsquared_maximum()"
549           Return the minimum or maximum Rsquared = X^2+Y^2 reached by integer
550           N values in the path.  If there's no minimum or maximum then return
551           "undef".
552
553           Rsquared is always >= 0 so it always has a minimum.  The minimum
554           will be more than 0 for paths which don't include the origin
555           X=0,Y=0.
556
557           RSquared generally has no maximum since the paths usually extend
558           infinitely in some direction.  "rsquared_maximum()" returns "undef"
559           in that case.
560
561       "($dx,$dy) = $path->dir_minimum_dxdy()"
562       "($dx,$dy) = $path->dir_maximum_dxdy()"
563           Return a vector which is the minimum or maximum angle taken by a
564           step integer N to N+1, or for a multi-arm path N to N+arms, so it's
565           the change along the same arm.  Directions are reckoned anti-
566           clockwise around from the X axis.
567
568                             |  *  dX=2,dY=2
569               dX=-1,dY=1  * | /
570                            \|/
571                       ------+----*  dX=1,dY=0
572                             |
573                             |
574                             * dX=0,dY=-1
575
576           A path which is always goes N,S,E,W such as the "SquareSpiral" has
577           minimum East dX=1,dY=0 and maximum South dX=0,dY=-1.
578
579           Paths which go diagonally may have different limits.  For example
580           the "KnightSpiral" goes in 2x1 steps and so has minimum East-North-
581           East dX=2,dY=1 and maximum East-South-East dX=2,dY=-1.
582
583           If the path has directions approaching 360 degrees then
584           "dir_maximum_dxdy()" is 0,0 which should be taken to mean a full
585           circle as a supremum.  For example "MultipleRings".
586
587           If the path only ever goes East then the maximum is East dX=1,dY=0,
588           and the minimum the same.  This isn't particularly interesting, but
589           arises for example in the "Columns" path height=0.
590
591       "$bool = $path->turn_any_left()"
592       "$bool = $path->turn_any_right()"
593       "$bool = $path->turn_any_straight()"
594           Return true if the path turns left, right, or straight (which
595           includes 180deg reverse) at any integer N.
596
597                           N+1 left
598
599               N-1  --------  N  -->   N+1 straight
600
601                           N+1 right
602
603           A line from N-1 to N is a current direction and the turn at N is
604           then whether point N+1 is to the left or right of that line.
605           Directly along the line is straight, and so is anything directly
606           behind as a reverse.  This is the turn style of
607           Math::NumSeq::PlanePathTurn.
608
609       "$str = $path->figure()"
610           Return a string name of the figure (shape) intended to be drawn at
611           each $n position.  This is currently either
612
613               "square"     side 1 centred on $x,$y
614               "circle"     diameter 1 centred on $x,$y
615
616           Of course this is only a suggestion since PlanePath doesn't draw
617           anything itself.  A figure like a diamond for instance can look
618           good too.
619
620   Tree Methods
621       Some paths are structured like a tree where each N has a parent and
622       possibly some children.
623
624                        123
625                       / | \
626                    456 999 458
627                   /        / \
628                 1000    1001 1005
629
630       The N numbering and any relation to X,Y positions varies among the
631       paths.  Some are numbered by rows in breadth-first style and some have
632       children with X,Y positions adjacent to their parent, but that
633       shouldn't be assumed, only that there's a parent-child relation down
634       from some set of root nodes.
635
636       "$bool = $path->is_tree()"
637           Return true if $path is a tree.
638
639           The various tree methods have empty or "undef" returns on non-tree
640           paths.  Often it's enough to check for that from a desired method
641           rather than a separate "is_tree()" check.
642
643       "@n_children = $path->tree_n_children($n)"
644           Return a list of N values which are the child nodes of $n, or
645           return an empty list if $n has no children.
646
647           There could be no children either because $path is not a tree or
648           because there's no children at a particular $n.
649
650       "$num = $path->tree_n_num_children($n)"
651           Return the number of children of $n, or 0 if $n has no children, or
652           "undef" if "$n < n_start()" (ie. before the start of the path).
653
654           If the tree is considered as a directed graph then this is the
655           "out-degree" of $n.
656
657       "$n_parent = $path->tree_n_parent($n)"
658           Return the parent node of $n, or "undef" if it has no parent.
659
660           There is no parent at the root node of the tree, or one of multiple
661           roots, or if $path is not a tree.
662
663       "$n_root = $path->tree_n_root ($n)"
664           Return the N which is the root node of $n.  This is the top of the
665           tree as would be found by following "tree_n_parent()" repeatedly.
666
667           The return is "undef" if there's no $n point or if $path is not a
668           tree.
669
670       "$depth = $path->tree_n_to_depth($n)"
671           Return the depth of node $n, or "undef" if there's no point $n.
672           The top of the tree is depth=0, then its children are depth=1, etc.
673
674           The depth is a count of how many parent, grandparent, etc, levels
675           are above $n, ie. until reaching "tree_n_to_parent()" returning
676           "undef".  For non-tree paths "tree_n_to_parent()" is always "undef"
677           and "tree_n_to_depth()" is always 0.
678
679       "$n_lo = $path->tree_depth_to_n($depth)"
680       "$n_hi = $path->tree_depth_to_n_end($depth)"
681       "($n_lo, $n_hi) = $path->tree_depth_to_n_range ($depth)"
682           Return the first or last N, or both those N, for tree level $depth
683           in the path.  If there's no such $depth or if $path is not a tree
684           then return "undef", or for "tree_depth_to_n_range()" return an
685           empty list.
686
687           The points $n_lo through $n_hi might not necessarily all be at
688           $depth.  It's possible for depths to be interleaved or intermixed
689           in the point numbering.  But many paths are breadth-wise successive
690           rows and for them $n_lo to $n_hi inclusive is all $depth.
691
692           $n_hi can only exist if the row has a finite number of points.
693           That's true of all current paths, but perhaps allowance ought to be
694           made for $n_hi as "undef" or some such if there is no maximum N for
695           some row.
696
697       "$num = $path->tree_depth_to_width ($depth)"
698           Return the number of points at $depth in the tree.  If there's no
699           such $depth or $path is not a tree then return "undef".
700
701       "$height = $path->tree_n_to_subheight($n)"
702           Return the height of the sub-tree starting at $n, or "undef" if
703           infinite.  The height of a tree is the longest distance down to a
704           leaf node.  For example,
705
706               ...                      N     subheight
707                 \                     ---    ---------
708                  6    7   8            0       undef
709                   \    \ /             1       undef
710                    3    4   5          2         2
711                     \    \ /           3       undef
712                      1    2            4         1
713                       \  /             5         0
714                         0             ...
715
716           At N=0 and all of the left side the tree continues infinitely so
717           the sub-height there is "undef" for infinite.  For N=2 the sub-
718           height is 2 because the longest path down is 2 levels (to N=7 or
719           N=8).  For a leaf node such as N,=5 the sub-height is 0.
720
721   Tree Descriptive Methods
722       "$num = $path->tree_num_roots()"
723           Return the number of root nodes in $path.  If $path is not a tree
724           then return 0.  Many tree paths have a single root and for them the
725           return is 1.
726
727       "@n_list = $path->tree_root_n_list()"
728           Return a list of the N values which are the root nodes in $path.
729           If $path is not a tree then this is an empty list.  There are
730           "tree_num_roots()" many return values.
731
732       "$num = $path->tree_num_children_minimum()"
733       "$num = $path->tree_num_children_maximum()"
734       "@nums = $path->tree_num_children_list()"
735           Return the possible number of children of the nodes of $path,
736           either the minimum, the maximum, or a list of all possible numbers
737           of children.
738
739           For "tree_num_children_list()" the list of values is in increasing
740           order, so the first value is "tree_num_children_minimum()" and the
741           last is "tree_num_children_maximum()".
742
743       "$bool = $path->tree_any_leaf()"
744           Return true if there are any leaf nodes in the tree, meaning any N
745           for which "tree_n_num_children()" is 0.
746
747           This is the same as "tree_num_children_minimum()==0" since if
748           NumChildren=0 occurs then there are leaf nodes.
749
750           Some trees may have no leaf nodes, for example in the complete
751           binary tree of "RationalsTree" every node always has 2 children.
752
753   Level Methods
754       "level = $path->n_to_level($n)"
755           Return the replication level containing $n.  The first level is 0.
756
757       "($n_lo,$n_hi) = $path->level_to_n_range($level)"
758           Return the range of N values, inclusive, which comprise a self-
759           similar replication level in $path.  If $path has no notion of such
760           levels then return an empty list.
761
762               my ($n_lo, $n_hi) = $path->level_to_n_range(6)
763                 or print "no levels in this path";
764
765           For example the "DragonCurve" has levels running 0 to "2**$level",
766           or the "HilbertCurve" is 0 to "4**$level - 1".  Most levels are
767           powers like this.  A power "2**$level" is a "vertex" style whereas
768           "2**$level - 1" is a "centre" style.  The difference is generally
769           whether the X,Y points represent vertices of the object's segments
770           as opposed to centres or midpoints.
771
772   Parameter Methods
773       "$aref = Math::PlanePath::Foo->parameter_info_array()"
774       "@list = Math::PlanePath::Foo->parameter_info_list()"
775           Return an arrayref of list describing the parameters taken by a
776           given class.  This meant to help making widgets etc for user
777           interaction in a GUI.  Each element is a hashref
778
779               {
780                 name        =>    parameter key arg for new()
781                 share_key   =>    string, or undef
782                 description =>    human readable string
783                 type        =>    string "integer","boolean","enum" etc
784                 default     =>    value
785                 minimum     =>    number, or undef
786                 maximum     =>    number, or undef
787                 width       =>    integer, suggested display size
788                 choices     =>    for enum, an arrayref
789               }
790
791           "type" is a string, one of
792
793               "integer"
794               "enum"
795               "boolean"
796               "string"
797               "filename"
798
799           "filename" is separate from "string" since it might require subtly
800           different handling to reach Perl as a byte string, whereas a
801           "string" type might in principle take Perl wide chars.
802
803           For "enum" the "choices" field is the possible values, such as
804
805               { name => "flavour",
806                 type => "enum",
807                 choices => ["strawberry","chocolate"],
808               }
809
810           "minimum" and/or "maximum" are omitted if there's no hard limit on
811           the parameter.
812
813           "share_key" is designed to indicate when parameters from different
814           "PlanePath" classes can done by a single control widget in a GUI
815           etc.  Normally the "name" is enough, but when the same name has
816           slightly different meanings in different classes a "share_key"
817           allows the same meanings to be matched up.
818
819       "$hashref = Math::PlanePath::Foo->parameter_info_hash()"
820           Return a hashref mapping parameter names "$info->{'name'}" to their
821           $info records.
822
823               { wider => { name => "wider",
824                            type => "integer",
825                            ...
826                          },
827               }
828

GENERAL CHARACTERISTICS

830       The classes are mostly based on integer $n positions and those designed
831       for a square grid turn an integer $n into integer "$x,$y".  Usually
832       they give in-between positions for fractional $n too.  Classes not on a
833       square grid but instead giving fractional X,Y such as "SacksSpiral" and
834       "VogelFloret" are designed for a unit circle at each $n but they too
835       can give in-between positions on request.
836
837       All X,Y positions are calculated by separate "n_to_xy()" calls.  To
838       follow a path use successive $n values starting from
839       "$path->n_start()".
840
841           foreach my $n ($path->n_start .. 100) {
842             my ($x,$y) = $path->n_to_xy($n);
843             print "$n  $x,$y\n";
844           }
845
846       The separate "n_to_xy()" calls were motivated by plotting just some N
847       points of a path, such as just the primes or the perfect squares.
848       Successive positions in paths could perhaps be done more efficiently in
849       an iterator style.  Paths with a quadratic "step" are not much worse
850       than a "sqrt()" to break N into a segment and offset, but the self-
851       similar paths which chop N into digits of some radix could increment
852       instead of recalculate.
853
854       If interested only in a particular rectangle or similar region then
855       iterating has the disadvantage that it may stray outside the target
856       region for a long time, making an iterator much less useful than it
857       seems.  For wild paths it can be better to apply "xy_to_n()" by rows or
858       similar across the desired region.
859
860       Math::NumSeq::PlanePathCoord etc offer the PlanePath coordinates,
861       directions, turns, etc as sequences.  The iterator forms there simply
862       make repeated calls to "n_to_xy()" etc.
863
864   Scaling and Orientation
865       The paths generally make a first move to the right and go anti-
866       clockwise around from the X axis, unless there's some more natural
867       orientation.  Anti-clockwise is the usual direction for mathematical
868       spirals.
869
870       There's no parameters for scaling, offset or reflection as those things
871       are thought better left to a general coordinate transformer, for
872       example to expand or invert for display.  Some easy transformations can
873       be had just from the X,Y with
874
875           -X,Y        flip horizontally (mirror image)
876           X,-Y        flip vertically (across the X axis)
877
878           -Y,X        rotate +90 degrees  (anti-clockwise)
879           Y,-X        rotate -90 degrees  (clockwise)
880           -X,-Y       rotate 180 degrees
881
882       Flip vertically makes spirals go clockwise instead of anti-clockwise,
883       or a flip horizontally the same but starting on the left at the
884       negative X axis.  See "Triangular Lattice" below for 60 degree
885       rotations of the triangular grid paths too.
886
887       The Rows and Columns paths are exceptions to the rule of not having
888       rotated versions of paths.  They began as ways to pass in width and
889       height as generic parameters and let the path use the one or the other.
890
891       For scaling and shifting see for example Transform::Canvas, and to
892       rotate as well see Geometry::AffineTransform.
893
894   Loop Step
895       The paths can be characterized by how much longer each loop or
896       repetition is than the preceding one.  For example each cycle around
897       the "SquareSpiral" is 8 more N points than the preceding.
898
899             Step        Path
900             ----        ----
901               0       Rows, Columns (fixed widths)
902               1       Diagonals
903              2/2      DiagonalsOctant (2 rows for +2)
904               2       SacksSpiral, Corner, CornerAlternating,
905                         PyramidSides, PyramidRows (default)
906               4       DiamondSpiral, AztecDiamondRings, Staircase
907              4/2      CellularRule54, CellularRule57,
908                         DiagonalsAlternating (2 rows for +4)
909               5       PentSpiral, PentSpiralSkewed
910              5.65     PixelRings (average about 4*sqrt(2))
911               6       HexSpiral, HexSpiralSkewed, MPeaks,
912                         MultipleRings (default)
913              6/2      CellularRule190 (2 rows for +6)
914              6.28     ArchimedeanChords (approaching 2*pi),
915                         FilledRings (average 2*pi)
916               7       HeptSpiralSkewed
917               8       SquareSpiral, PyramidSpiral
918             16/2      StaircaseAlternating (up and back for +16)
919               9       TriangleSpiral, TriangleSpiralSkewed
920              12       AnvilSpiral
921              16       OctagramSpiral, ToothpickSpiral
922             19.74     TheodorusSpiral (approaching 2*pi^2)
923             32/4      KnightSpiral (4 loops 2-wide for +32)
924              64       DiamondArms (each arm)
925              72       GreekKeySpiral
926             128       SquareArms (each arm)
927            128/4      CretanLabyrinth (4 loops for +128)
928             216       HexArms (each arm)
929
930           totient     CoprimeColumns, DiagonalRationals
931           numdivisors DivisibleColumns
932           various     CellularRule
933
934           parameter   MultipleRings, PyramidRows
935
936       The step determines which quadratic number sequences make straight
937       lines.  For example the gap between successive perfect squares
938       increases by 2 each time (4 to 9 is +5, 9 to 16 is +7, 16 to 25 is +9,
939       etc), so the perfect squares make a straight line in the paths of step
940       2.
941
942       In general straight lines on stepped paths are quadratics
943
944          N = a*k^2 + b*k + c    where a=step/2
945
946       The polygonal numbers are like this, with the (step+2)-gonal numbers
947       making a straight line on a "step" path.  For example the 7-gonals
948       (heptagonals) are 5/2*k^2-3/2*k and make a straight line on the step=5
949       "PentSpiral".  Or the 8-gonal octagonal numbers 6/2*k^2-4/2*k on the
950       step=6 "HexSpiral".
951
952       There are various interesting properties of primes in quadratic
953       progressions.  Some quadratics seem to have more primes than others.
954       For example see "Lucky Numbers of Euler" in
955       Math::PlanePath::PyramidSides.  Many quadratics have no primes at all,
956       or none above a certain point, either trivially if always a multiple of
957       2 etc, or by a more sophisticated reasoning.  See "Step 3 Pentagonals"
958       in Math::PlanePath::PyramidRows for a factorization on the roots making
959       a no-primes gap.
960
961       A 4*step path splits a straight line in two, so for example the perfect
962       squares are a straight line on the step=2 "Corner" path, and then on
963       the step=8 "SquareSpiral" they instead fall on two lines (lower left
964       and upper right).  In the bigger step there's one line of the even
965       squares (2k)^2 == 4*k^2 and another of the odd squares (2k+1)^2.  The
966       gap between successive even squares increases by 8 each time and
967       likewise between odd squares.
968
969   Self-Similar Powers
970       The self-similar patterns such as "PeanoCurve" generally have a base
971       pattern which repeats at powers N=base^level or squares
972       N=(base*base)^level.  Or some multiple or relationship to such a power
973       for things like "KochPeaks" and "GosperIslands".
974
975           Base          Path
976           ----          ----
977             2         HilbertCurve, HilbertSides, HilbertSpiral,
978                         ZOrderCurve (default), GrayCode (default),
979                         BetaOmega, AR2W2Curve, HIndexing,
980                         ImaginaryBase (default), ImaginaryHalf (default),
981                         SierpinskiCurve, SierpinskiCurveStair,
982                         CubicBase (default) CornerReplicate,
983                         ComplexMinus (default), ComplexPlus (default),
984                         ComplexRevolving, DragonCurve, DragonRounded,
985                         DragonMidpoint, AlternatePaper, AlternatePaperMidpoint,
986                         CCurve, DigitGroups (default), PowerArray (default)
987             3         PeanoCurve (default), PeanoDiagonals (default),
988                         WunderlichSerpentine (default),WunderlichMeander,
989                         KochelCurve, GosperIslands, GosperSide
990                         SierpinskiTriangle, SierpinskiArrowhead,
991                         SierpinskiArrowheadCentres,
992                         TerdragonCurve, TerdragonRounded, TerdragonMidpoint,
993                         AlternateTerdragon,
994                         UlamWarburton, UlamWarburtonQuarter (each level)
995             4         KochCurve, KochPeaks, KochSnowflakes, KochSquareflakes,
996                         LTiling,
997             5         QuintetCurve, QuintetCentres, QuintetReplicate,
998                         DekkingCurve, DekkingCentres, CincoCurve,
999                         R5DragonCurve, R5DragonMidpoint
1000             7         Flowsnake, FlowsnakeCentres, GosperReplicate
1001             8         QuadricCurve, QuadricIslands
1002             9         SquareReplicate
1003           Fibonacci   FibonacciWordFractal, WythoffArray
1004           parameter   PeanoCurve, PeanoDiagonals, WunderlichSerpentine,
1005                         ZOrderCurve, GrayCode, ImaginaryBase, ImaginaryHalf,
1006                         CubicBase, ComplexPlus, ComplexMinus, DigitGroups,
1007                         PowerArray
1008
1009       Many number sequences plotted on these self-similar paths tend to be
1010       fairly random, or merely show the tiling or path layout rather than
1011       much about the number sequence.  Sequences related to the base can make
1012       holes or patterns picking out parts of the path.  For example numbers
1013       without a particular digit (or digits) in the relevant base show up as
1014       holes.  See for example "Power of 2 Values" in
1015       Math::PlanePath::ZOrderCurve.
1016
1017   Triangular Lattice
1018       Some paths are on triangular or "A2" lattice points like
1019
1020             *---*---*---*---*---*
1021            / \ / \ / \ / \ / \ /
1022           *---*---*---*---*---*
1023            \ / \ / \ / \ / \ / \
1024             *---*---*---*---*---*
1025            / \ / \ / \ / \ / \ /
1026           *---*---*---*---*---*
1027            \ / \ / \ / \ / \ / \
1028             *---*---*---*---*---*
1029            / \ / \ / \ / \ / \ /
1030           *---*---*---*---*---*
1031
1032       This is done in integer X,Y on a square grid by using every second
1033       square and offsetting alternate rows.  This means sum X+Y even, ie. X,Y
1034       either both even or both odd, not of opposite parity.
1035
1036           . * . * . * . * . * . *
1037           * . * . * . * . * . * .
1038           . * . * . * . * . * . *
1039           * . * . * . * . * . * .
1040           . * . * . * . * . * . *
1041           * . * . * . * . * . * .
1042
1043       The X axis the and diagonals X=Y and X=-Y divide the plane into six
1044       equal parts in this grid.
1045
1046              X=-Y     X=Y
1047                \     /
1048                 \   /
1049                  \ /
1050           ----------------- X=0
1051                  / \
1052                 /   \
1053                /     \
1054
1055       The diagonal X=3*Y is the middle of the first sixth, representing a
1056       twelfth of the plane.
1057
1058       The resulting triangles are flatter than they should be.  The triangle
1059       base is width=2 and top is height=1, whereas it would be height=sqrt(3)
1060       for an equilateral triangle.  That sqrt(3) factor can be applied if
1061       desired,
1062
1063           X, Y*sqrt(3)          side length 2
1064
1065           X/2, Y*sqrt(3)/2      side length 1
1066
1067       Integer Y values have the advantage of fitting pixels on the usual kind
1068       of raster computer screen, and not losing precision in floating point
1069       results.
1070
1071       If doing a general-purpose coordinate rotation then be sure to apply
1072       the sqrt(3) scale factor before rotating or the result will be skewed.
1073       60 degree rotations can be made within the integer X,Y coordinates
1074       directly as follows, all giving integer X,Y results.
1075
1076           ( X-3Y)/2, ( X+Y)/2     rotate +60   (anti-clockwise)
1077           ( X+3Y)/2, (-X+Y)/2     rotate -60   (clockwise)
1078           (-X-3Y)/2, ( X-Y)/2     rotate +120
1079           (-X+3Y)/2, (-X-Y)/2     rotate -120
1080           -X,-Y                   rotate 180
1081
1082           (X+3Y)/2, (X-Y)/2       mirror across the X=3*Y twelfth (30deg)
1083
1084       The sqrt(3) factor can be worked into a hypotenuse radial distance
1085       calculation as follows if comparing distances from the origin.
1086
1087           hypot = sqrt(X*X + 3*Y*Y)
1088
1089       See for instance "TriangularHypot" which is triangular points ordered
1090       by this radial distance.
1091

FORMULAS

1093       The formulas section in the POD of each class describes some of the
1094       calculations.  This might be of interest even if the code is not.
1095
1096   Triangular Calculations
1097       For a triangular lattice, the rotation formulas above allow
1098       calculations to be done in the rectangular X,Y coordinates which are
1099       the inputs and outputs of the PlanePath functions.  Another way is to
1100       number vertically on a 60 degree angle with coordinates i,j,
1101
1102                 ...
1103                 *   *   *      2
1104               *   *   *       1
1105             *   *   *      j=0
1106           i=0  1   2
1107
1108       These coordinates are sometimes used for hexagonal grids in board games
1109       etc.  Using this internally can simplify rotations a little,
1110
1111           -j, i+j         rotate +60   (anti-clockwise)
1112           i+j, -i         rotate -60   (clockwise)
1113           -i-j, i         rotate +120
1114           j, -i-j         rotate -120
1115           -i, -j          rotate 180
1116
1117       Conversions between i,j and the rectangular X,Y are
1118
1119           X = 2*i + j         i = (X-Y)/2
1120           Y = j               j = Y
1121
1122       A third coordinate k at a +120 degrees angle can be used too,
1123
1124            k=0  k=1 k=2
1125               *   *   *
1126                 *   *   *
1127                   *   *   *
1128                    0   1   2
1129
1130       This is redundant in that it doesn't number anything i,j alone can't
1131       already, but it has the advantage of turning rotations into just sign
1132       changes and swaps,
1133
1134           -k, i, j        rotate +60
1135           j, k, -i        rotate -60
1136           -j, -k, i       rotate +120
1137           k, -i, -j       rotate -120
1138           -i, -j, -k      rotate 180
1139
1140       The conversions between i,j,k and the rectangular X,Y are like the i,j
1141       above but with k worked in too.
1142
1143           X = 2i + j - k        i = (X-Y)/2        i = (X+Y)/2
1144           Y = j + k             j = Y         or   j = 0
1145                                 k = 0              k = Y
1146
1147   N to dX,dY -- Fractional
1148       "n_to_dxdy()" is the change from N to N+1, and is designed both for
1149       integer N and fractional N.  For fractional N it can be convenient to
1150       calculate a dX,dY at floor(N) and at floor(N)+1 and then combine the
1151       two in proportion to frac(N).
1152
1153                            int+2
1154                             |
1155                             |
1156                             N+1    \
1157                            /|       |
1158                           / |       |
1159                          /  |       | frac
1160                         /   |       |
1161                        /    |       |
1162                       /     |      /
1163              int-----N------int+1
1164           this_dX  dX,dY     next_dX
1165           this_dY            next_dY
1166
1167              |-------|------|
1168                frac   1-frac
1169
1170
1171           int = int(N)
1172           frac = N - int    0 <= frac < 1
1173
1174           this_dX,this_dY  at int
1175           next_dX,next_dY  at int+1
1176
1177           at fractional N
1178             dX = this_dX * (1-frac) + next_dX * frac
1179             dY = this_dY * (1-frac) + next_dY * frac
1180
1181       This is combination of this_dX,this_dY and next_dX,next_dY in
1182       proportion to the distances from positions N to int+1 and from int+1 to
1183       N+1.
1184
1185       The formulas can be rearranged to
1186
1187           dX = this_dX + frac*(next_dX - this_dX)
1188           dY = this_dY + frac*(next_dY - this_dY)
1189
1190       which is like dX,dY at the integer position plus fractional part of a
1191       turn or change to the next dX,dY.
1192
1193   N to dX,dY -- Self-Similar
1194       For most of the self-similar paths such as "HilbertCurve", the change
1195       dX,dY is determined by following the state table transitions down
1196       through either all digits of N, or to the last non-9 digit, ie. drop
1197       any low digits equal to radix-1.
1198
1199       Generally paths which are the edges of some tiling use all digits, and
1200       those which are the centres of a tiling stop at the lowest non-9.  This
1201       can be seen for example in the "DekkingCurve" using all digits, whereas
1202       its "DekkingCentres" variant stops at the lowest non-24.
1203
1204       Perhaps this all-digits vs low-non-9 would even characterize path style
1205       as edges or centres of a tiling, when a path is specified in some way
1206       that a tiling is not quite obvious.
1207

SUBCLASSING

1209       The mandatory methods for a PlanePath subclass are
1210
1211           n_to_xy()
1212           xy_to_n()
1213           xy_to_n_list()     if multiple N's map to an X,Y
1214           rect_to_n_range()
1215
1216       It sometimes happens that one of "n_to_xy()" or "xy_to_n()" is easier
1217       than the other but both should be implemented.
1218
1219       "n_to_xy()" should do something sensible on fractional N.  The
1220       suggestion is to make it an X,Y proportionally between integer N
1221       positions.  It could be along a straight line or an arc as best suits
1222       the path.  A straight line can be done simply by two calculations of
1223       the surrounding integer points, until it's clear how to work the
1224       fraction into the code directly.
1225
1226       "xy_to_n_list()" has a base implementation calling plain "xy_to_n()" to
1227       give a single N at X,Y.  If a path has multiple Ns at an X,Y (eg.
1228       "DragonCurve") then it must implement "xy_to_n_list()" to return all
1229       those Ns, and must also implement a plain "xy_to_n()" returning the
1230       first of them.
1231
1232       "rect_to_n_range()" can initially be any convenient over-estimate.  It
1233       should give N big enough that from there onwards all points are sure to
1234       be beyond the given X,Y rectangle.
1235
1236       The following descriptive methods have base implementations
1237
1238           n_start()           1
1239           class_x_negative()  \ 1, so whole plane
1240           class_y_negative()  /
1241           x_negative()        calls class_x_negative()
1242           y_negative()        calls class_x_negative()
1243           x_negative_at_n()   undef \ as for no negatives
1244           y_negative_at_n()   undef /
1245
1246       The base "n_start()" starts at N=1.  Paths which treat N as digits of
1247       some radix or where there's self-similar replication are often best
1248       started from N=0 instead since doing so puts nice powers-of-2 etc on
1249       the axes or diagonals.
1250
1251           use constant n_start => 0;    # digit or replication style
1252
1253       Paths which use only parts of the plane should define
1254       "class_x_negative()" and/or "class_y_negative()" to false.  For example
1255       if only the first quadrant X>=0,Y>=0 then
1256
1257           use constant class_x_negative => 0;
1258           use constant class_y_negative => 0;
1259
1260       If negativeness varies with path parameters then "x_negative()" and/or
1261       "y_negative()" follow those parameters and the "class_()" forms are
1262       whether any set of parameters ever gives negative.
1263
1264       The following methods have base implementations calling "n_to_xy()".  A
1265       subclass can implement them directly if they can be done more
1266       efficiently.
1267
1268           n_to_dxdy()           calls n_to_xy() twice
1269           n_to_rsquared()       calls n_to_xy()
1270           n_to_radius()         sqrt of n_to_rsquared()
1271
1272       "SacksSpiral" is an example of an easy "n_to_rsquared()".
1273       "TheodorusSpiral" is only slightly trickier.  Unless a path has some
1274       sort of easy X^2+Y^2 then it might as well let the base implementation
1275       call "n_to_xy()".
1276
1277       The way "n_to_dxdy()" supports fractional N can be a little tricky.
1278       One way is to calculate dX,dY on the integer N below and above and
1279       combine as described in "N to dX,dY -- Fractional".  For some paths the
1280       calculation of turn or direction at ceil(N) can be worked into a
1281       calculation of the direction at floor(N) so not much more work.
1282
1283       The following methods have base implementations calling "xy_to_n()".  A
1284       subclass might implement them directly if it can be done more
1285       efficiently.
1286
1287           xy_is_visited()          defined(xy_to_n($x,$y))
1288           xyxy_to_n()              \
1289           xyxy_to_n_either()       | calling xy_to_n_list()
1290           xyxy_to_n_list()         |
1291           xyxy_to_n_list_either()  /
1292
1293       Paths such as "SquareSpiral" which fill the plane have
1294       "xy_is_visited()" always true, so for them
1295
1296           use constant xy_is_visited => 1;
1297
1298       For a tree path the following methods are mandatory
1299
1300           tree_n_parent()
1301           tree_n_children()
1302           tree_n_to_depth()
1303           tree_depth_to_n()
1304           tree_num_children_list()
1305           tree_n_to_subheight()
1306
1307       The other tree methods have base implementations,
1308
1309       "is_tree()"
1310           Checks for "n_start()" having non-zero "tree_n_to_num_children()".
1311           Usually this suffices, expecting "n_start()" to be a root node and
1312           to have some children.
1313
1314       "tree_n_num_children()"
1315           Calls "tree_n_children()" and counts the number of return values.
1316           Many trees can count the children with less work than calculating
1317           outright, for example "RationalsTree" is simply always 2 for
1318           N>=Nstart.
1319
1320       "tree_depth_to_n_end()"
1321           Calls "tree_depth_to_n($depth+1)-1".  This assumes that the depth
1322           level ends where the next begins.  This is true for the various
1323           breadth-wise tree traversals, but anything interleaved etc will
1324           need its own implementation.
1325
1326       "tree_depth_to_n_range()"
1327           Calls "tree_depth_to_n()" and "tree_depth_to_n_end()".  For some
1328           paths the row start and end, or start and width, might be
1329           calculated together more efficiently.
1330
1331       "tree_depth_to_width()"
1332           Returns "tree_depth_to_n_end() - tree_depth_to_n() + 1".  This
1333           suits breadth-wise style paths where all points at $depth are in a
1334           contiguous block.  Any path not like that will need its own
1335           "tree_depth_to_width()".
1336
1337       "tree_num_children_minimum()", "tree_num_children_maximum()"
1338           Return the first and last values of "tree_num_children_list()" as
1339           the minimum and maximum.
1340
1341       "tree_any_leaf()"
1342           Calls "tree_num_children_minimum()".  If the minimum "num_children"
1343           is 0 then there's leaf nodes.
1344

SEE ALSO

1346       Math::PlanePath::SquareSpiral, Math::PlanePath::PyramidSpiral,
1347       Math::PlanePath::TriangleSpiral, Math::PlanePath::TriangleSpiralSkewed,
1348       Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiral,
1349       Math::PlanePath::PentSpiralSkewed, Math::PlanePath::HexSpiral,
1350       Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed,
1351       Math::PlanePath::AnvilSpiral, Math::PlanePath::OctagramSpiral,
1352       Math::PlanePath::KnightSpiral, Math::PlanePath::CretanLabyrinth
1353
1354       Math::PlanePath::HexArms, Math::PlanePath::SquareArms,
1355       Math::PlanePath::DiamondArms, Math::PlanePath::AztecDiamondRings,
1356       Math::PlanePath::GreekKeySpiral, Math::PlanePath::MPeaks
1357
1358       Math::PlanePath::SacksSpiral, Math::PlanePath::VogelFloret,
1359       Math::PlanePath::TheodorusSpiral, Math::PlanePath::ArchimedeanChords,
1360       Math::PlanePath::MultipleRings, Math::PlanePath::PixelRings,
1361       Math::PlanePath::FilledRings, Math::PlanePath::Hypot,
1362       Math::PlanePath::HypotOctant, Math::PlanePath::TriangularHypot,
1363       Math::PlanePath::PythagoreanTree
1364
1365       Math::PlanePath::PeanoCurve, Math::PlanePath::PeanoDiagonals,
1366       Math::PlanePath::WunderlichSerpentine,
1367       Math::PlanePath::WunderlichMeander, Math::PlanePath::HilbertCurve,
1368       Math::PlanePath::HilbertSides, Math::PlanePath::HilbertSpiral,
1369       Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode,
1370       Math::PlanePath::AR2W2Curve, Math::PlanePath::BetaOmega,
1371       Math::PlanePath::KochelCurve, Math::PlanePath::DekkingCurve,
1372       Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve
1373
1374       Math::PlanePath::ImaginaryBase, Math::PlanePath::ImaginaryHalf,
1375       Math::PlanePath::CubicBase, Math::PlanePath::SquareReplicate,
1376       Math::PlanePath::CornerReplicate, Math::PlanePath::LTiling,
1377       Math::PlanePath::DigitGroups, Math::PlanePath::FibonacciWordFractal
1378
1379       Math::PlanePath::Flowsnake, Math::PlanePath::FlowsnakeCentres,
1380       Math::PlanePath::GosperReplicate, Math::PlanePath::GosperIslands,
1381       Math::PlanePath::GosperSide
1382
1383       Math::PlanePath::QuintetCurve, Math::PlanePath::QuintetCentres,
1384       Math::PlanePath::QuintetReplicate
1385
1386       Math::PlanePath::KochCurve, Math::PlanePath::KochPeaks,
1387       Math::PlanePath::KochSnowflakes, Math::PlanePath::KochSquareflakes
1388
1389       Math::PlanePath::QuadricCurve, Math::PlanePath::QuadricIslands
1390
1391       Math::PlanePath::SierpinskiCurve,
1392       Math::PlanePath::SierpinskiCurveStair, Math::PlanePath::HIndexing
1393
1394       Math::PlanePath::SierpinskiTriangle,
1395       Math::PlanePath::SierpinskiArrowhead,
1396       Math::PlanePath::SierpinskiArrowheadCentres
1397
1398       Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded,
1399       Math::PlanePath::DragonMidpoint, Math::PlanePath::AlternatePaper,
1400       Math::PlanePath::AlternatePaperMidpoint,
1401       Math::PlanePath::TerdragonCurve, Math::PlanePath::TerdragonRounded,
1402       Math::PlanePath::TerdragonMidpoint,
1403       Math::PlanePath::AlternateTerdragon, Math::PlanePath::R5DragonCurve,
1404       Math::PlanePath::R5DragonMidpoint, Math::PlanePath::CCurve
1405
1406       Math::PlanePath::ComplexPlus, Math::PlanePath::ComplexMinus,
1407       Math::PlanePath::ComplexRevolving
1408
1409       Math::PlanePath::Rows, Math::PlanePath::Columns,
1410       Math::PlanePath::Diagonals, Math::PlanePath::DiagonalsAlternating,
1411       Math::PlanePath::DiagonalsOctant, Math::PlanePath::Staircase,
1412       Math::PlanePath::StaircaseAlternating, Math::PlanePath::Corner
1413       Math::PlanePath::CornerAlternating
1414
1415       Math::PlanePath::PyramidRows, Math::PlanePath::PyramidSides,
1416       Math::PlanePath::CellularRule, Math::PlanePath::CellularRule54,
1417       Math::PlanePath::CellularRule57, Math::PlanePath::CellularRule190,
1418       Math::PlanePath::UlamWarburton, Math::PlanePath::UlamWarburtonQuarter
1419
1420       Math::PlanePath::DiagonalRationals, Math::PlanePath::FactorRationals,
1421       Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree,
1422       Math::PlanePath::FractionsTree, Math::PlanePath::ChanTree,
1423       Math::PlanePath::CfracDigits, Math::PlanePath::CoprimeColumns,
1424       Math::PlanePath::DivisibleColumns, Math::PlanePath::WythoffArray,
1425       Math::PlanePath::WythoffPreliminaryTriangle,
1426       Math::PlanePath::PowerArray, Math::PlanePath::File
1427
1428       Math::PlanePath::LCornerTree, Math::PlanePath::LCornerReplicate,
1429       Math::PlanePath::ToothpickTree, Math::PlanePath::ToothpickReplicate,
1430       Math::PlanePath::ToothpickUpist, Math::PlanePath::ToothpickSpiral,
1431       Math::PlanePath::OneOfEight, Math::PlanePath::HTree
1432
1433       Math::NumSeq::PlanePathCoord, Math::NumSeq::PlanePathDelta,
1434       Math::NumSeq::PlanePathTurn, Math::NumSeq::PlanePathN
1435
1436       math-image, displaying various sequences on these paths.
1437
1438       examples/numbers.pl, to print all the paths.
1439
1440   Other Ways To Do It
1441       Math::Fractal::Curve, Math::Curve::Hilbert,
1442       Algorithm::SpatialIndex::Strategy::QuadTree
1443
1444       PerlMagick (module Image::Magick) demo scripts lsys.pl and tree.pl
1445

HOME PAGE

1447       <http://user42.tuxfamily.org/math-planepath/index.html>
1448
1449       <http://user42.tuxfamily.org/math-planepath/gallery.html>
1450

LICENSE

1452       Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
1453
1454       This file is part of Math-PlanePath.
1455
1456       Math-PlanePath is free software; you can redistribute it and/or modify
1457       it under the terms of the GNU General Public License as published by
1458       the Free Software Foundation; either version 3, or (at your option) any
1459       later version.
1460
1461       Math-PlanePath is distributed in the hope that it will be useful, but
1462       WITHOUT ANY WARRANTY; without even the implied warranty of
1463       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1464       General Public License for more details.
1465
1466       You should have received a copy of the GNU General Public License along
1467       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
1468
1469
1470
1471perl v5.36.0                      2022-07-22                Math::PlanePath(3)
Impressum