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" to
320           "$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 "$x1,$y1"
323           and "$x2,$y2".  For example in "Math::PlanePath::CCurve" some
324           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 there's
357           no points in the rectangle and might instead return an over-
358           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 intended
368           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 absdx_minimum()
443           will be something bigger than 0.  absdy_minimum() likewise 0 if any
444           horizontal dY=0, or bigger if Y 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 path
535           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 empty
684           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, Corner, CornerAlternating,
904                         PyramidSides, PyramidRows (default)
905               4       DiamondSpiral, AztecDiamondRings, Staircase
906              4/2      CellularRule54, CellularRule57,
907                         DiagonalsAlternating (2 rows for +4)
908               5       PentSpiral, PentSpiralSkewed
909              5.65     PixelRings (average about 4*sqrt(2))
910               6       HexSpiral, HexSpiralSkewed, MPeaks,
911                         MultipleRings (default)
912              6/2      CellularRule190 (2 rows for +6)
913              6.28     ArchimedeanChords (approaching 2*pi),
914                         FilledRings (average 2*pi)
915               7       HeptSpiralSkewed
916               8       SquareSpiral, PyramidSpiral
917             16/2      StaircaseAlternating (up and back for +16)
918               9       TriangleSpiral, TriangleSpiralSkewed
919              12       AnvilSpiral
920              16       OctagramSpiral, ToothpickSpiral
921             19.74     TheodorusSpiral (approaching 2*pi^2)
922             32/4      KnightSpiral (4 loops 2-wide for +32)
923              64       DiamondArms (each arm)
924              72       GreekKeySpiral
925             128       SquareArms (each arm)
926            128/4      CretanLabyrinth (4 loops for +128)
927             216       HexArms (each arm)
928
929           totient     CoprimeColumns, DiagonalRationals
930           numdivisors DivisibleColumns
931           various     CellularRule
932
933           parameter   MultipleRings, PyramidRows
934
935       The step determines which quadratic number sequences make straight
936       lines.  For example the gap between successive perfect squares
937       increases by 2 each time (4 to 9 is +5, 9 to 16 is +7, 16 to 25 is +9,
938       etc), so the perfect squares make a straight line in the paths of step
939       2.
940
941       In general straight lines on stepped paths are quadratics
942
943          N = a*k^2 + b*k + c    where a=step/2
944
945       The polygonal numbers are like this, with the (step+2)-gonal numbers
946       making a straight line on a "step" path.  For example the 7-gonals
947       (heptagonals) are 5/2*k^2-3/2*k and make a straight line on the step=5
948       "PentSpiral".  Or the 8-gonal octagonal numbers 6/2*k^2-4/2*k on the
949       step=6 "HexSpiral".
950
951       There are various interesting properties of primes in quadratic
952       progressions.  Some quadratics seem to have more primes than others.
953       For example see "Lucky Numbers of Euler" in
954       Math::PlanePath::PyramidSides.  Many quadratics have no primes at all,
955       or none above a certain point, either trivially if always a multiple of
956       2 etc, or by a more sophisticated reasoning.  See "Step 3 Pentagonals"
957       in Math::PlanePath::PyramidRows for a factorization on the roots making
958       a no-primes gap.
959
960       A 4*step path splits a straight line in two, so for example the perfect
961       squares are a straight line on the step=2 "Corner" path, and then on
962       the step=8 "SquareSpiral" they instead fall on two lines (lower left
963       and upper right).  In the bigger step there's one line of the even
964       squares (2k)^2 == 4*k^2 and another of the odd squares (2k+1)^2.  The
965       gap between successive even squares increases by 8 each time and
966       likewise between odd squares.
967
968   Self-Similar Powers
969       The self-similar patterns such as "PeanoCurve" generally have a base
970       pattern which repeats at powers N=base^level or squares
971       N=(base*base)^level.  Or some multiple or relationship to such a power
972       for things like "KochPeaks" and "GosperIslands".
973
974           Base          Path
975           ----          ----
976             2         HilbertCurve, HilbertSides, HilbertSpiral,
977                         ZOrderCurve (default), GrayCode (default),
978                         BetaOmega, AR2W2Curve, HIndexing,
979                         ImaginaryBase (default), ImaginaryHalf (default),
980                         SierpinskiCurve, SierpinskiCurveStair,
981                         CubicBase (default) CornerReplicate,
982                         ComplexMinus (default), ComplexPlus (default),
983                         ComplexRevolving, DragonCurve, DragonRounded,
984                         DragonMidpoint, AlternatePaper, AlternatePaperMidpoint,
985                         CCurve, DigitGroups (default), PowerArray (default)
986             3         PeanoCurve (default), PeanoDiagonals (default),
987                         WunderlichSerpentine (default),WunderlichMeander,
988                         KochelCurve, GosperIslands, GosperSide
989                         SierpinskiTriangle, SierpinskiArrowhead,
990                         SierpinskiArrowheadCentres,
991                         TerdragonCurve, TerdragonRounded, TerdragonMidpoint,
992                         AlternateTerdragon,
993                         UlamWarburton, UlamWarburtonQuarter (each level)
994             4         KochCurve, KochPeaks, KochSnowflakes, KochSquareflakes,
995                         LTiling,
996             5         QuintetCurve, QuintetCentres, QuintetReplicate,
997                         DekkingCurve, DekkingCentres, CincoCurve,
998                         R5DragonCurve, R5DragonMidpoint
999             7         Flowsnake, FlowsnakeCentres, GosperReplicate
1000             8         QuadricCurve, QuadricIslands
1001             9         SquareReplicate
1002           Fibonacci   FibonacciWordFractal, WythoffArray
1003           parameter   PeanoCurve, PeanoDiagonals, WunderlichSerpentine,
1004                         ZOrderCurve, GrayCode, ImaginaryBase, ImaginaryHalf,
1005                         CubicBase, ComplexPlus, ComplexMinus, DigitGroups,
1006                         PowerArray
1007
1008       Many number sequences plotted on these self-similar paths tend to be
1009       fairly random, or merely show the tiling or path layout rather than
1010       much about the number sequence.  Sequences related to the base can make
1011       holes or patterns picking out parts of the path.  For example numbers
1012       without a particular digit (or digits) in the relevant base show up as
1013       holes.  See for example "Power of 2 Values" in
1014       Math::PlanePath::ZOrderCurve.
1015
1016   Triangular Lattice
1017       Some paths are on triangular or "A2" lattice points like
1018
1019             *---*---*---*---*---*
1020            / \ / \ / \ / \ / \ /
1021           *---*---*---*---*---*
1022            \ / \ / \ / \ / \ / \
1023             *---*---*---*---*---*
1024            / \ / \ / \ / \ / \ /
1025           *---*---*---*---*---*
1026            \ / \ / \ / \ / \ / \
1027             *---*---*---*---*---*
1028            / \ / \ / \ / \ / \ /
1029           *---*---*---*---*---*
1030
1031       This is done in integer X,Y on a square grid by using every second
1032       square and offsetting alternate rows.  This means sum X+Y even, ie. X,Y
1033       either both even or both odd, not of opposite parity.
1034
1035           . * . * . * . * . * . *
1036           * . * . * . * . * . * .
1037           . * . * . * . * . * . *
1038           * . * . * . * . * . * .
1039           . * . * . * . * . * . *
1040           * . * . * . * . * . * .
1041
1042       The X axis the and diagonals X=Y and X=-Y divide the plane into six
1043       equal parts in this grid.
1044
1045              X=-Y     X=Y
1046                \     /
1047                 \   /
1048                  \ /
1049           ----------------- X=0
1050                  / \
1051                 /   \
1052                /     \
1053
1054       The diagonal X=3*Y is the middle of the first sixth, representing a
1055       twelfth of the plane.
1056
1057       The resulting triangles are flatter than they should be.  The triangle
1058       base is width=2 and top is height=1, whereas it would be height=sqrt(3)
1059       for an equilateral triangle.  That sqrt(3) factor can be applied if
1060       desired,
1061
1062           X, Y*sqrt(3)          side length 2
1063
1064           X/2, Y*sqrt(3)/2      side length 1
1065
1066       Integer Y values have the advantage of fitting pixels on the usual kind
1067       of raster computer screen, and not losing precision in floating point
1068       results.
1069
1070       If doing a general-purpose coordinate rotation then be sure to apply
1071       the sqrt(3) scale factor before rotating or the result will be skewed.
1072       60 degree rotations can be made within the integer X,Y coordinates
1073       directly as follows, all giving integer X,Y results.
1074
1075           ( X-3Y)/2, ( X+Y)/2     rotate +60   (anti-clockwise)
1076           ( X+3Y)/2, (-X+Y)/2     rotate -60   (clockwise)
1077           (-X-3Y)/2, ( X-Y)/2     rotate +120
1078           (-X+3Y)/2, (-X-Y)/2     rotate -120
1079           -X,-Y                   rotate 180
1080
1081           (X+3Y)/2, (X-Y)/2       mirror across the X=3*Y twelfth (30deg)
1082
1083       The sqrt(3) factor can be worked into a hypotenuse radial distance
1084       calculation as follows if comparing distances from the origin.
1085
1086           hypot = sqrt(X*X + 3*Y*Y)
1087
1088       See for instance "TriangularHypot" which is triangular points ordered
1089       by this radial distance.
1090

FORMULAS

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

SUBCLASSING

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

SEE ALSO

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

HOME PAGE

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

LICENSE

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