1Math::PlanePath(3) User Contributed Perl Documentation Math::PlanePath(3)
2
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 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 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 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 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 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 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 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 QuintetCurve self-similar "+" traversal
87 QuintetCentres likewise but centres of squares
88 QuintetReplicate self-similar "+" tiling
89 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 SierpinskiCurve self-similar right-triangles
107 SierpinskiCurveStair self-similar right-triangles, stair-step
108 HIndexing self-similar right-triangles, squared up
109 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 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 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 And in the separate Math-PlanePath-Toothpick distribution
153 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 LCornerTree L-shape corner growth
160 LCornerReplicate same by replication rather than tree
161 OneOfEight
162 HTree H shapes replicated
163 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 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 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 Floating point NaNs (when available) give NaN, infinite, or empty/undef
178 returns, but again of some unspecified kind as yet.
179 Most of the classes can operate on overloaded number types as inputs
181 and give corresponding outputs.
182 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 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 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 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 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 my ($x,$y) = $path->n_to_xy (-123)
214 or next; # no negatives in $path
215 Paths start from "$path->n_start()" below, though some will give a
217 position for N=0 or N=-0.5 too.
218 "($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 + $n+1 == $next_x,$next_y
225 ^
226 |
227 | $dx = $next_x - $x
228 + $n == $x,$y $dy = $next_y - $y
229 $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 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 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 "$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 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 "$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 my $n = $path->xy_to_n(20,20);
264 if (! defined $n) {
265 next; # nothing at this X,Y
266 }
267 $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 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 "@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 my @n_list = $path->xy_to_n(20,20);
281 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 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 "@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 The return list includes $n itself. If there is no $n in the path
295 then return an empty list.
296 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 "$bool = $path->xy_is_visited ($x,$y)"
302 Return true if "$x,$y" is visited. This is equivalent to
303 defined($path->xy_to_n($x,$y))
305 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 "$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 The either() forms allow <$n> in either direction, so "$x1,$y1" to
320 "$x2,$y2" or the other way "$x2,$y2" to "$x1,$y1".
321 The n_list() forms return a list of all $n going between "$x1,$y1"
323 and "$x2,$y2". For example in "Math::PlanePath::CCurve" some
324 segments are traversed twice, once in each direction.
325 The possible N values at each X,Y are determined the same way as
327 for xy_to_n().
328 "($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 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 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 $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 $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 If there's no points in the rectangle then the return can be a
355 "crossed" range like "$n_lo=1", "$n_hi=0" (which makes a "foreach"
356 do no loops). But rect_to_n_range() may not always notice there's
357 no points in the rectangle and might instead return an over-
358 estimate.
359 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 Some classes have secret dubious undocumented support for N values
367 below this start (zero or negative), but n_start() is the intended
368 starting point.
369 "$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 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 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 "$arms = $path->arms_count()"
385 Return the number of arms in a "multi-arm" path.
386 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 "$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 "$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 For some classes the X or Y extent may depend on parameter values.
404 "$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 "$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 "$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 Various paths which go by rows have non-decreasing Y. For them
428 dy_minimum() is 0.
429 "$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 absdx_maximum() is simply max(dXmax,-dXmin), the biggest change
439 either positive or negative. absdy_maximum() similarly.
440 absdx_minimum() is 0 if dX=0 occurs anywhere in the path, which
442 means any vertical step. If X always changes then absdx_minimum()
443 will be something bigger than 0. absdy_minimum() likewise 0 if any
444 horizontal dY=0, or bigger if Y always changes.
445 "$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 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 \ 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 "$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 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 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 |
481 /|\ SumAbs = which diamond X,Y falls on
482 / | \
483 / | \
484 -----o-----
485 \ | /
486 \ | /
487 \|/
488 |
489 "$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 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 / 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 "$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 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 d=abs(X-Y) X=Y line
520 ^ /
521 \ /
522 \/
523 /\
524 / \
525 / \
526 o v
527 / d=abs(X-Y)
528 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 If the path is entirely below the X=Y line so X>=Y then X-Y>=0 and
534 absdiffxy_minimum() is the same as diffxy_minimum(). If the path
535 is entirely below the X=Y line then absdiffxy_minimum() is
536 "- diffxy_maximum()".
537 "$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 "$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 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 RSquared generally has no maximum since the paths usually extend
557 infinitely in some direction. rsquared_maximum() returns "undef"
558 in that case.
559 "($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 | * dX=2,dY=2
568 dX=-1,dY=1 * | /
569 \|/
570 ------+----* dX=1,dY=0
571 |
572 |
573 * dX=0,dY=-1
574 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 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 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 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 "$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 N+1 left
597 N-1 -------- N --> N+1 straight
599 N+1 right
601 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 "$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 "square" side 1 centred on $x,$y
613 "circle" diameter 1 centred on $x,$y
614 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 Tree Methods
620 Some paths are structured like a tree where each N has a parent and
621 possibly some children.
622 123
624 / | \
625 456 999 458
626 / / \
627 1000 1001 1005
628 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 "$bool = $path->is_tree()"
636 Return true if $path is a tree.
637 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 "@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 There could be no children either because $path is not a tree or
647 because there's no children at a particular $n.
648 "$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 If the tree is considered as a directed graph then this is the
654 "out-degree" of $n.
655 "$n_parent = $path->tree_n_parent($n)"
657 Return the parent node of $n, or "undef" if it has no parent.
658 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 "$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 The return is "undef" if there's no $n point or if $path is not a
667 tree.
668 "$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 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 "$n_lo = $path->tree_depth_to_n($depth)"
679 "$n_hi = $path->tree_depth_to_n_end($depth)"
680 "($n_lo, $n_hi) = $path->tree_depth_to_n_range ($depth)"
681 Return the first or last N, or both those N, for tree level $depth
682 in the path. If there's no such $depth or if $path is not a tree
683 then return "undef", or for tree_depth_to_n_range() return an empty
684 list.
685 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 $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 "$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 "$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 ... 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 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 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 "@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 "$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 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 "$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 This is the same as "tree_num_children_minimum()==0" since if
747 NumChildren=0 occurs then there are leaf nodes.
748 Some trees may have no leaf nodes, for example in the complete
750 binary tree of "RationalsTree" every node always has 2 children.
751 Level Methods
753 "level = $path->n_to_level($n)"
754 Return the replication level containing $n. The first level is 0.
755 "($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 my ($n_lo, $n_hi) = $path->level_to_n_range(6)
762 or print "no levels in this path";
763 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 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 {
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 "type" is a string, one of
791 "integer"
793 "enum"
794 "boolean"
795 "string"
796 "filename"
797 "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 For "enum" the "choices" field is the possible values, such as
803 { name => "flavour",
805 type => "enum",
806 choices => ["strawberry","chocolate"],
807 }
808 "minimum" and/or "maximum" are omitted if there's no hard limit on
810 the parameter.
811 "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 "$hashref = Math::PlanePath::Foo->parameter_info_hash()"
819 Return a hashref mapping parameter names "$info->{'name'}" to their
820 $info records.
821 { 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 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 foreach my $n ($path->n_start .. 100) {
841 my ($x,$y) = $path->n_to_xy($n);
842 print "$n $x,$y\n";
843 }
844 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 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 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 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 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 -X,Y flip horizontally (mirror image)
875 X,-Y flip vertically (across the X axis)
876 -Y,X rotate +90 degrees (anti-clockwise)
878 Y,-X rotate -90 degrees (clockwise)
879 -X,-Y rotate 180 degrees
880 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 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 For scaling and shifting see for example Transform::Canvas, and to
891 rotate as well see Geometry::AffineTransform.
892 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 Step Path
899 ---- ----
900 0 Rows, Columns (fixed widths)
901 1 Diagonals
902 2/2 DiagonalsOctant (2 rows for +2)
903 2 SacksSpiral, Corner, CornerAlternating,
904 PyramidSides, PyramidRows (default)
905 4 DiamondSpiral, AztecDiamondRings, Staircase
906 4/2 CellularRule54, CellularRule57,
907 DiagonalsAlternating (2 rows for +4)
908 5 PentSpiral, PentSpiralSkewed
909 5.65 PixelRings (average about 4*sqrt(2))
910 6 HexSpiral, HexSpiralSkewed, MPeaks,
911 MultipleRings (default)
912 6/2 CellularRule190 (2 rows for +6)
913 6.28 ArchimedeanChords (approaching 2*pi),
914 FilledRings (average 2*pi)
915 7 HeptSpiralSkewed
916 8 SquareSpiral, PyramidSpiral
917 16/2 StaircaseAlternating (up and back for +16)
918 9 TriangleSpiral, TriangleSpiralSkewed
919 12 AnvilSpiral
920 16 OctagramSpiral, ToothpickSpiral
921 19.74 TheodorusSpiral (approaching 2*pi^2)
922 32/4 KnightSpiral (4 loops 2-wide for +32)
923 64 DiamondArms (each arm)
924 72 GreekKeySpiral
925 128 SquareArms (each arm)
926 128/4 CretanLabyrinth (4 loops for +128)
927 216 HexArms (each arm)
928 totient CoprimeColumns, DiagonalRationals
930 numdivisors DivisibleColumns
931 various CellularRule
932 parameter MultipleRings, PyramidRows
934 The step determines which quadratic number sequences make straight
936 lines. For example the gap between successive perfect squares
937 increases by 2 each time (4 to 9 is +5, 9 to 16 is +7, 16 to 25 is +9,
938 etc), so the perfect squares make a straight line in the paths of step
939 2.
940 In general straight lines on stepped paths are quadratics
942 N = a*k^2 + b*k + c where a=step/2
944 The polygonal numbers are like this, with the (step+2)-gonal numbers
946 making a straight line on a "step" path. For example the 7-gonals
947 (heptagonals) are 5/2*k^2-3/2*k and make a straight line on the step=5
948 "PentSpiral". Or the 8-gonal octagonal numbers 6/2*k^2-4/2*k on the
949 step=6 "HexSpiral".
950 There are various interesting properties of primes in quadratic
952 progressions. Some quadratics seem to have more primes than others.
953 For example see "Lucky Numbers of Euler" in
954 Math::PlanePath::PyramidSides. Many quadratics have no primes at all,
955 or none above a certain point, either trivially if always a multiple of
956 2 etc, or by a more sophisticated reasoning. See "Step 3 Pentagonals"
957 in Math::PlanePath::PyramidRows for a factorization on the roots making
958 a no-primes gap.
959 A 4*step path splits a straight line in two, so for example the perfect
961 squares are a straight line on the step=2 "Corner" path, and then on
962 the step=8 "SquareSpiral" they instead fall on two lines (lower left
963 and upper right). In the bigger step there's one line of the even
964 squares (2k)^2 == 4*k^2 and another of the odd squares (2k+1)^2. The
965 gap between successive even squares increases by 8 each time and
966 likewise between odd squares.
967 Self-Similar Powers
969 The self-similar patterns such as "PeanoCurve" generally have a base
970 pattern which repeats at powers N=base^level or squares
971 N=(base*base)^level. Or some multiple or relationship to such a power
972 for things like "KochPeaks" and "GosperIslands".
973 Base Path
975 ---- ----
976 2 HilbertCurve, HilbertSides, HilbertSpiral,
977 ZOrderCurve (default), GrayCode (default),
978 BetaOmega, AR2W2Curve, HIndexing,
979 ImaginaryBase (default), ImaginaryHalf (default),
980 SierpinskiCurve, SierpinskiCurveStair,
981 CubicBase (default) CornerReplicate,
982 ComplexMinus (default), ComplexPlus (default),
983 ComplexRevolving, DragonCurve, DragonRounded,
984 DragonMidpoint, AlternatePaper, AlternatePaperMidpoint,
985 CCurve, DigitGroups (default), PowerArray (default)
986 3 PeanoCurve (default), PeanoDiagonals (default),
987 WunderlichSerpentine (default),WunderlichMeander,
988 KochelCurve, GosperIslands, GosperSide
989 SierpinskiTriangle, SierpinskiArrowhead,
990 SierpinskiArrowheadCentres,
991 TerdragonCurve, TerdragonRounded, TerdragonMidpoint,
992 AlternateTerdragon,
993 UlamWarburton, UlamWarburtonQuarter (each level)
994 4 KochCurve, KochPeaks, KochSnowflakes, KochSquareflakes,
995 LTiling,
996 5 QuintetCurve, QuintetCentres, QuintetReplicate,
997 DekkingCurve, DekkingCentres, CincoCurve,
998 R5DragonCurve, R5DragonMidpoint
999 7 Flowsnake, FlowsnakeCentres, GosperReplicate
1000 8 QuadricCurve, QuadricIslands
1001 9 SquareReplicate
1002 Fibonacci FibonacciWordFractal, WythoffArray
1003 parameter PeanoCurve, PeanoDiagonals, WunderlichSerpentine,
1004 ZOrderCurve, GrayCode, ImaginaryBase, ImaginaryHalf,
1005 CubicBase, ComplexPlus, ComplexMinus, DigitGroups,
1006 PowerArray
1007 Many number sequences plotted on these self-similar paths tend to be
1009 fairly random, or merely show the tiling or path layout rather than
1010 much about the number sequence. Sequences related to the base can make
1011 holes or patterns picking out parts of the path. For example numbers
1012 without a particular digit (or digits) in the relevant base show up as
1013 holes. See for example "Power of 2 Values" in
1014 Math::PlanePath::ZOrderCurve.
1015 Triangular Lattice
1017 Some paths are on triangular or "A2" lattice points like
1018 *---*---*---*---*---*
1020 / \ / \ / \ / \ / \ /
1021 *---*---*---*---*---*
1022 \ / \ / \ / \ / \ / \
1023 *---*---*---*---*---*
1024 / \ / \ / \ / \ / \ /
1025 *---*---*---*---*---*
1026 \ / \ / \ / \ / \ / \
1027 *---*---*---*---*---*
1028 / \ / \ / \ / \ / \ /
1029 *---*---*---*---*---*
1030 This is done in integer X,Y on a square grid by using every second
1032 square and offsetting alternate rows. This means sum X+Y even, ie. X,Y
1033 either both even or both odd, not of opposite parity.
1034 . * . * . * . * . * . *
1036 * . * . * . * . * . * .
1037 . * . * . * . * . * . *
1038 * . * . * . * . * . * .
1039 . * . * . * . * . * . *
1040 * . * . * . * . * . * .
1041 The X axis the and diagonals X=Y and X=-Y divide the plane into six
1043 equal parts in this grid.
1044 X=-Y X=Y
1046 \ /
1047 \ /
1048 \ /
1049 ----------------- X=0
1050 / \
1051 / \
1052 / \
1053 The diagonal X=3*Y is the middle of the first sixth, representing a
1055 twelfth of the plane.
1056 The resulting triangles are flatter than they should be. The triangle
1058 base is width=2 and top is height=1, whereas it would be height=sqrt(3)
1059 for an equilateral triangle. That sqrt(3) factor can be applied if
1060 desired,
1061 X, Y*sqrt(3) side length 2
1063 X/2, Y*sqrt(3)/2 side length 1
1065 Integer Y values have the advantage of fitting pixels on the usual kind
1067 of raster computer screen, and not losing precision in floating point
1068 results.
1069 If doing a general-purpose coordinate rotation then be sure to apply
1071 the sqrt(3) scale factor before rotating or the result will be skewed.
1072 60 degree rotations can be made within the integer X,Y coordinates
1073 directly as follows, all giving integer X,Y results.
1074 ( X-3Y)/2, ( X+Y)/2 rotate +60 (anti-clockwise)
1076 ( X+3Y)/2, (-X+Y)/2 rotate -60 (clockwise)
1077 (-X-3Y)/2, ( X-Y)/2 rotate +120
1078 (-X+3Y)/2, (-X-Y)/2 rotate -120
1079 -X,-Y rotate 180
1080 (X+3Y)/2, (X-Y)/2 mirror across the X=3*Y twelfth (30deg)
1082 The sqrt(3) factor can be worked into a hypotenuse radial distance
1084 calculation as follows if comparing distances from the origin.
1085 hypot = sqrt(X*X + 3*Y*Y)
1087 See for instance "TriangularHypot" which is triangular points ordered
1089 by this radial distance.
1090
1092 The formulas section in the POD of each class describes some of the
1093 calculations. This might be of interest even if the code is not.
1094 Triangular Calculations
1096 For a triangular lattice, the rotation formulas above allow
1097 calculations to be done in the rectangular X,Y coordinates which are
1098 the inputs and outputs of the PlanePath functions. Another way is to
1099 number vertically on a 60 degree angle with coordinates i,j,
1100 ...
1102 * * * 2
1103 * * * 1
1104 * * * j=0
1105 i=0 1 2
1106 These coordinates are sometimes used for hexagonal grids in board games
1108 etc. Using this internally can simplify rotations a little,
1109 -j, i+j rotate +60 (anti-clockwise)
1111 i+j, -i rotate -60 (clockwise)
1112 -i-j, i rotate +120
1113 j, -i-j rotate -120
1114 -i, -j rotate 180
1115 Conversions between i,j and the rectangular X,Y are
1117 X = 2*i + j i = (X-Y)/2
1119 Y = j j = Y
1120 A third coordinate k at a +120 degrees angle can be used too,
1122 k=0 k=1 k=2
1124 * * *
1125 * * *
1126 * * *
1127 0 1 2
1128 This is redundant in that it doesn't number anything i,j alone can't
1130 already, but it has the advantage of turning rotations into just sign
1131 changes and swaps,
1132 -k, i, j rotate +60
1134 j, k, -i rotate -60
1135 -j, -k, i rotate +120
1136 k, -i, -j rotate -120
1137 -i, -j, -k rotate 180
1138 The conversions between i,j,k and the rectangular X,Y are like the i,j
1140 above but with k worked in too.
1141 X = 2i + j - k i = (X-Y)/2 i = (X+Y)/2
1143 Y = j + k j = Y or j = 0
1144 k = 0 k = Y
1145 N to dX,dY -- Fractional
1147 n_to_dxdy() is the change from N to N+1, and is designed both for
1148 integer N and fractional N. For fractional N it can be convenient to
1149 calculate a dX,dY at floor(N) and at floor(N)+1 and then combine the
1150 two in proportion to frac(N).
1151 int+2
1153 |
1154 |
1155 N+1 \
1156 /| |
1157 / | |
1158 / | | frac
1159 / | |
1160 / | |
1161 / | /
1162 int-----N------int+1
1163 this_dX dX,dY next_dX
1164 this_dY next_dY
1165 |-------|------|
1167 frac 1-frac
1168 int = int(N)
1171 frac = N - int 0 <= frac < 1
1172 this_dX,this_dY at int
1174 next_dX,next_dY at int+1
1175 at fractional N
1177 dX = this_dX * (1-frac) + next_dX * frac
1178 dY = this_dY * (1-frac) + next_dY * frac
1179 This is combination of this_dX,this_dY and next_dX,next_dY in
1181 proportion to the distances from positions N to int+1 and from int+1 to
1182 N+1.
1183 The formulas can be rearranged to
1185 dX = this_dX + frac*(next_dX - this_dX)
1187 dY = this_dY + frac*(next_dY - this_dY)
1188 which is like dX,dY at the integer position plus fractional part of a
1190 turn or change to the next dX,dY.
1191 N to dX,dY -- Self-Similar
1193 For most of the self-similar paths such as "HilbertCurve", the change
1194 dX,dY is determined by following the state table transitions down
1195 through either all digits of N, or to the last non-9 digit, ie. drop
1196 any low digits equal to radix-1.
1197 Generally paths which are the edges of some tiling use all digits, and
1199 those which are the centres of a tiling stop at the lowest non-9. This
1200 can be seen for example in the "DekkingCurve" using all digits, whereas
1201 its "DekkingCentres" variant stops at the lowest non-24.
1202 Perhaps this all-digits vs low-non-9 would even characterize path style
1204 as edges or centres of a tiling, when a path is specified in some way
1205 that a tiling is not quite obvious.
1206
1208 The mandatory methods for a PlanePath subclass are
1209 n_to_xy()
1211 xy_to_n()
1212 xy_to_n_list() if multiple N's map to an X,Y
1213 rect_to_n_range()
1214 It sometimes happens that one of n_to_xy() or xy_to_n() is easier than
1216 the other but both should be implemented.
1217 n_to_xy() should do something sensible on fractional N. The suggestion
1219 is to make it an X,Y proportionally between integer N positions. It
1220 could be along a straight line or an arc as best suits the path. A
1221 straight line can be done simply by two calculations of the surrounding
1222 integer points, until it's clear how to work the fraction into the code
1223 directly.
1224 xy_to_n_list() has a base implementation calling plain xy_to_n() to
1226 give a single N at X,Y. If a path has multiple Ns at an X,Y (eg.
1227 "DragonCurve") then it must implement xy_to_n_list() to return all
1228 those Ns, and must also implement a plain xy_to_n() returning the first
1229 of them.
1230 rect_to_n_range() can initially be any convenient over-estimate. It
1232 should give N big enough that from there onwards all points are sure to
1233 be beyond the given X,Y rectangle.
1234 The following descriptive methods have base implementations
1236 n_start() 1
1238 class_x_negative() \ 1, so whole plane
1239 class_y_negative() /
1240 x_negative() calls class_x_negative()
1241 y_negative() calls class_x_negative()
1242 x_negative_at_n() undef \ as for no negatives
1243 y_negative_at_n() undef /
1244 The base n_start() starts at N=1. Paths which treat N as digits of
1246 some radix or where there's self-similar replication are often best
1247 started from N=0 instead since doing so puts nice powers-of-2 etc on
1248 the axes or diagonals.
1249 use constant n_start => 0; # digit or replication style
1251 Paths which use only parts of the plane should define
1253 class_x_negative() and/or class_y_negative() to false. For example if
1254 only the first quadrant X>=0,Y>=0 then
1255 use constant class_x_negative => 0;
1257 use constant class_y_negative => 0;
1258 If negativeness varies with path parameters then x_negative() and/or
1260 y_negative() follow those parameters and the class_() forms are whether
1261 any set of parameters ever gives negative.
1262 The following methods have base implementations calling n_to_xy(). A
1264 subclass can implement them directly if they can be done more
1265 efficiently.
1266 n_to_dxdy() calls n_to_xy() twice
1268 n_to_rsquared() calls n_to_xy()
1269 n_to_radius() sqrt of n_to_rsquared()
1270 "SacksSpiral" is an example of an easy n_to_rsquared().
1272 "TheodorusSpiral" is only slightly trickier. Unless a path has some
1273 sort of easy X^2+Y^2 then it might as well let the base implementation
1274 call n_to_xy().
1275 The way n_to_dxdy() supports fractional N can be a little tricky. One
1277 way is to calculate dX,dY on the integer N below and above and combine
1278 as described in "N to dX,dY -- Fractional". For some paths the
1279 calculation of turn or direction at ceil(N) can be worked into a
1280 calculation of the direction at floor(N) so not much more work.
1281 The following methods have base implementations calling xy_to_n(). A
1283 subclass might implement them directly if it can be done more
1284 efficiently.
1285 xy_is_visited() defined(xy_to_n($x,$y))
1287 xyxy_to_n() \
1288 xyxy_to_n_either() | calling xy_to_n_list()
1289 xyxy_to_n_list() |
1290 xyxy_to_n_list_either() /
1291 Paths such as "SquareSpiral" which fill the plane have xy_is_visited()
1293 always true, so for them
1294 use constant xy_is_visited => 1;
1296 For a tree path the following methods are mandatory
1298 tree_n_parent()
1300 tree_n_children()
1301 tree_n_to_depth()
1302 tree_depth_to_n()
1303 tree_num_children_list()
1304 tree_n_to_subheight()
1305 The other tree methods have base implementations,
1307 is_tree()
1309 Checks for n_start() having non-zero tree_n_to_num_children().
1310 Usually this suffices, expecting n_start() to be a root node and to
1311 have some children.
1312 tree_n_num_children()
1314 Calls tree_n_children() and counts the number of return values.
1315 Many trees can count the children with less work than calculating
1316 outright, for example "RationalsTree" is simply always 2 for
1317 N>=Nstart.
1318 tree_depth_to_n_end()
1320 Calls "tree_depth_to_n($depth+1)-1". This assumes that the depth
1321 level ends where the next begins. This is true for the various
1322 breadth-wise tree traversals, but anything interleaved etc will
1323 need its own implementation.
1324 tree_depth_to_n_range()
1326 Calls tree_depth_to_n() and tree_depth_to_n_end(). For some paths
1327 the row start and end, or start and width, might be calculated
1328 together more efficiently.
1329 tree_depth_to_width()
1331 Returns "tree_depth_to_n_end() - tree_depth_to_n() + 1". This
1332 suits breadth-wise style paths where all points at $depth are in a
1333 contiguous block. Any path not like that will need its own
1334 tree_depth_to_width().
1335 tree_num_children_minimum(), tree_num_children_maximum()
1337 Return the first and last values of tree_num_children_list() as the
1338 minimum and maximum.
1339 tree_any_leaf()
1341 Calls tree_num_children_minimum(). If the minimum "num_children"
1342 is 0 then there's leaf nodes.
1343
1345 Math::PlanePath::SquareSpiral, Math::PlanePath::PyramidSpiral,
1346 Math::PlanePath::TriangleSpiral, Math::PlanePath::TriangleSpiralSkewed,
1347 Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiral,
1348 Math::PlanePath::PentSpiralSkewed, Math::PlanePath::HexSpiral,
1349 Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed,
1350 Math::PlanePath::AnvilSpiral, Math::PlanePath::OctagramSpiral,
1351 Math::PlanePath::KnightSpiral, Math::PlanePath::CretanLabyrinth
1352 Math::PlanePath::HexArms, Math::PlanePath::SquareArms,
1354 Math::PlanePath::DiamondArms, Math::PlanePath::AztecDiamondRings,
1355 Math::PlanePath::GreekKeySpiral, Math::PlanePath::MPeaks
1356 Math::PlanePath::SacksSpiral, Math::PlanePath::VogelFloret,
1358 Math::PlanePath::TheodorusSpiral, Math::PlanePath::ArchimedeanChords,
1359 Math::PlanePath::MultipleRings, Math::PlanePath::PixelRings,
1360 Math::PlanePath::FilledRings, Math::PlanePath::Hypot,
1361 Math::PlanePath::HypotOctant, Math::PlanePath::TriangularHypot,
1362 Math::PlanePath::PythagoreanTree
1363 Math::PlanePath::PeanoCurve, Math::PlanePath::PeanoDiagonals,
1365 Math::PlanePath::WunderlichSerpentine,
1366 Math::PlanePath::WunderlichMeander, Math::PlanePath::HilbertCurve,
1367 Math::PlanePath::HilbertSides, Math::PlanePath::HilbertSpiral,
1368 Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode,
1369 Math::PlanePath::AR2W2Curve, Math::PlanePath::BetaOmega,
1370 Math::PlanePath::KochelCurve, Math::PlanePath::DekkingCurve,
1371 Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve
1372 Math::PlanePath::ImaginaryBase, Math::PlanePath::ImaginaryHalf,
1374 Math::PlanePath::CubicBase, Math::PlanePath::SquareReplicate,
1375 Math::PlanePath::CornerReplicate, Math::PlanePath::LTiling,
1376 Math::PlanePath::DigitGroups, Math::PlanePath::FibonacciWordFractal
1377 Math::PlanePath::Flowsnake, Math::PlanePath::FlowsnakeCentres,
1379 Math::PlanePath::GosperReplicate, Math::PlanePath::GosperIslands,
1380 Math::PlanePath::GosperSide
1381 Math::PlanePath::QuintetCurve, Math::PlanePath::QuintetCentres,
1383 Math::PlanePath::QuintetReplicate
1384 Math::PlanePath::KochCurve, Math::PlanePath::KochPeaks,
1386 Math::PlanePath::KochSnowflakes, Math::PlanePath::KochSquareflakes
1387 Math::PlanePath::QuadricCurve, Math::PlanePath::QuadricIslands
1389 Math::PlanePath::SierpinskiCurve,
1391 Math::PlanePath::SierpinskiCurveStair, Math::PlanePath::HIndexing
1392 Math::PlanePath::SierpinskiTriangle,
1394 Math::PlanePath::SierpinskiArrowhead,
1395 Math::PlanePath::SierpinskiArrowheadCentres
1396 Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded,
1398 Math::PlanePath::DragonMidpoint, Math::PlanePath::AlternatePaper,
1399 Math::PlanePath::AlternatePaperMidpoint,
1400 Math::PlanePath::TerdragonCurve, Math::PlanePath::TerdragonRounded,
1401 Math::PlanePath::TerdragonMidpoint,
1402 Math::PlanePath::AlternateTerdragon, Math::PlanePath::R5DragonCurve,
1403 Math::PlanePath::R5DragonMidpoint, Math::PlanePath::CCurve
1404 Math::PlanePath::ComplexPlus, Math::PlanePath::ComplexMinus,
1406 Math::PlanePath::ComplexRevolving
1407 Math::PlanePath::Rows, Math::PlanePath::Columns,
1409 Math::PlanePath::Diagonals, Math::PlanePath::DiagonalsAlternating,
1410 Math::PlanePath::DiagonalsOctant, Math::PlanePath::Staircase,
1411 Math::PlanePath::StaircaseAlternating, Math::PlanePath::Corner
1412 Math::PlanePath::CornerAlternating
1413 Math::PlanePath::PyramidRows, Math::PlanePath::PyramidSides,
1415 Math::PlanePath::CellularRule, Math::PlanePath::CellularRule54,
1416 Math::PlanePath::CellularRule57, Math::PlanePath::CellularRule190,
1417 Math::PlanePath::UlamWarburton, Math::PlanePath::UlamWarburtonQuarter
1418 Math::PlanePath::DiagonalRationals, Math::PlanePath::FactorRationals,
1420 Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree,
1421 Math::PlanePath::FractionsTree, Math::PlanePath::ChanTree,
1422 Math::PlanePath::CfracDigits, Math::PlanePath::CoprimeColumns,
1423 Math::PlanePath::DivisibleColumns, Math::PlanePath::WythoffArray,
1424 Math::PlanePath::WythoffPreliminaryTriangle,
1425 Math::PlanePath::PowerArray, Math::PlanePath::File
1426 Math::PlanePath::LCornerTree, Math::PlanePath::LCornerReplicate,
1428 Math::PlanePath::ToothpickTree, Math::PlanePath::ToothpickReplicate,
1429 Math::PlanePath::ToothpickUpist, Math::PlanePath::ToothpickSpiral,
1430 Math::PlanePath::OneOfEight, Math::PlanePath::HTree
1431 Math::NumSeq::PlanePathCoord, Math::NumSeq::PlanePathDelta,
1433 Math::NumSeq::PlanePathTurn, Math::NumSeq::PlanePathN
1434 math-image, displaying various sequences on these paths.
1436 examples/numbers.pl, to print all the paths.
1438 Other Ways To Do It
1440 Math::Fractal::Curve, Math::Curve::Hilbert,
1441 Algorithm::SpatialIndex::Strategy::QuadTree
1442 PerlMagick (module Image::Magick) demo scripts lsys.pl and tree.pl
1444
1446 <http://user42.tuxfamily.org/math-planepath/index.html>
1447 <http://user42.tuxfamily.org/math-planepath/gallery.html>
1449
1451 Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
1452 This file is part of Math-PlanePath.
1454 Math-PlanePath is free software; you can redistribute it and/or modify
1456 it under the terms of the GNU General Public License as published by
1457 the Free Software Foundation; either version 3, or (at your option) any
1458 later version.
1459 Math-PlanePath is distributed in the hope that it will be useful, but
1461 WITHOUT ANY WARRANTY; without even the implied warranty of
1462 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1463 General Public License for more details.
1464 You should have received a copy of the GNU General Public License along
1466 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
1467perl v5.36.0 2023-01-20 Math::PlanePath(3)