1Math::PlanePath::PeanoCUusrevre(C3o)ntributed Perl DocumMeanttha:t:iPolnanePath::PeanoCurve(3)
2
3
4

NAME

6       Math::PlanePath::PeanoCurve -- 3x3 self-similar quadrant traversal
7

SYNOPSIS

9        use Math::PlanePath::PeanoCurve;
10        my $path = Math::PlanePath::PeanoCurve->new;
11        my ($x, $y) = $path->n_to_xy (123);
12
13        # or another radix digits ...
14        my $path5 = Math::PlanePath::PeanoCurve->new (radix => 5);
15

DESCRIPTION

17       This path is an integer version of the curve described by Peano for
18       filling a unit square,
19
20           Guiseppe Peano, "Sur Une Courbe, Qui Remplit Toute Une Aire Plane",
21           Mathematische Annalen, volume 36, number 1, 1890, p157-160.  DOI
22           10.1007/BF01199438.
23           <http://www.springerlink.com/content/w232301n53960133/>
24
25       It traverses a quadrant of the plane one step at a time in a self-
26       similar 3x3 pattern,
27
28              8    60--61--62--63--64--65  78--79--80--...
29                    |                   |   |
30              7    59--58--57  68--67--66  77--76--75
31                            |   |                   |
32              6    54--55--56  69--70--71--72--73--74
33                    |
34              5    53--52--51  38--37--36--35--34--33
35                            |   |                   |
36              4    48--49--50  39--40--41  30--31--32
37                    |                   |   |
38              3    47--46--45--44--43--42  29--28--27
39                                                    |
40              2     6---7---8---9--10--11  24--25--26
41                    |                   |   |
42              1     5---4---3  14--13--12  23--22--21
43                            |   |                   |
44             Y=0    0---1---2  15--16--17--18--19--20
45
46                  X=0   1   2   3   4   5   6   7   8   9 ...
47
48       The start is an S shape of the nine points N=0 to N=8, and then nine of
49       those groups are put together in the same S configuration.  The sub-
50       parts are flipped horizontally and/or vertically to make the starts and
51       ends adjacent, so 8 is next to 9, 17 next to 18, etc,
52
53           60,61,62 --- 63,64,65     78,79,80
54           59,58,57     68,67,55     77,76,75
55           54,55,56     69,70,71 --- 72,73,74
56            |
57            |
58           53,52,51     38,37,36 --- 35,34,33
59           48,49,50     39,40,41     30,31,32
60           47,46,45 --- 44,43,42     29,28,27
61                                            |
62                                            |
63            6,7,8  ----  9,10,11     24,25,26
64            3,4,5       12,13,14     23,22,21
65            0,1,2       15,16,17 --- 18,19,20
66
67       The process repeats, tripling in size each time.
68
69       Within a power-of-3 square, 3x3, 9x9, 27x27, 81x81 etc (3^k)x(3^k) at
70       the origin, all the N values 0 to 3^(2*k)-1 are within the square.  The
71       top right corner 8, 80, 728, etc is the 3^(2*k)-1 maximum in each.
72
73       Because each step is by 1, the distance along the curve between two X,Y
74       points is the difference in their N values as given by "xy_to_n()".
75
76   Radix
77       The "radix" parameter can do the calculation in a base other than 3,
78       using the same kind of direction reversals.  For example radix 5 gives
79       5x5 groups,
80
81            radix => 5
82
83             4  |  20--21--22--23--24--25--26--27--28--29
84                |   |                                   |
85             3  |  19--18--17--16--15  34--33--32--31--30
86                |                   |   |
87             2  |  10--11--12--13--14  35--36--37--38--39
88                |   |                                   |
89             1  |   9-- 8-- 7-- 6-- 5  44--43--42--41--40
90                |                   |   |
91            Y=0 |   0-- 1-- 2-- 3-- 4  45--46--47--48--49--50-...
92                |
93                +----------------------------------------------
94                  X=0   1   2   3   4   5   6   7   8   9  10
95
96       If the radix is even then the ends of each group don't join up.  For
97       example in radix 4 N=15 isn't next to N=16, nor N=31 to N=32, etc.
98
99            radix => 4
100
101             3  |  15--14--13--12  16--17--18--19
102                |               |               |
103             2  |   8-- 9--10--11  23--22--21--20
104                |   |               |
105             1  |   7-- 6-- 5-- 4  24--25--26--27
106                |               |               |
107            Y=0 |   0-- 1-- 2-- 3  31--30--29--28  32--33-...
108                |
109                +------------------------------------------
110                  X=0   1   2   4   5   6   7   8   9  10
111
112       Even sizes can be made to join using other patterns, but this module is
113       just Peano's digit construction.  For joining up in 2x2 groupings see
114       "HilbertCurve" (which is essentially the only way to join up in 2x2).
115       For bigger groupings there's various ways.
116
117   Unit Square
118       Peano's original form was for filling a unit square by mapping a number
119       T in the range 0<T<1 to a pair of X,Y coordinates 0<X<1 and 0<Y<1.  The
120       curve is continuous and every such X,Y is reached, so it fills the unit
121       square.  A unit cube or higher dimension can be filled similarly by
122       developing three or more coordinates X,Y,Z, etc.  Georg Cantor had
123       shown a line is equivalent to the plane, Peano's mapping is a
124       continuous way to do that.
125
126       The code here could be pressed into service for a fractional T to X,Y
127       by multiplying up by a power of 9 to desired precision then dividing X
128       and Y back by the same power of 3 (perhaps swapping X,Y for which one
129       should be the first ternary digit).  Note that if T is a binary
130       floating point then a power of 3 division will round off in general
131       since 1/3 is not exactly representable.  (See "HilbertCurve" or
132       "ZOrderCurve" for binary mappings.)
133
134   Diagonal Lines
135       Moore in
136
137           E. H. Moore, "On Certain Crinkly Curves", Trans. Am. Math. Soc.,
138           volume 1, number 1, 1900, pages 72-90.
139
140           <http://www.ams.org/journals/tran/1900-001-01/S0002-9947-1900-1500526-4/>
141           <http://www.ams.org/tran/1900-001-01/S0002-9947-1900-1500526-4/S0002-9947-1900-1500526-4.pdf>
142
143           <http://www.ams.org/journals/tran/1900-001-04/S0002-9947-1900-1500428-3/>
144           <http://www.ams.org/journals/tran/1900-001-04/S0002-9947-1900-1500428-3/S0002-9947-1900-1500428-3.pdf>
145
146       draws the curve as a base shape
147
148                +-----+
149                |     |
150           -----+-----+-----
151                |     |
152                +-----+
153
154       with each line segment replaced by the same for the next level (with
155       suitable mirror image in odd segments).
156
157       The is equivalent to the square form by drawing diagonal lines
158       alternately in the direction of the leading diagonal or opposite
159       diagonal, per the ".."  marked lines in the following.
160
161           +--------+--------+--------+        +--------+--------+--------+
162           |     .. | ..     |     .. |        |        |        |        |
163           |6  ..   |7  ..   |8  ..   |        |    6--------7--------8   |
164           | ..     |     .. | ..     |        |    |   |        |        |
165           +--------+--------+--------+        +----|---+--------+--------+
166           | ..     |     .. | ..     |        |    |   |        |        |
167           |   ..  5|   ..  4|   ..  3|        |    5--------4--------3   |
168           |     .. | ..     |     .. |        |        |        |    |   |
169           +--------+--------+--------+        +--------+--------+----|---+
170           |     .. | ..     |     .. |        |        |        |    |   |
171           |0  ..   |1  ..   |2  ..   |        |    0--------1--------2   |
172           | ..     |     .. | ..     |        |        |        |        |
173           +--------+--------+--------+        +--------+--------+--------+
174
175           X==Y mod 2 "even" points leading-diagonal  "/"
176           X!=Y mod 2 "odd"  points opposite-diagonal "\"
177
178       Rounding off the corners of the diagonal form so they don't touch can
179       help show the equivalence,
180
181             -----7        /
182            /      \      /
183           6        -----8
184           |
185           |        4-----
186            \      /      \
187             5-----        3
188                           |
189             -----1        |
190            /      \      /
191           0        -----2
192
193   Power of 3 Patterns
194       Plotting sequences of values with some connection to ternary digits or
195       powers of 3 will usually give the most interesting patterns on the
196       Peano curve.  For example the Mephisto waltz sequence
197       (Math::NumSeq::MephistoWaltz) makes diamond shapes,
198
199           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
200           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
201             *** **   *** ** **   *  ***   *  ***   *  *  *** **
202            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
203             *** **   *** ** **   *  ***   *  ***   *  *  *** **
204           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
205             *** **   *** ** **   *  ***   *  ***   *  *  *** **
206            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
207           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
208           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
209           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
210            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
211             *** **   *** ** **   *  ***   *  ***   *  *  *** **
212            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
213           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
214            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
215             *** **   *** ** **   *  ***   *  ***   *  *  *** **
216           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
217             *** **   *** ** **   *  ***   *  ***   *  *  *** **
218            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
219           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
220           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
221           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
222            ** ***  *  *   ***  *   ** ** ***  *  *   ***  *   **
223           **   *  ***   *  *  *** **   *** **   *** ** **   *  *
224           *  *   ** ** ***   ** ***  *  *   ** ** ***   ** ***
225             *** **   *** ** **   *  ***   *  ***   *  *  *** **
226
227       This arises from each 3x3 block in the Mephisto waltz being one of two
228       shapes which are then flipped by the Peano pattern
229
230           * * _                     _ _ *
231           * _ _           or        _ * *    (inverse)
232           _ _ *                     * * _
233
234           0,0,1, 0,0,1, 1,1,0       1,1,0, 1,1,0, 0,0,1
235

