1Math::PlanePath::PeanoDUisaegronCaolnst(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::PeanoDiagonals(3)
2
3
4

NAME

6       Math::PlanePath::PeanoDiagonals -- 3x3 self-similar quadrant traversal
7       across squares
8

SYNOPSIS

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

DESCRIPTION

18       This path is the Peano curve with segments going diagonally across unit
19       squares.
20
21           Giuseppe Peano, "Sur Une Courbe, Qui Remplit Toute Une Aire Plane",
22           Mathematische Annalen, volume 36, number 1, 1890, pages 157-160.
23           DOI 10.1007/BF01199438.
24           <https://link.springer.com/article/10.1007/BF01199438>,
25           <https://eudml.org/doc/157489>
26
27       Points N are at each corner of the squares, so even locations (X+Y
28       even),
29
30             9 |    61,425      63,423      65,421      79,407      81,405
31             8 | 60       58,62       64,68       66,78       76,80
32             7 |    55,59       57,69       67,71       73,77       75,87
33             6 | 54       52,56       38,70       36,72       34,74
34             5 |    49,53       39,51       37,41       31,35       33,129
35             4 | 48       46,50       40,44       30,42       28,32
36             3 |     7,47        9,45       11,43       25,29       27,135
37             2 |  6        4,8        10,14       12,24       22,26
38             1 |     1,5         3,15       13,17       19,23       21,141
39           Y=0 |  0         2          16          18          20
40               +----------------------------------------------------------
41                X=0   1     2     3     4     5     6     7     8     9
42
43       Moore (figure 3) draws this form, though here is transposed so first
44       unit squares go East.
45
46           E. H. Moore, "On Certain Crinkly Curves", Transactions of the
47           American Mathematical Society, volume 1, number 1, 1900, pages
48           72-90.
49
50           <http://www.ams.org/journals/tran/1900-001-01/S0002-9947-1900-1500526-4/>,
51           <http://www.ams.org/journals/tran/1900-001-04/S0002-9947-1900-1500428-3/>
52
53       Segments between the initial points can be illustrated,
54
55             |    \              \
56             +--- 47,7 ----+--- 45,9 --
57             |    ^ | \    |   ^  | \
58             |  /   |  \   |  /   |  v
59             | /    |   v  | /    |  ...
60             6 -----+---- 4,8 ----+--
61             | ^    |    / | ^    |
62             |   \  |   /  |   \  |
63             |    \ | v    |    \ |
64             +-----5,1 ----+---- 3,15
65             |   ^  | \    |   ^  |
66             |  /   |  \   |  /   |
67             | /    |   v  | /    |
68           N=0------+------2------+--
69
70       Segment N=0 to N=1 goes from the origin X=0,Y=0 up to X=1,Y=1, then N=2
71       is down again to X=2,Y=0, and so on.  The plain PeanoCurve is the
72       middle of each square, so points N + 1/2 here (and reckoning the first
73       such midpoint as the origin).
74
75       The rule for block reversals is described with PeanoCurve.  N is split
76       to an X and Y digit alternately.  If the sum of Y digits above is odd
77       then the X digit is reversed, and vice versa X odd is Y reversed.
78
79       A plain diagonal is North-East per N=0 to 1.  Diagonals are mirrored
80       according to the final sum of all digits.  If sum of Y digits is odd
81       then mirror horizontally.  If sum of X digits is odd then mirror
82       vertically.  Such mirroring is X+1 and/or Y+1 as compared to the plain
83       PeanoCurve.
84
85       An integer N is at the start of the segment with its final reversal.
86       Fractional N follows the diagonal across its unit square.
87
88       As noted above all locations are even (X+Y even).  Those on the axes
89       are visited once and all others twice.
90
91   Diamond Shape
92       Some authors take this diagonals form and raw it rotated -45 degrees so
93       that the segments are X,Y aligned, and the pattern fills a wedge shape
94       between diagonals X=Y and X=-Y (for X>=0).
95
96                6----7,47
97                |     |
98                |     |
99           0---1,5---4,8---9,45
100                |     |     |
101                |     |    ...
102                2----3,15
103
104       In terms of the coordinates here, this is (X+Y)/2, (Y-X)/2.
105
106   Even Radix
107       In an even radix, the mirror rule for diagonals across unit squares is
108       applied the same way.  But in this case the end of one segment does not
109       always coincide with the start of the next.
110
111             +---15,125----+---13,127-- 16 -----+----18,98-
112             |   /  | ^    |   /  | ^    | \    |   ^  | \
113             |  /   |  \   |  /   |  \   |  \   |  /   |  \
114             | v    |   \  | v    |   \  |   v  | /    |   v
115             +----- 9 --- 14 --- 11 --- 12 --- 17 -----+--  ...
116             |    ^ | \    |   ^  | \    |
117             |  /   |  \   |  /   |  \   |
118             | /    |   v  | /    |    v |
119             8 ---- 7 --- 10 ---- 5 -----+---
120             |   /  | ^    |   /  | ^    |
121             |  /   |  \   |  /   |  \   |         radix => 4
122             | v    |   \  | v    |   \  |
123             +----- 1 ---- 6 ---- 3 ---- 4 --
124             |   ^  | \    |   ^  | \    |
125             |  /   |  \   |  /   |  \   |
126             | /    |   v  | /    |   v  |
127           N=0------+----- 2 -----+------+---
128
129       The first row N=0 to N=3 goes left to right.  The next row N=4 to N=7
130       is a horizontal mirror image to go right to left.  N = 3.99.. < 4
131       follows its diagonal across its unit square, so approaches X=3.99,Y=0.
132       There is then a discontinuity up to N=4 at X=4,Y=1.
133
134       Block N=0 to N=15 repeats starting N=16, with vertical mirror image.
135       There is a bigger discontinuity between N=15 to N=16 (like there is in
136       even radix PeanoCurve).
137
138       Some double-visited points occur, such as N=15 and N=125 both at
139       X=1,Y=4.  This is when the 4x16 block N=0 to 64 is copied above,
140       mirrored horizontally.
141

FUNCTIONS

143       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
144       classes.
145
146       "$path = Math::PlanePath::PeanoDiagonals->new ()"
147       "$path = Math::PlanePath::PeanoDiagonals->new (radix => $r)"
148           Create and return a new path object.
149
150           The optional "radix" parameter gives the base for digit splitting.
151           The default is ternary, "radix => 3".
152
153       "($x,$y) = $path->n_to_xy ($n)"
154           Return the X,Y coordinates of point number $n on the path.  Points
155           begin at 0 and if "$n < 0" then the return is an empty list.
156
157           Fractional $n gives an X,Y position along the diagonals across unit
158           squares.
159
160       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
161           Return a range of N values which covers the rectangle with corners
162           at $x1,$y1 and $x2,$y2.  If the X,Y values are not integers then
163           the curve is treated as unit squares centred on each integer point
164           and squares which are partly covered by the given rectangle are
165           included.
166
167           In the current implementation, the returned range is an over-
168           estimate, so that $n_lo might be smaller than the smallest actually
169           in the rectangle, and $n_hi bigger than the actual biggest.
170
171   Level Methods
172       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
173           Return "(0, $radix**(2*$level) - 1)".
174

FORMULAS

176   N to Turn
177       The curve turns left or right 90 degrees at each point N >= 1.  The
178       turn is 90 degrees
179
180           turn(N) = (-1)^(N + number of low ternary 0s of N)
181                   = -1,1,1,1,-1,-1,-1,1,-1,1,-1,-1,-1,1,1,1,-1,1
182           by 90 degrees (+1 left, -1 right)
183
184       The power of -1 means left or right flip for each low ternary 0 of N,
185       and flip again if N is odd.  Odd N is an odd number of ternary 1
186       digits.
187
188       This formula follows from the turns in a new low base-9 digit.  For a
189       segment crossing a given unit square, the expanded segments have the
190       same start and end directions, so existing turns, now 9*N, are
191       unchanged.  Then 9*N+r goes as r in the base figure, but flipped L<->R
192       when N odd since blocks are mirrored alternately.
193
194           turn(9N)   = turn(N)
195           turn(9N+r) = turn(r)*(-1)^N         for  1 <= r <= 8
196
197       Or in terms of base 3, a single new low ternary digit is a transpose of
198       what's above, and the base figure turns r=1,2 are L<->R when N above is
199       odd.
200
201           turn(3N)   = - turn(N)
202           turn(3N+r) = turn(r)*(-1)^N         for r = 1 or 2
203
204       Similarly in any odd radix.
205

SEE ALSO

207       Math::PlanePath, Math::PlanePath::PeanoCurve,
208       Math::PlanePath::HilbertSides
209

HOME PAGE

211       <http://user42.tuxfamily.org/math-planepath/index.html>
212

LICENSE

214       Copyright 2019, 2020 Kevin Ryde
215
216       This file is part of Math-PlanePath.
217
218       Math-PlanePath is free software; you can redistribute it and/or modify
219       it under the terms of the GNU General Public License as published by
220       the Free Software Foundation; either version 3, or (at your option) any
221       later version.
222
223       Math-PlanePath is distributed in the hope that it will be useful, but
224       WITHOUT ANY WARRANTY; without even the implied warranty of
225       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
226       General Public License for more details.
227
228       You should have received a copy of the GNU General Public License along
229       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
230
231
232
233perl v5.34.0                      2021-07-22Math::PlanePath::PeanoDiagonals(3)
Impressum