1Math::PlanePath(3) User Contributed Perl Documentation Math::PlanePath(3)
2
3
4
6 Math::PlanePath -- points on a path through the 2-D plane
7
9 use Math::PlanePath;
10 # only a base class, see the subclasses for actual operation
11
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
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
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
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
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
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
1442 <http://user42.tuxfamily.org/math-planepath/index.html>
1443
1444 <http://user42.tuxfamily.org/math-planepath/gallery.html>
1445
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.30.0 2019-08-17 Math::PlanePath(3)