FUNCTIONS

237       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
238       classes.
239
240       "$path = Math::PlanePath::PeanoCurve->new ()"
241       "$path = Math::PlanePath::PeanoCurve->new (radix => $integer)"
242           Create and return a new path object.
243
244           The optional "radix" parameter gives the base for digit splitting.
245           The default is ternary "radix => 3".
246
247       "($x,$y) = $path->n_to_xy ($n)"
248           Return the X,Y coordinates of point number $n on the path.  Points
249           begin at 0 and if "$n < 0" then the return is an empty list.
250
251           Fractional positions give an X,Y position along a straight line
252           between the integer positions.  Integer positions are always just 1
253           apart either horizontally or vertically, so the effect is that the
254           fraction part appears either added to or subtracted from X or Y.
255
256       "$n = $path->xy_to_n ($x,$y)"
257           Return an integer point number for coordinates "$x,$y".  Each
258           integer N is considered the centre of a unit square and an "$x,$y"
259           within that square returns N.
260
261       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
262           Return a range of N values which occur in a rectangle with corners
263           at $x1,$y1 and $x2,$y2.  If the X,Y values are not integers then
264           the curve is treated as unit squares centred on each integer point
265           and squares which are partly covered by the given rectangle are
266           included.
267
268           The returned range is exact, meaning $n_lo and $n_hi are the
269           smallest and biggest in the rectangle.
270
271   Level Methods
272       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
273           Return "(0, $radix**(2*$level) - 1)".
274

