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           WunderlichSerpentine   transpose parts of PeanoCurve
57           HilbertCurve           2x2 self-similar quadrant
58           HilbertSides           2x2 self-similar quadrant segments
59           HilbertSpiral          2x2 self-similar whole-plane
60           ZOrderCurve            replicating Z shapes
61           GrayCode               Gray code splits
62           WunderlichMeander      3x3 "R" pattern quadrant
63           BetaOmega              2x2 self-similar half-plane
64           AR2W2Curve             2x2 self-similar of four parts
65           KochelCurve            3x3 self-similar of two parts
66           DekkingCurve           5x5 self-similar, edges
67           DekkingCentres         5x5 self-similar, centres
68           CincoCurve             5x5 self-similar
69
70           ImaginaryBase          replicate in four directions
71           ImaginaryHalf          half-plane replicate three directions
72           CubicBase              replicate in three directions
73           SquareReplicate        3x3 replicating squares
74           CornerReplicate        2x2 replicating "U"
75           LTiling                self-simlar L shapes
76           DigitGroups            digits grouped by zeros
77           FibonacciWordFractal   turns by Fibonacci word bits
78
79           Flowsnake              self-similar hexagonal tile traversal
80           FlowsnakeCentres         likewise but centres of hexagons
81           GosperReplicate        self-similar hexagonal tiling
82           GosperIslands          concentric island rings
83           GosperSide             single side or radial
84
85           QuintetCurve           self-similar "+" traversal
86           QuintetCentres           likewise but centres of squares
87           QuintetReplicate       self-similar "+" tiling
88
89           DragonCurve            paper folding
90           DragonRounded          paper folding rounded corners
91           DragonMidpoint         paper folding segment midpoints
92           AlternatePaper         alternating direction folding
93           AlternatePaperMidpoint alternating direction folding, midpoints
94           TerdragonCurve         ternary dragon
95           TerdragonRounded       ternary dragon rounded corners
96           TerdragonMidpoint      ternary dragon segment midpoints
97           AlternateTerdragon     alternate ternary dragon
98           R5DragonCurve          radix-5 dragon curve
99           R5DragonMidpoint       radix-5 dragon curve midpoints
100           CCurve                 "C" curve
101           ComplexPlus            base i+realpart
102           ComplexMinus           base i-realpart, including twindragon
103           ComplexRevolving       revolving base i+1
104
105           SierpinskiCurve        self-similar right-triangles
106           SierpinskiCurveStair   self-similar right-triangles, stair-step
107           HIndexing              self-similar right-triangles, squared up
108
109           KochCurve              replicating triangular notches
110           KochPeaks              two replicating notches
111           KochSnowflakes         concentric notched 3-sided rings
112           KochSquareflakes       concentric notched 4-sided rings
113           QuadricCurve           eight segment zig-zag
114           QuadricIslands           rings of those zig-zags
115           SierpinskiTriangle     self-similar triangle by rows
116           SierpinskiArrowhead    self-similar triangle connectedly
117           SierpinskiArrowheadCentres  likewise but centres of triangles
118
119           Rows                   fixed-width rows
120           Columns                fixed-height columns
121           Diagonals              diagonals between X and Y axes
122           DiagonalsAlternating   diagonals Y to X and back again
123           DiagonalsOctant        diagonals between Y axis and X=Y centre
124           Staircase              stairs down from the Y to X axes
125           StaircaseAlternating   stairs Y to X and back again
126           Corner                 expanding stripes around a corner
127           PyramidRows            expanding stacked rows pyramid
128           PyramidSides           along the sides of a 45-degree pyramid
129           CellularRule           cellular automaton by rule number
130           CellularRule54         cellular automaton rows pattern
131           CellularRule57         cellular automaton (rule 99 mirror too)
132           CellularRule190        cellular automaton (rule 246 mirror too)
133           UlamWarburton          cellular automaton diamonds
134           UlamWarburtonQuarter   cellular automaton quarter-plane
135
136           DiagonalRationals      rationals X/Y by diagonals
137           FactorRationals        rationals X/Y by prime factorization
138           GcdRationals           rationals X/Y by rows with GCD integer
139           RationalsTree          rationals X/Y by tree
140           FractionsTree          fractions 0<X/Y<1 by tree
141           ChanTree               rationals X/Y multi-child tree
142           CfracDigits            continued fraction 0<X/Y<1 by digits
143           CoprimeColumns         coprime X,Y
144           DivisibleColumns       X divisible by Y
145           WythoffArray           Fibonacci recurrences
146           WythoffPreliminaryTriangle
147           PowerArray             powers in rows
148           File                   points from a disk file
149
150       And in the separate Math-PlanePath-Toothpick distribution
151
152           ToothpickTree          pattern of toothpicks
153           ToothpickReplicate     same by replication rather than tree
154           ToothpickUpist         toothpicks only growing upwards
155           ToothpickSpiral        toothpicks around the origin
156
157           LCornerTree            L-shape corner growth
158           LCornerReplicate       same by replication rather than tree
159           OneOfEight
160           HTree                  H shapes replicated
161
162       The paths are object oriented to allow parameters, though many have
163       none.  See "examples/numbers.pl" in the Math-PlanePath sources for a
164       sample printout of numbers from selected paths or all paths.
165
166   Number Types
167       The $n and "$x,$y" parameters can be either integers or floating point.
168       The paths are meant to do something sensible with fractions but expect
169       round-off for big floating point exponents.
170
171       Floating point infinities (when available) give NaN or infinite returns
172       of some kind (some unspecified kind as yet).  "n_to_xy()" on negative
173       infinity is an empty return the same as other negative $n.
174
175       Floating point NaNs (when available) give NaN, infinite, or empty/undef
176       returns, but again of some unspecified kind as yet.
177
178       Most of the classes can operate on overloaded number types as inputs
179       and give corresponding outputs.
180
181           Math::BigInt        maybe perl 5.8 up for ** operator
182           Math::BigRat
183           Math::BigFloat
184           Number::Fraction    1.14 or higher for abs()
185
186       A few classes might truncate a bignum or a fraction to a float as yet.
187       In general the intention is to make the calculations generic enough to
188       act on any sensible number type.  Recent enough versions of the bignum
189       modules might be required, perhaps "BigInt" of Perl 5.8 or higher for
190       "**" exponentiation operator.
191
192       For reference, an "undef" input as $n, $x, $y, etc, is designed to
193       provoke an uninitialized value warning when warnings are enabled.
194       Perhaps that will change, but the warning at least prevents bad inputs
195       going unnoticed.
196

FUNCTIONS

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

GENERAL CHARACTERISTICS

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

FORMULAS

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

SUBCLASSING

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

SEE ALSO

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

HOME PAGE

1442       <http://user42.tuxfamily.org/math-planepath/index.html>
1443
1444       <http://user42.tuxfamily.org/math-planepath/gallery.html>
1445

LICENSE

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