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 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
200 In the following "Foo" is one of the various subclasses, see the list
201 above and under "SEE ALSO".
202
203 Constructor
204 "$path = Math::PlanePath::Foo->new (key=>value, ...)"
205 Create and return a new path object. Optional key/value parameters
206 may control aspects of the object.
207
208 Coordinate Methods
209 "($x,$y) = $path->n_to_xy ($n)"
210 Return X,Y coordinates of point $n on the path. If there's no
211 point $n then the return is an empty list. For example
212
213 my ($x,$y) = $path->n_to_xy (-123)
214 or next; # no negatives in $path
215
216 Paths start from "$path->n_start()" below, though some will give a
217 position for N=0 or N=-0.5 too.
218
219 "($dx,$dy) = $path->n_to_dxdy ($n)"
220 Return the change in X and Y going from point $n to point "$n+1",
221 or for paths with multiple arms from $n to "$n+$arms_count" (thus
222 advancing one point along the arm of $n).
223
224 + $n+1 == $next_x,$next_y
225 ^
226 |
227 | $dx = $next_x - $x
228 + $n == $x,$y $dy = $next_y - $y
229
230 $n can be fractional and in that case the dX,dY is from that
231 fractional $n position to "$n+1" (or "$n+$arms").
232
233 frac $n+1 == $next_x,$next_y
234 v
235 integer *---+----
236 | /
237 | /
238 |/ $dx = $next_x - $x
239 frac + $n == $x,$y $dy = $next_y - $y
240 |
241 integer *
242
243 In both cases "n_to_dxdy()" is the difference "$dx=$next_x-$x,
244 $dy=$next_y-$y". Currently for most paths it's merely two
245 "n_to_xy()" calls to calculate the two points, but some paths can
246 calculate a dX,dY with a little less work.
247
248 "$rsquared = $path->n_to_radius ($n)"
249 "$rsquared = $path->n_to_rsquared ($n)"
250 Return the radial distance R=sqrt(X^2+Y^2) of point $n, or the
251 radius squared R^2=X^2+Y^2. If there's no point $n then the return
252 is "undef".
253
254 For a few paths, these might be calculated with less work than
255 "n_to_xy()". For example the "SacksSpiral" is simply R^2=N, or the
256 "MultipleRings" path with its default step=6 has an integer radius
257 for integer $n whereas "$x,$y" are fractional (and so inexact).
258
259 "$n = $path->xy_to_n ($x,$y)"
260 Return the N point number at coordinates "$x,$y". If there's
261 nothing at "$x,$y" then return "undef".
262
263 my $n = $path->xy_to_n(20,20);
264 if (! defined $n) {
265 next; # nothing at this X,Y
266 }
267
268 $x and $y can be fractional and the path classes will give an
269 integer $n which contains "$x,$y" within a unit square, circle, or
270 intended figure centred on the integer $n.
271
272 For paths which completely fill the plane there's always an $n to
273 return, but for the spread-out paths an "$x,$y" position may fall
274 in between (no $n close enough) and give "undef".
275
276 "@n_list = $path->xy_to_n_list ($x,$y)"
277 Return a list of N point numbers at coordinates "$x,$y". If
278 there's nothing at "$x,$y" then return an empty list.
279
280 my @n_list = $path->xy_to_n(20,20);
281
282 Most paths have just a single N for a given X,Y but some such as
283 "DragonCurve" and "TerdragonCurve" have multiple N's and this
284 method returns all of them.
285
286 Currently all paths have a finite number of N at a given location.
287 It's unspecified what might happen for an infinite list, if that
288 ever occurred.
289
290 "@n_list = $path->n_to_n_list ($n)"
291 Return a list of all N point numbers at the location of $n. This
292 is equivalent to "xy_to_n_list(n_to_xy($n))".
293
294 The return list includes $n itself. If there is no $n in the path
295 then return an empty list.
296
297 This function is convenient for paths like "DragonCurve" or
298 "TerdragonCurve" with double or triple visited points so an N may
299 have other N at the same location.
300
301 "$bool = $path->xy_is_visited ($x,$y)"
302 Return true if "$x,$y" is visited. This is equivalent to
303
304 defined($path->xy_to_n($x,$y))
305
306 Some paths cover the plane and for them "xy_is_visited()" is always
307 true. For others it might be less work to test a point than to
308 calculate its $n.
309
310 "$n = $path->xyxy_to_n($x1,$y1, $x2,$y2)"
311 "$n = $path->xyxy_to_n_either($x1,$y1, $x2,$y2)"
312 "@n_list = $path->xyxy_to_n_list($x1,$y1, $x2,$y2)"
313 "@n_list = $path->xyxy_to_n_list_either($x1,$y1, $x2,$y2)"
314 Return <$n> which goes from "$x1,$y1" to "$x2,$y2". <$n> is at
315 "$x1,$y1" and "$n+1" is at "$x2,$y2", or for a multi-arm path
316 "$n+$arms", so a step along the same arm. If there's no such $n
317 then return "undef".
318
319 The "either()" forms allow <$n> in either direction, so "$x1,$y1"
320 to "$x2,$y2" or the other way "$x2,$y2" to "$x1,$y1".
321
322 The "n_list()" forms return a list of all $n going between
323 "$x1,$y1" and "$x2,$y2". For example in "Math::PlanePath::CCurve"
324 some segments are traversed twice, once in each direction.
325
326 The possible N values at each X,Y are determined the same way as
327 for "xy_to_n()".
328
329 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
330 Return a range of N values covering the rectangle with corners at
331 $x1,$y1 and $x2,$y2. The range is inclusive. For example,
332
333 my ($n_lo, $n_hi) = $path->rect_to_n_range (-5,-5, 5,5);
334 foreach my $n ($n_lo .. $n_hi) {
335 my ($x, $y) = $path->n_to_xy($n) or next;
336 print "$n $x,$y";
337 }
338
339 The return might be an over-estimate of the N range required to
340 cover the rectangle. Even if the range is exact, the nature of the
341 path may mean many points between $n_lo and $n_hi are outside the
342 rectangle. But the range is at least a lower and upper bound on
343 the N values which occur in the rectangle. Classes which guarantee
344 an exact lo/hi say so in their docs.
345
346 $n_hi is usually no more than an extra partial row, revolution, or
347 self-similar level. $n_lo might be merely the starting
348 "$path->n_start()", which is fine if the origin is in the desired
349 rectangle but away from the origin could actually start higher.
350
351 $x1,$y1 and $x2,$y2 can be fractional. If they partly overlap some
352 N figures then those N's are included in the return.
353
354 If there's no points in the rectangle then the return can be a
355 "crossed" range like "$n_lo=1", "$n_hi=0" (which makes a "foreach"
356 do no loops). But "rect_to_n_range()" may not always notice
357 there's no points in the rectangle and might instead return an
358 over-estimate.
359
360 Descriptive Methods
361 "$n = $path->n_start()"
362 Return the first N in the path. The start is usually either 0 or 1
363 according to what is most natural for the path. Some paths have an
364 "n_start" parameter to control the numbering.
365
366 Some classes have secret dubious undocumented support for N values
367 below this start (zero or negative), but "n_start()" is the
368 intended starting point.
369
370 "$f = $path->n_frac_discontinuity()"
371 Return the fraction of N at which there may be discontinuities in
372 the path. For example if there's a jump in the coordinates between
373 N=7.4999 and N=7.5 then the returned $f is 0.5. Or $f is 0 if
374 there's a discontinuity between 6.999 and 7.0.
375
376 If there's no discontinuities in the path then the return is
377 "undef". That means for example fractions between N=7 to N=8 give
378 smooth continuous X,Y values (of some kind).
379
380 This is mainly of interest for drawing line segments between N
381 points. If there's discontinuities then the idea is to draw from
382 say N=7.0 to N=7.499 and then another line from N=7.5 to N=8.
383
384 "$arms = $path->arms_count()"
385 Return the number of arms in a "multi-arm" path.
386
387 For example in "SquareArms" this is 4 and each arm increments in
388 turn, so the first arm is N=1,5,9,13,etc starting from
389 "$path->n_start()" and incrementing by 4 each time.
390
391 "$bool = $path->x_negative()"
392 "$bool = $path->y_negative()"
393 Return true if the path extends into negative X coordinates and/or
394 negative Y coordinates respectively.
395
396 "$bool = Math::PlanePath::Foo->class_x_negative()"
397 "$bool = Math::PlanePath::Foo->class_y_negative()"
398 "$bool = $path->class_x_negative()"
399 "$bool = $path->class_y_negative()"
400 Return true if any paths made by this class extend into negative X
401 coordinates and/or negative Y coordinates, respectively.
402
403 For some classes the X or Y extent may depend on parameter values.
404
405 "$n = $path->x_negative_at_n()"
406 "$n = $path->y_negative_at_n()"
407 Return the integer N where X or Y respectively first goes negative,
408 or return "undef" if it does not go negative ("x_negative()" or
409 "y_negative()" respectively is false).
410
411 "$x = $path->x_minimum()"
412 "$y = $path->y_minimum()"
413 "$x = $path->x_maximum()"
414 "$y = $path->y_maximum()"
415 Return the minimum or maximum of the X or Y coordinate reached by
416 integer N values in the path. If there's no minimum or maximum
417 then return "undef".
418
419 "$dx = $path->dx_minimum()"
420 "$dx = $path->dx_maximum()"
421 "$dy = $path->dy_minimum()"
422 "$dy = $path->dy_maximum()"
423 Return the minimum or maximum change dX, dY occurring in the path
424 for integer N to N+1. For a multi-arm path the change is N to
425 N+arms so it's the change along the same arm.
426
427 Various paths which go by rows have non-decreasing Y. For them
428 "dy_minimum()" is 0.
429
430 "$adx = $path->absdx_minimum()"
431 "$adx = $path->absdx_maximum()"
432 "$ady = $path->absdy_minimum()"
433 "$ady = $path->absdy_maximum()"
434 Return the minimum or maximum change abs(dX) or abs(dY) occurring
435 in the path for integer N to N+1. For a multi-arm path, the change
436 is N to N+arms so it's the change along the same arm.
437
438 "absdx_maximum()" is simply max(dXmax,-dXmin), the biggest change
439 either positive or negative. "absdy_maximum()" similarly.
440
441 "absdx_minimum()" is 0 if dX=0 occurs anywhere in the path, which
442 means any vertical step. If X always changes then
443 "absdx_minimum()" will be something bigger than 0.
444 "absdy_minimum()" likewise 0 if any horizontal dY=0, or bigger if Y
445 always changes.
446
447 "$sum = $path->sumxy_minimum()"
448 "$sum = $path->sumxy_maximum()"
449 Return the minimum or maximum values taken by coordinate sum X+Y
450 reached by integer N values in the path. If there's no minimum or
451 maximum then return "undef".
452
453 S=X+Y is an anti-diagonal. A path which is always right and above
454 some anti-diagonal has a minimum. Some paths might be entirely
455 left and below and so have a maximum, though that's unusual.
456
457 \ Path always above
458 \ | has minimum S=X+Y
459 \|
460 ---o----
461 Path always below |\
462 has maximum S=X+Y | \
463 \ S=X+Y
464
465 "$sum = $path->sumabsxy_minimum()"
466 "$sum = $path->sumabsxy_maximum()"
467 Return the minimum or maximum values taken by coordinate sum
468 abs(X)+abs(Y) reached by integer N values in the path. A minimum
469 always exists but if there's no maximum then return "undef".
470
471 SumAbs=abs(X)+abs(Y) is sometimes called the "taxi-cab" or
472 "Manhattan" distance, being how far to travel through a square-grid
473 city to get to X,Y. "sumabsxy_minimum()" is then how close to the
474 origin the path extends.
475
476 SumAbs can also be interpreted geometrically as numbering the anti-
477 diagonals of the quadrant containing X,Y, which is equivalent to
478 asking which diamond shape X,Y falls on. "sumabsxy_minimum()" is
479 then the smallest such diamond reached by the path.
480
481 |
482 /|\ SumAbs = which diamond X,Y falls on
483 / | \
484 / | \
485 -----o-----
486 \ | /
487 \ | /
488 \|/
489 |
490
491 "$diffxy = $path->diffxy_minimum()"
492 "$diffxy = $path->diffxy_maximum()"
493 Return the minimum or maximum values taken by coordinate difference
494 X-Y reached by integer N values in the path. If there's no minimum
495 or maximum then return "undef".
496
497 D=X-Y is a leading diagonal. A path which is always right and
498 below such a diagonal has a minimum, for example "HypotOctant". A
499 path which is always left and above some diagonal has a maximum
500 D=X-Y. For example various wedge-like paths such as "PyramidRows"
501 in its default step=2, and "upper octant" paths have a maximum.
502
503 / D=X-Y
504 Path always below | /
505 has maximum D=X-Y |/
506 ---o----
507 /|
508 / | Path always above
509 / has minimum D=X-Y
510
511 "$absdiffxy = $path->absdiffxy_minimum()"
512 "$absdiffxy = $path->absdiffxy_maximum()"
513 Return the minimum or maximum values taken by abs(X-Y) for integer
514 N in the path. The minimum is 0 or more. If there's maximum then
515 return "undef".
516
517 abs(X-Y) can be interpreted geometrically as the distance away from
518 the X=Y diagonal and measured at right-angles to that line.
519
520 d=abs(X-Y) X=Y line
521 ^ /
522 \ /
523 \/
524 /\
525 / \
526 / \
527 o v
528 / d=abs(X-Y)
529
530 Paths which visit the X=Y line (or approach it as an infimum) have
531 "absdiffxy_minimum() = 0". Otherwise "absdiffxy_minimum()" is how
532 close they come to the line.
533
534 If the path is entirely below the X=Y line so X>=Y then X-Y>=0 and
535 "absdiffxy_minimum()" is the same as "diffxy_minimum()". If the
536 path is entirely below the X=Y line then "absdiffxy_minimum()" is
537 "-Â diffxy_maximum()".
538
539 "$dsumxy = $path->dsumxy_minimum()"
540 "$dsumxy = $path->dsumxy_maximum()"
541 "$ddiffxy = $path->ddiffxy_minimum()"
542 "$ddiffxy = $path->ddiffxy_maximum()"
543 Return the minimum or maximum change dSum or dDiffXY occurring in
544 the path for integer N to N+1. For a multi-arm path, the change is
545 N to N+arms so it's the change along the same arm.
546
547 "$rsquared = $path->rsquared_minimum()"
548 "$rsquared = $path->rsquared_maximum()"
549 Return the minimum or maximum Rsquared = X^2+Y^2 reached by integer
550 N values in the path. If there's no minimum or maximum then return
551 "undef".
552
553 Rsquared is always >= 0 so it always has a minimum. The minimum
554 will be more than 0 for paths which don't include the origin
555 X=0,Y=0.
556
557 RSquared generally has no maximum since the paths usually extend
558 infinitely in some direction. "rsquared_maximum()" returns "undef"
559 in that case.
560
561 "($dx,$dy) = $path->dir_minimum_dxdy()"
562 "($dx,$dy) = $path->dir_maximum_dxdy()"
563 Return a vector which is the minimum or maximum angle taken by a
564 step integer N to N+1, or for a multi-arm path N to N+arms, so it's
565 the change along the same arm. Directions are reckoned anti-
566 clockwise around from the X axis.
567
568 | * dX=2,dY=2
569 dX=-1,dY=1 * | /
570 \|/
571 ------+----* dX=1,dY=0
572 |
573 |
574 * dX=0,dY=-1
575
576 A path which is always goes N,S,E,W such as the "SquareSpiral" has
577 minimum East dX=1,dY=0 and maximum South dX=0,dY=-1.
578
579 Paths which go diagonally may have different limits. For example
580 the "KnightSpiral" goes in 2x1 steps and so has minimum East-North-
581 East dX=2,dY=1 and maximum East-South-East dX=2,dY=-1.
582
583 If the path has directions approaching 360 degrees then
584 "dir_maximum_dxdy()" is 0,0 which should be taken to mean a full
585 circle as a supremum. For example "MultipleRings".
586
587 If the path only ever goes East then the maximum is East dX=1,dY=0,
588 and the minimum the same. This isn't particularly interesting, but
589 arises for example in the "Columns" path height=0.
590
591 "$bool = $path->turn_any_left()"
592 "$bool = $path->turn_any_right()"
593 "$bool = $path->turn_any_straight()"
594 Return true if the path turns left, right, or straight (which
595 includes 180deg reverse) at any integer N.
596
597 N+1 left
598
599 N-1 -------- N --> N+1 straight
600
601 N+1 right
602
603 A line from N-1 to N is a current direction and the turn at N is
604 then whether point N+1 is to the left or right of that line.
605 Directly along the line is straight, and so is anything directly
606 behind as a reverse. This is the turn style of
607 Math::NumSeq::PlanePathTurn.
608
609 "$str = $path->figure()"
610 Return a string name of the figure (shape) intended to be drawn at
611 each $n position. This is currently either
612
613 "square" side 1 centred on $x,$y
614 "circle" diameter 1 centred on $x,$y
615
616 Of course this is only a suggestion since PlanePath doesn't draw
617 anything itself. A figure like a diamond for instance can look
618 good too.
619
620 Tree Methods
621 Some paths are structured like a tree where each N has a parent and
622 possibly some children.
623
624 123
625 / | \
626 456 999 458
627 / / \
628 1000 1001 1005
629
630 The N numbering and any relation to X,Y positions varies among the
631 paths. Some are numbered by rows in breadth-first style and some have
632 children with X,Y positions adjacent to their parent, but that
633 shouldn't be assumed, only that there's a parent-child relation down
634 from some set of root nodes.
635
636 "$bool = $path->is_tree()"
637 Return true if $path is a tree.
638
639 The various tree methods have empty or "undef" returns on non-tree
640 paths. Often it's enough to check for that from a desired method
641 rather than a separate "is_tree()" check.
642
643 "@n_children = $path->tree_n_children($n)"
644 Return a list of N values which are the child nodes of $n, or
645 return an empty list if $n has no children.
646
647 There could be no children either because $path is not a tree or
648 because there's no children at a particular $n.
649
650 "$num = $path->tree_n_num_children($n)"
651 Return the number of children of $n, or 0 if $n has no children, or
652 "undef" if "$n < n_start()" (ie. before the start of the path).
653
654 If the tree is considered as a directed graph then this is the
655 "out-degree" of $n.
656
657 "$n_parent = $path->tree_n_parent($n)"
658 Return the parent node of $n, or "undef" if it has no parent.
659
660 There is no parent at the root node of the tree, or one of multiple
661 roots, or if $path is not a tree.
662
663 "$n_root = $path->tree_n_root ($n)"
664 Return the N which is the root node of $n. This is the top of the
665 tree as would be found by following "tree_n_parent()" repeatedly.
666
667 The return is "undef" if there's no $n point or if $path is not a
668 tree.
669
670 "$depth = $path->tree_n_to_depth($n)"
671 Return the depth of node $n, or "undef" if there's no point $n.
672 The top of the tree is depth=0, then its children are depth=1, etc.
673
674 The depth is a count of how many parent, grandparent, etc, levels
675 are above $n, ie. until reaching "tree_n_to_parent()" returning
676 "undef". For non-tree paths "tree_n_to_parent()" is always "undef"
677 and "tree_n_to_depth()" is always 0.
678
679 "$n_lo = $path->tree_depth_to_n($depth)"
680 "$n_hi = $path->tree_depth_to_n_end($depth)"
681 "($n_lo, $n_hi) = $path->tree_depth_to_n_range ($depth)"
682 Return the first or last N, or both those N, for tree level $depth
683 in the path. If there's no such $depth or if $path is not a tree
684 then return "undef", or for "tree_depth_to_n_range()" return an
685 empty list.
686
687 The points $n_lo through $n_hi might not necessarily all be at
688 $depth. It's possible for depths to be interleaved or intermixed
689 in the point numbering. But many paths are breadth-wise successive
690 rows and for them $n_lo to $n_hi inclusive is all $depth.
691
692 $n_hi can only exist if the row has a finite number of points.
693 That's true of all current paths, but perhaps allowance ought to be
694 made for $n_hi as "undef" or some such if there is no maximum N for
695 some row.
696
697 "$num = $path->tree_depth_to_width ($depth)"
698 Return the number of points at $depth in the tree. If there's no
699 such $depth or $path is not a tree then return "undef".
700
701 "$height = $path->tree_n_to_subheight($n)"
702 Return the height of the sub-tree starting at $n, or "undef" if
703 infinite. The height of a tree is the longest distance down to a
704 leaf node. For example,
705
706 ... N subheight
707 \ --- ---------
708 6 7 8 0 undef
709 \ \ / 1 undef
710 3 4 5 2 2
711 \ \ / 3 undef
712 1 2 4 1
713 \ / 5 0
714 0 ...
715
716 At N=0 and all of the left side the tree continues infinitely so
717 the sub-height there is "undef" for infinite. For N=2 the sub-
718 height is 2 because the longest path down is 2 levels (to N=7 or
719 N=8). For a leaf node such as N,=5 the sub-height is 0.
720
721 Tree Descriptive Methods
722 "$num = $path->tree_num_roots()"
723 Return the number of root nodes in $path. If $path is not a tree
724 then return 0. Many tree paths have a single root and for them the
725 return is 1.
726
727 "@n_list = $path->tree_root_n_list()"
728 Return a list of the N values which are the root nodes in $path.
729 If $path is not a tree then this is an empty list. There are
730 "tree_num_roots()" many return values.
731
732 "$num = $path->tree_num_children_minimum()"
733 "$num = $path->tree_num_children_maximum()"
734 "@nums = $path->tree_num_children_list()"
735 Return the possible number of children of the nodes of $path,
736 either the minimum, the maximum, or a list of all possible numbers
737 of children.
738
739 For "tree_num_children_list()" the list of values is in increasing
740 order, so the first value is "tree_num_children_minimum()" and the
741 last is "tree_num_children_maximum()".
742
743 "$bool = $path->tree_any_leaf()"
744 Return true if there are any leaf nodes in the tree, meaning any N
745 for which "tree_n_num_children()" is 0.
746
747 This is the same as "tree_num_children_minimum()==0" since if
748 NumChildren=0 occurs then there are leaf nodes.
749
750 Some trees may have no leaf nodes, for example in the complete
751 binary tree of "RationalsTree" every node always has 2 children.
752
753 Level Methods
754 "level = $path->n_to_level($n)"
755 Return the replication level containing $n. The first level is 0.
756
757 "($n_lo,$n_hi) = $path->level_to_n_range($level)"
758 Return the range of N values, inclusive, which comprise a self-
759 similar replication level in $path. If $path has no notion of such
760 levels then return an empty list.
761
762 my ($n_lo, $n_hi) = $path->level_to_n_range(6)
763 or print "no levels in this path";
764
765 For example the "DragonCurve" has levels running 0 to "2**$level",
766 or the "HilbertCurve" is 0 to "4**$level - 1". Most levels are
767 powers like this. A power "2**$level" is a "vertex" style whereas
768 "2**$level - 1" is a "centre" style. The difference is generally
769 whether the X,Y points represent vertices of the object's segments
770 as opposed to centres or midpoints.
771
772 Parameter Methods
773 "$aref = Math::PlanePath::Foo->parameter_info_array()"
774 "@list = Math::PlanePath::Foo->parameter_info_list()"
775 Return an arrayref of list describing the parameters taken by a
776 given class. This meant to help making widgets etc for user
777 interaction in a GUI. Each element is a hashref
778
779 {
780 name => parameter key arg for new()
781 share_key => string, or undef
782 description => human readable string
783 type => string "integer","boolean","enum" etc
784 default => value
785 minimum => number, or undef
786 maximum => number, or undef
787 width => integer, suggested display size
788 choices => for enum, an arrayref
789 }
790
791 "type" is a string, one of
792
793 "integer"
794 "enum"
795 "boolean"
796 "string"
797 "filename"
798
799 "filename" is separate from "string" since it might require subtly
800 different handling to reach Perl as a byte string, whereas a
801 "string" type might in principle take Perl wide chars.
802
803 For "enum" the "choices" field is the possible values, such as
804
805 { name => "flavour",
806 type => "enum",
807 choices => ["strawberry","chocolate"],
808 }
809
810 "minimum" and/or "maximum" are omitted if there's no hard limit on
811 the parameter.
812
813 "share_key" is designed to indicate when parameters from different
814 "PlanePath" classes can done by a single control widget in a GUI
815 etc. Normally the "name" is enough, but when the same name has
816 slightly different meanings in different classes a "share_key"
817 allows the same meanings to be matched up.
818
819 "$hashref = Math::PlanePath::Foo->parameter_info_hash()"
820 Return a hashref mapping parameter names "$info->{'name'}" to their
821 $info records.
822
823 { wider => { name => "wider",
824 type => "integer",
825 ...
826 },
827 }
828
830 The classes are mostly based on integer $n positions and those designed
831 for a square grid turn an integer $n into integer "$x,$y". Usually
832 they give in-between positions for fractional $n too. Classes not on a
833 square grid but instead giving fractional X,Y such as "SacksSpiral" and
834 "VogelFloret" are designed for a unit circle at each $n but they too
835 can give in-between positions on request.
836
837 All X,Y positions are calculated by separate "n_to_xy()" calls. To
838 follow a path use successive $n values starting from
839 "$path->n_start()".
840
841 foreach my $n ($path->n_start .. 100) {
842 my ($x,$y) = $path->n_to_xy($n);
843 print "$n $x,$y\n";
844 }
845
846 The separate "n_to_xy()" calls were motivated by plotting just some N
847 points of a path, such as just the primes or the perfect squares.
848 Successive positions in paths could perhaps be done more efficiently in
849 an iterator style. Paths with a quadratic "step" are not much worse
850 than a "sqrt()" to break N into a segment and offset, but the self-
851 similar paths which chop N into digits of some radix could increment
852 instead of recalculate.
853
854 If interested only in a particular rectangle or similar region then
855 iterating has the disadvantage that it may stray outside the target
856 region for a long time, making an iterator much less useful than it
857 seems. For wild paths it can be better to apply "xy_to_n()" by rows or
858 similar across the desired region.
859
860 Math::NumSeq::PlanePathCoord etc offer the PlanePath coordinates,
861 directions, turns, etc as sequences. The iterator forms there simply
862 make repeated calls to "n_to_xy()" etc.
863
864 Scaling and Orientation
865 The paths generally make a first move to the right and go anti-
866 clockwise around from the X axis, unless there's some more natural
867 orientation. Anti-clockwise is the usual direction for mathematical
868 spirals.
869
870 There's no parameters for scaling, offset or reflection as those things
871 are thought better left to a general coordinate transformer, for
872 example to expand or invert for display. Some easy transformations can
873 be had just from the X,Y with
874
875 -X,Y flip horizontally (mirror image)
876 X,-Y flip vertically (across the X axis)
877
878 -Y,X rotate +90 degrees (anti-clockwise)
879 Y,-X rotate -90 degrees (clockwise)
880 -X,-Y rotate 180 degrees
881
882 Flip vertically makes spirals go clockwise instead of anti-clockwise,
883 or a flip horizontally the same but starting on the left at the
884 negative X axis. See "Triangular Lattice" below for 60 degree
885 rotations of the triangular grid paths too.
886
887 The Rows and Columns paths are exceptions to the rule of not having
888 rotated versions of paths. They began as ways to pass in width and
889 height as generic parameters and let the path use the one or the other.
890
891 For scaling and shifting see for example Transform::Canvas, and to
892 rotate as well see Geometry::AffineTransform.
893
894 Loop Step
895 The paths can be characterized by how much longer each loop or
896 repetition is than the preceding one. For example each cycle around
897 the "SquareSpiral" is 8 more N points than the preceding.
898
899 Step Path
900 ---- ----
901 0 Rows, Columns (fixed widths)
902 1 Diagonals
903 2/2 DiagonalsOctant (2 rows for +2)
904 2 SacksSpiral, Corner, CornerAlternating,
905 PyramidSides, PyramidRows (default)
906 4 DiamondSpiral, AztecDiamondRings, Staircase
907 4/2 CellularRule54, CellularRule57,
908 DiagonalsAlternating (2 rows for +4)
909 5 PentSpiral, PentSpiralSkewed
910 5.65 PixelRings (average about 4*sqrt(2))
911 6 HexSpiral, HexSpiralSkewed, MPeaks,
912 MultipleRings (default)
913 6/2 CellularRule190 (2 rows for +6)
914 6.28 ArchimedeanChords (approaching 2*pi),
915 FilledRings (average 2*pi)
916 7 HeptSpiralSkewed
917 8 SquareSpiral, PyramidSpiral
918 16/2 StaircaseAlternating (up and back for +16)
919 9 TriangleSpiral, TriangleSpiralSkewed
920 12 AnvilSpiral
921 16 OctagramSpiral, ToothpickSpiral
922 19.74 TheodorusSpiral (approaching 2*pi^2)
923 32/4 KnightSpiral (4 loops 2-wide for +32)
924 64 DiamondArms (each arm)
925 72 GreekKeySpiral
926 128 SquareArms (each arm)
927 128/4 CretanLabyrinth (4 loops for +128)
928 216 HexArms (each arm)
929
930 totient CoprimeColumns, DiagonalRationals
931 numdivisors DivisibleColumns
932 various CellularRule
933
934 parameter MultipleRings, PyramidRows
935
936 The step determines which quadratic number sequences make straight
937 lines. For example the gap between successive perfect squares
938 increases by 2 each time (4 to 9 is +5, 9 to 16 is +7, 16 to 25 is +9,
939 etc), so the perfect squares make a straight line in the paths of step
940 2.
941
942 In general straight lines on stepped paths are quadratics
943
944 N = a*k^2 + b*k + c where a=step/2
945
946 The polygonal numbers are like this, with the (step+2)-gonal numbers
947 making a straight line on a "step" path. For example the 7-gonals
948 (heptagonals) are 5/2*k^2-3/2*k and make a straight line on the step=5
949 "PentSpiral". Or the 8-gonal octagonal numbers 6/2*k^2-4/2*k on the
950 step=6 "HexSpiral".
951
952 There are various interesting properties of primes in quadratic
953 progressions. Some quadratics seem to have more primes than others.
954 For example see "Lucky Numbers of Euler" in
955 Math::PlanePath::PyramidSides. Many quadratics have no primes at all,
956 or none above a certain point, either trivially if always a multiple of
957 2 etc, or by a more sophisticated reasoning. See "Step 3 Pentagonals"
958 in Math::PlanePath::PyramidRows for a factorization on the roots making
959 a no-primes gap.
960
961 A 4*step path splits a straight line in two, so for example the perfect
962 squares are a straight line on the step=2 "Corner" path, and then on
963 the step=8 "SquareSpiral" they instead fall on two lines (lower left
964 and upper right). In the bigger step there's one line of the even
965 squares (2k)^2 == 4*k^2 and another of the odd squares (2k+1)^2. The
966 gap between successive even squares increases by 8 each time and
967 likewise between odd squares.
968
969 Self-Similar Powers
970 The self-similar patterns such as "PeanoCurve" generally have a base
971 pattern which repeats at powers N=base^level or squares
972 N=(base*base)^level. Or some multiple or relationship to such a power
973 for things like "KochPeaks" and "GosperIslands".
974
975 Base Path
976 ---- ----
977 2 HilbertCurve, HilbertSides, HilbertSpiral,
978 ZOrderCurve (default), GrayCode (default),
979 BetaOmega, AR2W2Curve, HIndexing,
980 ImaginaryBase (default), ImaginaryHalf (default),
981 SierpinskiCurve, SierpinskiCurveStair,
982 CubicBase (default) CornerReplicate,
983 ComplexMinus (default), ComplexPlus (default),
984 ComplexRevolving, DragonCurve, DragonRounded,
985 DragonMidpoint, AlternatePaper, AlternatePaperMidpoint,
986 CCurve, DigitGroups (default), PowerArray (default)
987 3 PeanoCurve (default), PeanoDiagonals (default),
988 WunderlichSerpentine (default),WunderlichMeander,
989 KochelCurve, GosperIslands, GosperSide
990 SierpinskiTriangle, SierpinskiArrowhead,
991 SierpinskiArrowheadCentres,
992 TerdragonCurve, TerdragonRounded, TerdragonMidpoint,
993 AlternateTerdragon,
994 UlamWarburton, UlamWarburtonQuarter (each level)
995 4 KochCurve, KochPeaks, KochSnowflakes, KochSquareflakes,
996 LTiling,
997 5 QuintetCurve, QuintetCentres, QuintetReplicate,
998 DekkingCurve, DekkingCentres, CincoCurve,
999 R5DragonCurve, R5DragonMidpoint
1000 7 Flowsnake, FlowsnakeCentres, GosperReplicate
1001 8 QuadricCurve, QuadricIslands
1002 9 SquareReplicate
1003 Fibonacci FibonacciWordFractal, WythoffArray
1004 parameter PeanoCurve, PeanoDiagonals, WunderlichSerpentine,
1005 ZOrderCurve, GrayCode, ImaginaryBase, ImaginaryHalf,
1006 CubicBase, ComplexPlus, ComplexMinus, DigitGroups,
1007 PowerArray
1008
1009 Many number sequences plotted on these self-similar paths tend to be
1010 fairly random, or merely show the tiling or path layout rather than
1011 much about the number sequence. Sequences related to the base can make
1012 holes or patterns picking out parts of the path. For example numbers
1013 without a particular digit (or digits) in the relevant base show up as
1014 holes. See for example "Power of 2 Values" in
1015 Math::PlanePath::ZOrderCurve.
1016
1017 Triangular Lattice
1018 Some paths are on triangular or "A2" lattice points like
1019
1020 *---*---*---*---*---*
1021 / \ / \ / \ / \ / \ /
1022 *---*---*---*---*---*
1023 \ / \ / \ / \ / \ / \
1024 *---*---*---*---*---*
1025 / \ / \ / \ / \ / \ /
1026 *---*---*---*---*---*
1027 \ / \ / \ / \ / \ / \
1028 *---*---*---*---*---*
1029 / \ / \ / \ / \ / \ /
1030 *---*---*---*---*---*
1031
1032 This is done in integer X,Y on a square grid by using every second
1033 square and offsetting alternate rows. This means sum X+Y even, ie. X,Y
1034 either both even or both odd, not of opposite parity.
1035
1036 . * . * . * . * . * . *
1037 * . * . * . * . * . * .
1038 . * . * . * . * . * . *
1039 * . * . * . * . * . * .
1040 . * . * . * . * . * . *
1041 * . * . * . * . * . * .
1042
1043 The X axis the and diagonals X=Y and X=-Y divide the plane into six
1044 equal parts in this grid.
1045
1046 X=-Y X=Y
1047 \ /
1048 \ /
1049 \ /
1050 ----------------- X=0
1051 / \
1052 / \
1053 / \
1054
1055 The diagonal X=3*Y is the middle of the first sixth, representing a
1056 twelfth of the plane.
1057
1058 The resulting triangles are flatter than they should be. The triangle
1059 base is width=2 and top is height=1, whereas it would be height=sqrt(3)
1060 for an equilateral triangle. That sqrt(3) factor can be applied if
1061 desired,
1062
1063 X, Y*sqrt(3) side length 2
1064
1065 X/2, Y*sqrt(3)/2 side length 1
1066
1067 Integer Y values have the advantage of fitting pixels on the usual kind
1068 of raster computer screen, and not losing precision in floating point
1069 results.
1070
1071 If doing a general-purpose coordinate rotation then be sure to apply
1072 the sqrt(3) scale factor before rotating or the result will be skewed.
1073 60 degree rotations can be made within the integer X,Y coordinates
1074 directly as follows, all giving integer X,Y results.
1075
1076 ( X-3Y)/2, ( X+Y)/2 rotate +60 (anti-clockwise)
1077 ( X+3Y)/2, (-X+Y)/2 rotate -60 (clockwise)
1078 (-X-3Y)/2, ( X-Y)/2 rotate +120
1079 (-X+3Y)/2, (-X-Y)/2 rotate -120
1080 -X,-Y rotate 180
1081
1082 (X+3Y)/2, (X-Y)/2 mirror across the X=3*Y twelfth (30deg)
1083
1084 The sqrt(3) factor can be worked into a hypotenuse radial distance
1085 calculation as follows if comparing distances from the origin.
1086
1087 hypot = sqrt(X*X + 3*Y*Y)
1088
1089 See for instance "TriangularHypot" which is triangular points ordered
1090 by this radial distance.
1091
1093 The formulas section in the POD of each class describes some of the
1094 calculations. This might be of interest even if the code is not.
1095
1096 Triangular Calculations
1097 For a triangular lattice, the rotation formulas above allow
1098 calculations to be done in the rectangular X,Y coordinates which are
1099 the inputs and outputs of the PlanePath functions. Another way is to
1100 number vertically on a 60 degree angle with coordinates i,j,
1101
1102 ...
1103 * * * 2
1104 * * * 1
1105 * * * j=0
1106 i=0 1 2
1107
1108 These coordinates are sometimes used for hexagonal grids in board games
1109 etc. Using this internally can simplify rotations a little,
1110
1111 -j, i+j rotate +60 (anti-clockwise)
1112 i+j, -i rotate -60 (clockwise)
1113 -i-j, i rotate +120
1114 j, -i-j rotate -120
1115 -i, -j rotate 180
1116
1117 Conversions between i,j and the rectangular X,Y are
1118
1119 X = 2*i + j i = (X-Y)/2
1120 Y = j j = Y
1121
1122 A third coordinate k at a +120 degrees angle can be used too,
1123
1124 k=0 k=1 k=2
1125 * * *
1126 * * *
1127 * * *
1128 0 1 2
1129
1130 This is redundant in that it doesn't number anything i,j alone can't
1131 already, but it has the advantage of turning rotations into just sign
1132 changes and swaps,
1133
1134 -k, i, j rotate +60
1135 j, k, -i rotate -60
1136 -j, -k, i rotate +120
1137 k, -i, -j rotate -120
1138 -i, -j, -k rotate 180
1139
1140 The conversions between i,j,k and the rectangular X,Y are like the i,j
1141 above but with k worked in too.
1142
1143 X = 2i + j - k i = (X-Y)/2 i = (X+Y)/2
1144 Y = j + k j = Y or j = 0
1145 k = 0 k = Y
1146
1147 N to dX,dY -- Fractional
1148 "n_to_dxdy()" is the change from N to N+1, and is designed both for
1149 integer N and fractional N. For fractional N it can be convenient to
1150 calculate a dX,dY at floor(N) and at floor(N)+1 and then combine the
1151 two in proportion to frac(N).
1152
1153 int+2
1154 |
1155 |
1156 N+1 \
1157 /| |
1158 / | |
1159 / | | frac
1160 / | |
1161 / | |
1162 / | /
1163 int-----N------int+1
1164 this_dX dX,dY next_dX
1165 this_dY next_dY
1166
1167 |-------|------|
1168 frac 1-frac
1169
1170
1171 int = int(N)
1172 frac = N - int 0 <= frac < 1
1173
1174 this_dX,this_dY at int
1175 next_dX,next_dY at int+1
1176
1177 at fractional N
1178 dX = this_dX * (1-frac) + next_dX * frac
1179 dY = this_dY * (1-frac) + next_dY * frac
1180
1181 This is combination of this_dX,this_dY and next_dX,next_dY in
1182 proportion to the distances from positions N to int+1 and from int+1 to
1183 N+1.
1184
1185 The formulas can be rearranged to
1186
1187 dX = this_dX + frac*(next_dX - this_dX)
1188 dY = this_dY + frac*(next_dY - this_dY)
1189
1190 which is like dX,dY at the integer position plus fractional part of a
1191 turn or change to the next dX,dY.
1192
1193 N to dX,dY -- Self-Similar
1194 For most of the self-similar paths such as "HilbertCurve", the change
1195 dX,dY is determined by following the state table transitions down
1196 through either all digits of N, or to the last non-9 digit, ie. drop
1197 any low digits equal to radix-1.
1198
1199 Generally paths which are the edges of some tiling use all digits, and
1200 those which are the centres of a tiling stop at the lowest non-9. This
1201 can be seen for example in the "DekkingCurve" using all digits, whereas
1202 its "DekkingCentres" variant stops at the lowest non-24.
1203
1204 Perhaps this all-digits vs low-non-9 would even characterize path style
1205 as edges or centres of a tiling, when a path is specified in some way
1206 that a tiling is not quite obvious.
1207
1209 The mandatory methods for a PlanePath subclass are
1210
1211 n_to_xy()
1212 xy_to_n()
1213 xy_to_n_list() if multiple N's map to an X,Y
1214 rect_to_n_range()
1215
1216 It sometimes happens that one of "n_to_xy()" or "xy_to_n()" is easier
1217 than the other but both should be implemented.
1218
1219 "n_to_xy()" should do something sensible on fractional N. The
1220 suggestion is to make it an X,Y proportionally between integer N
1221 positions. It could be along a straight line or an arc as best suits
1222 the path. A straight line can be done simply by two calculations of
1223 the surrounding integer points, until it's clear how to work the
1224 fraction into the code directly.
1225
1226 "xy_to_n_list()" has a base implementation calling plain "xy_to_n()" to
1227 give a single N at X,Y. If a path has multiple Ns at an X,Y (eg.
1228 "DragonCurve") then it must implement "xy_to_n_list()" to return all
1229 those Ns, and must also implement a plain "xy_to_n()" returning the
1230 first of them.
1231
1232 "rect_to_n_range()" can initially be any convenient over-estimate. It
1233 should give N big enough that from there onwards all points are sure to
1234 be beyond the given X,Y rectangle.
1235
1236 The following descriptive methods have base implementations
1237
1238 n_start() 1
1239 class_x_negative() \ 1, so whole plane
1240 class_y_negative() /
1241 x_negative() calls class_x_negative()
1242 y_negative() calls class_x_negative()
1243 x_negative_at_n() undef \ as for no negatives
1244 y_negative_at_n() undef /
1245
1246 The base "n_start()" starts at N=1. Paths which treat N as digits of
1247 some radix or where there's self-similar replication are often best
1248 started from N=0 instead since doing so puts nice powers-of-2 etc on
1249 the axes or diagonals.
1250
1251 use constant n_start => 0; # digit or replication style
1252
1253 Paths which use only parts of the plane should define
1254 "class_x_negative()" and/or "class_y_negative()" to false. For example
1255 if only the first quadrant X>=0,Y>=0 then
1256
1257 use constant class_x_negative => 0;
1258 use constant class_y_negative => 0;
1259
1260 If negativeness varies with path parameters then "x_negative()" and/or
1261 "y_negative()" follow those parameters and the "class_()" forms are
1262 whether any set of parameters ever gives negative.
1263
1264 The following methods have base implementations calling "n_to_xy()". A
1265 subclass can implement them directly if they can be done more
1266 efficiently.
1267
1268 n_to_dxdy() calls n_to_xy() twice
1269 n_to_rsquared() calls n_to_xy()
1270 n_to_radius() sqrt of n_to_rsquared()
1271
1272 "SacksSpiral" is an example of an easy "n_to_rsquared()".
1273 "TheodorusSpiral" is only slightly trickier. Unless a path has some
1274 sort of easy X^2+Y^2 then it might as well let the base implementation
1275 call "n_to_xy()".
1276
1277 The way "n_to_dxdy()" supports fractional N can be a little tricky.
1278 One way is to calculate dX,dY on the integer N below and above and
1279 combine as described in "N to dX,dY -- Fractional". For some paths the
1280 calculation of turn or direction at ceil(N) can be worked into a
1281 calculation of the direction at floor(N) so not much more work.
1282
1283 The following methods have base implementations calling "xy_to_n()". A
1284 subclass might implement them directly if it can be done more
1285 efficiently.
1286
1287 xy_is_visited() defined(xy_to_n($x,$y))
1288 xyxy_to_n() \
1289 xyxy_to_n_either() | calling xy_to_n_list()
1290 xyxy_to_n_list() |
1291 xyxy_to_n_list_either() /
1292
1293 Paths such as "SquareSpiral" which fill the plane have
1294 "xy_is_visited()" always true, so for them
1295
1296 use constant xy_is_visited => 1;
1297
1298 For a tree path the following methods are mandatory
1299
1300 tree_n_parent()
1301 tree_n_children()
1302 tree_n_to_depth()
1303 tree_depth_to_n()
1304 tree_num_children_list()
1305 tree_n_to_subheight()
1306
1307 The other tree methods have base implementations,
1308
1309 "is_tree()"
1310 Checks for "n_start()" having non-zero "tree_n_to_num_children()".
1311 Usually this suffices, expecting "n_start()" to be a root node and
1312 to have some children.
1313
1314 "tree_n_num_children()"
1315 Calls "tree_n_children()" and counts the number of return values.
1316 Many trees can count the children with less work than calculating
1317 outright, for example "RationalsTree" is simply always 2 for
1318 N>=Nstart.
1319
1320 "tree_depth_to_n_end()"
1321 Calls "tree_depth_to_n($depth+1)-1". This assumes that the depth
1322 level ends where the next begins. This is true for the various
1323 breadth-wise tree traversals, but anything interleaved etc will
1324 need its own implementation.
1325
1326 "tree_depth_to_n_range()"
1327 Calls "tree_depth_to_n()" and "tree_depth_to_n_end()". For some
1328 paths the row start and end, or start and width, might be
1329 calculated together more efficiently.
1330
1331 "tree_depth_to_width()"
1332 Returns "tree_depth_to_n_end() - tree_depth_to_n() + 1". This
1333 suits breadth-wise style paths where all points at $depth are in a
1334 contiguous block. Any path not like that will need its own
1335 "tree_depth_to_width()".
1336
1337 "tree_num_children_minimum()", "tree_num_children_maximum()"
1338 Return the first and last values of "tree_num_children_list()" as
1339 the minimum and maximum.
1340
1341 "tree_any_leaf()"
1342 Calls "tree_num_children_minimum()". If the minimum "num_children"
1343 is 0 then there's leaf nodes.
1344
1346 Math::PlanePath::SquareSpiral, Math::PlanePath::PyramidSpiral,
1347 Math::PlanePath::TriangleSpiral, Math::PlanePath::TriangleSpiralSkewed,
1348 Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiral,
1349 Math::PlanePath::PentSpiralSkewed, Math::PlanePath::HexSpiral,
1350 Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed,
1351 Math::PlanePath::AnvilSpiral, Math::PlanePath::OctagramSpiral,
1352 Math::PlanePath::KnightSpiral, Math::PlanePath::CretanLabyrinth
1353
1354 Math::PlanePath::HexArms, Math::PlanePath::SquareArms,
1355 Math::PlanePath::DiamondArms, Math::PlanePath::AztecDiamondRings,
1356 Math::PlanePath::GreekKeySpiral, Math::PlanePath::MPeaks
1357
1358 Math::PlanePath::SacksSpiral, Math::PlanePath::VogelFloret,
1359 Math::PlanePath::TheodorusSpiral, Math::PlanePath::ArchimedeanChords,
1360 Math::PlanePath::MultipleRings, Math::PlanePath::PixelRings,
1361 Math::PlanePath::FilledRings, Math::PlanePath::Hypot,
1362 Math::PlanePath::HypotOctant, Math::PlanePath::TriangularHypot,
1363 Math::PlanePath::PythagoreanTree
1364
1365 Math::PlanePath::PeanoCurve, Math::PlanePath::PeanoDiagonals,
1366 Math::PlanePath::WunderlichSerpentine,
1367 Math::PlanePath::WunderlichMeander, Math::PlanePath::HilbertCurve,
1368 Math::PlanePath::HilbertSides, Math::PlanePath::HilbertSpiral,
1369 Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode,
1370 Math::PlanePath::AR2W2Curve, Math::PlanePath::BetaOmega,
1371 Math::PlanePath::KochelCurve, Math::PlanePath::DekkingCurve,
1372 Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve
1373
1374 Math::PlanePath::ImaginaryBase, Math::PlanePath::ImaginaryHalf,
1375 Math::PlanePath::CubicBase, Math::PlanePath::SquareReplicate,
1376 Math::PlanePath::CornerReplicate, Math::PlanePath::LTiling,
1377 Math::PlanePath::DigitGroups, Math::PlanePath::FibonacciWordFractal
1378
1379 Math::PlanePath::Flowsnake, Math::PlanePath::FlowsnakeCentres,
1380 Math::PlanePath::GosperReplicate, Math::PlanePath::GosperIslands,
1381 Math::PlanePath::GosperSide
1382
1383 Math::PlanePath::QuintetCurve, Math::PlanePath::QuintetCentres,
1384 Math::PlanePath::QuintetReplicate
1385
1386 Math::PlanePath::KochCurve, Math::PlanePath::KochPeaks,
1387 Math::PlanePath::KochSnowflakes, Math::PlanePath::KochSquareflakes
1388
1389 Math::PlanePath::QuadricCurve, Math::PlanePath::QuadricIslands
1390
1391 Math::PlanePath::SierpinskiCurve,
1392 Math::PlanePath::SierpinskiCurveStair, Math::PlanePath::HIndexing
1393
1394 Math::PlanePath::SierpinskiTriangle,
1395 Math::PlanePath::SierpinskiArrowhead,
1396 Math::PlanePath::SierpinskiArrowheadCentres
1397
1398 Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded,
1399 Math::PlanePath::DragonMidpoint, Math::PlanePath::AlternatePaper,
1400 Math::PlanePath::AlternatePaperMidpoint,
1401 Math::PlanePath::TerdragonCurve, Math::PlanePath::TerdragonRounded,
1402 Math::PlanePath::TerdragonMidpoint,
1403 Math::PlanePath::AlternateTerdragon, Math::PlanePath::R5DragonCurve,
1404 Math::PlanePath::R5DragonMidpoint, Math::PlanePath::CCurve
1405
1406 Math::PlanePath::ComplexPlus, Math::PlanePath::ComplexMinus,
1407 Math::PlanePath::ComplexRevolving
1408
1409 Math::PlanePath::Rows, Math::PlanePath::Columns,
1410 Math::PlanePath::Diagonals, Math::PlanePath::DiagonalsAlternating,
1411 Math::PlanePath::DiagonalsOctant, Math::PlanePath::Staircase,
1412 Math::PlanePath::StaircaseAlternating, Math::PlanePath::Corner
1413 Math::PlanePath::CornerAlternating
1414
1415 Math::PlanePath::PyramidRows, Math::PlanePath::PyramidSides,
1416 Math::PlanePath::CellularRule, Math::PlanePath::CellularRule54,
1417 Math::PlanePath::CellularRule57, Math::PlanePath::CellularRule190,
1418 Math::PlanePath::UlamWarburton, Math::PlanePath::UlamWarburtonQuarter
1419
1420 Math::PlanePath::DiagonalRationals, Math::PlanePath::FactorRationals,
1421 Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree,
1422 Math::PlanePath::FractionsTree, Math::PlanePath::ChanTree,
1423 Math::PlanePath::CfracDigits, Math::PlanePath::CoprimeColumns,
1424 Math::PlanePath::DivisibleColumns, Math::PlanePath::WythoffArray,
1425 Math::PlanePath::WythoffPreliminaryTriangle,
1426 Math::PlanePath::PowerArray, Math::PlanePath::File
1427
1428 Math::PlanePath::LCornerTree, Math::PlanePath::LCornerReplicate,
1429 Math::PlanePath::ToothpickTree, Math::PlanePath::ToothpickReplicate,
1430 Math::PlanePath::ToothpickUpist, Math::PlanePath::ToothpickSpiral,
1431 Math::PlanePath::OneOfEight, Math::PlanePath::HTree
1432
1433 Math::NumSeq::PlanePathCoord, Math::NumSeq::PlanePathDelta,
1434 Math::NumSeq::PlanePathTurn, Math::NumSeq::PlanePathN
1435
1436 math-image, displaying various sequences on these paths.
1437
1438 examples/numbers.pl, to print all the paths.
1439
1440 Other Ways To Do It
1441 Math::Fractal::Curve, Math::Curve::Hilbert,
1442 Algorithm::SpatialIndex::Strategy::QuadTree
1443
1444 PerlMagick (module Image::Magick) demo scripts lsys.pl and tree.pl
1445
1447 <http://user42.tuxfamily.org/math-planepath/index.html>
1448
1449 <http://user42.tuxfamily.org/math-planepath/gallery.html>
1450
1452 Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
1453
1454 This file is part of Math-PlanePath.
1455
1456 Math-PlanePath is free software; you can redistribute it and/or modify
1457 it under the terms of the GNU General Public License as published by
1458 the Free Software Foundation; either version 3, or (at your option) any
1459 later version.
1460
1461 Math-PlanePath is distributed in the hope that it will be useful, but
1462 WITHOUT ANY WARRANTY; without even the implied warranty of
1463 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1464 General Public License for more details.
1465
1466 You should have received a copy of the GNU General Public License along
1467 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
1468
1469
1470
1471perl v5.34.0 2021-07-22 Math::PlanePath(3)