FORMULAS

276   N to X,Y
277       Peano's calculation is based on putting base-3 digits of N alternately
278       to X or Y.  From the high end of N a digit is appended to Y then the
279       next appended to X.  Beginning at an even digit position in N makes the
280       last digit go to X so the first N=0,1,2 goes along the X axis.
281
282       At each stage a "complement" state is maintained for X and for Y.  When
283       complemented the digit is reversed to 2 - digit, so 0,1,2 becomes
284       2,1,0.  This reverses the direction so points like N=12,13,14 shown
285       above go to the left, or groups like 9,10,11 then 12,13,14 then
286       15,16,17 go downwards.
287
288       The complement is calculated by adding the digits from N which went to
289       the other one of X or Y.  So the X complement is the sum of digits
290       which have gone to Y so far.  Conversely the Y complement is the sum of
291       digits put to X.  If the complement sum is odd then the reversal is
292       done.  A bitwise XOR can be used instead of a sum to accumulate
293       odd/even-ness the same way as a sum.
294
295       When forming the complement state the original digits from N are added,
296       before applying any complementing for putting them to X or Y.  If the
297       radix is odd, like the default 3, then complementing doesn't change it
298       mod 2 so either before or after is fine, but if the radix is even then
299       it's not the same.
300
301       It also works to take the base-3 digits of N from low to high,
302       generating low to high digits in X and Y.  When an odd digit is put to
303       X then the low digits of Y so far must be complemented as 22..22 - Y
304       (the 22..22 value being all 2s in base 3, ie. 3^k-1).  Conversely if an
305       odd digit is put to Y then X must be complemented.  With this approach
306       the high digit position in N doesn't have to be found, but instead peel
307       off digits of N from the low end.  But the subtract to complement is
308       then more work if using bignums.
309
310   X,Y to N
311       The X,Y to N calculation can be done by an inverse of either the high
312       to low or low to high methods above.  In both cases digits are put
313       alternately from X and Y onto N, with complement as necessary.
314
315       For the low to high approach it's not easy to complement just the X
316       digits in the N constructed so far, but it works to build and
317       complement the X and Y digits separately then at the end interleave to
318       make the final N.  Complementing is the ternary equivalent of an XOR in
319       binary.  On a ternary machine some trit-twiddling could no doubt do it.
320
321       For the low to high with even radix the complementing is also tricky
322       since changing the accumulated X affects the digits of Y below that,
323       and vice versa.  What's the rule?  Is it alternate digits which end up
324       complemented?  In any case the current "xy_to_n()" code goes high to
325       low which is easier, but means breaking the X,Y inputs into arrays of
326       digits before beginning.
327
328   N to abs(dX),abs(dY)
329       The curve goes horizontally or vertically according to the number of
330       trailing "2" digits when N is written in ternary,
331
332           N trailing 2s   direction     abs(dX)     abs(dY)
333           -------------   ---------     -------
334             even          horizontal       1          0
335             odd           vertical         0          1
336
337       For example N=5 is "12" in ternary has 1 trailing "2" which is odd so
338       the step from N=5 to N=6 is vertical.
339
340       This works because when stepping from N to N+1 a carry propagates
341       through the trailing 2s to increment the digit above.  Digits go
342       alternately to X or Y so odd or even trailing 2s put that carry into an
343       X digit or Y digit.
344
345                 X Y X Y X
346           N   ... 2 2 2 2
347           N+1   1 0 0 0 0  carry propagates
348
349   Rectangle to N Range
350       An easy over-estimate of the maximum N in a region can be had by going
351       to the next bigger (3^k)x(3^k) square enclosing the region.  This means
352       the biggest X or Y rounded up to the next power of 3 (perhaps using
353       "log()" if you trust its accuracy), so
354
355           find k with 3^k > max(X,Y)
356           N_hi = 3^(2k) - 1
357
358       An exact N range can be found by following the "high to low" N to X,Y
359       procedure above.  Start with the easy over-estimate to find a 3^(2k)
360       ternary digit position in N bigger than the desired region, then choose
361       a digit 0,1,2 for X, the biggest which overlaps some of the region.  Or
362       if there's an X complement then the smallest digit is the biggest N,
363       again whichever overlaps the region.  Then likewise for a digit of Y,
364       etc.
365
366       Biggest and smallest N must maintain separate complement states as they
367       track down different N digits.  A single loop can be used since there's
368       the same "2k" many digits of N to consider for both.
369
370       The N range of any shape can be done this way, not just a rectangle
371       like "rect_to_n_range()".  The procedure only depends on asking whether
372       a one-third sub-part of X or Y overlaps the target region or not.
373

OEIS

375       This path is in Sloane's Online Encyclopedia of Integer Sequences in
376       several forms,
377
378           <http://oeis.org/A163528> (etc)
379
380           A163528    X coordinate
381           A163529    Y coordinate
382           A163530    X+Y coordinate sum
383           A163531    X^2+Y^2 square of distance from origin
384           A163532    dX, change in X -1,0,1
385           A163533    dY, change in Y -1,0,1
386           A014578    abs(dX) from n-1 to n, 1=horiz 0=vertical
387                        thue-morse count low 0-bits + 1 mod 2
388           A182581    abs(dY) from n-1 to n, 0=horiz 1=vertical
389                        thue-morse count low 0-bits mod 2
390           A163534    direction of each step (up,down,left,right)
391           A163535    direction, transposed X,Y
392           A163536    turn 0=straight,1=right,2=left
393           A163537    turn, transposed X,Y
394           A163342    diagonal sums
395           A163479    diagonal sums divided by 6
396
397           A163480    N on X axis
398           A163481    N on Y axis
399           A163343    N on X=Y diagonal, 0,4,8,44,40,36,etc
400           A163344    N on X=Y diagonal divided by 4
401           A007417    N+1 of positions of horizontals, ternary even trailing 0s
402           A145204    N+1 of positions of verticals, ternary odd trailing 0s
403
404           A163332    Peano N -> ZOrder radix=3 N mapping
405                        and vice versa since is self-inverse
406           A163333    with ternary digit swaps before and after
407
408       And taking X,Y points by the Diagonals sequence, then the value of the
409       following sequences is the N of the Peano curve at those positions.
410
411           A163334    numbering by diagonals, from same axis as first step
412           A163336    numbering by diagonals, from opposite axis
413           A163338    A163334 + 1, Peano starting from N=1
414           A163340    A163336 + 1, Peano starting from N=1
415
416       "Math::PlanePath::Diagonals" numbers points from the Y axis down, which
417       is the opposite axis to the Peano curve first step along the X axis, so
418       a plain "Diagonals" -> "PeanoCurve" is the "opposite axis" form
419       A163336.
420
421       These sequences are permutations of the integers since all X,Y
422       positions of the first quadrant are reached eventually.  The inverses
423       are as follows.  They can be thought of taking X,Y positions in the
424       Peano curve order and then asking what N the Diagonals would put there.
425
426           A163335    inverse of A163334
427           A163337    inverse of A163336
428           A163339    inverse of A163338
429           A163341    inverse of A163340
430

SEE ALSO

432       Math::PlanePath, Math::PlanePath::HilbertCurve,
433       Math::PlanePath::ZOrderCurve, Math::PlanePath::AR2W2Curve,
434       Math::PlanePath::BetaOmega, Math::PlanePath::CincoCurve,
435       Math::PlanePath::KochelCurve, Math::PlanePath::WunderlichMeander
436
437       Math::PlanePath::KochCurve
438

HOME PAGE

440       <http://user42.tuxfamily.org/math-planepath/index.html>
441

LICENSE

443       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
444
445       This file is part of Math-PlanePath.
446
447       Math-PlanePath is free software; you can redistribute it and/or modify
448       it under the terms of the GNU General Public License as published by
449       the Free Software Foundation; either version 3, or (at your option) any
450       later version.
451
452       Math-PlanePath is distributed in the hope that it will be useful, but
453       WITHOUT ANY WARRANTY; without even the implied warranty of
454       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
455       General Public License for more details.
456
457       You should have received a copy of the GNU General Public License along
458       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
459
460
461
462perl v5.28.0                      2017-12-03    Math::PlanePath::PeanoCurve(3)
Impressum