1Math::PlanePath::PeanoDUisaegronCaolnst(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::PeanoDiagonals(3)
2
6 Math::PlanePath::PeanoDiagonals -- 3x3 self-similar quadrant traversal
7 across squares
8
10 use Math::PlanePath::PeanoDiagonals;
11 my $path = Math::PlanePath::PeanoDiagonals->new;
12 my ($x, $y) = $path->n_to_xy (123);
13 # or another radix digits ...
15 my $path5 = Math::PlanePath::PeanoDiagonals->new (radix => 5);
16
18 This path is the Peano curve with segments going diagonally across unit
19 squares.
20 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 Points N are at each corner of the squares, so even locations (X+Y
28 even),
29 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 Moore (figure 3) draws this form, though here is transposed so first
44 unit squares go East.
45 E. H. Moore, "On Certain Crinkly Curves", Transactions of the
47 American Mathematical Society, volume 1, number 1, 1900, pages
48 72-90.
49 <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 Segments between the initial points can be illustrated,
54 | \ \
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 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 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 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 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 As noted above all locations are even (X+Y even). Those on the axes
89 are visited once and all others twice.
90 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 6----7,47
97 | |
98 | |
99 0---1,5---4,8---9,45
100 | | |
101 | | ...
102 2----3,15
103 In terms of the coordinates here, this is (X+Y)/2, (Y-X)/2.
105 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 +---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 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 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 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
143 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
144 classes.
145 "$path = Math::PlanePath::PeanoDiagonals->new ()"
147 "$path = Math::PlanePath::PeanoDiagonals->new (radix => $r)"
148 Create and return a new path object.
149 The optional "radix" parameter gives the base for digit splitting.
151 The default is ternary, "radix => 3".
152 "($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 Fractional $n gives an X,Y position along the diagonals across unit
158 squares.
159 "($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 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 Level Methods
172 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
173 Return "(0, $radix**(2*$level) - 1)".
174
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 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 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 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 turn(9N) = turn(N)
195 turn(9N+r) = turn(r)*(-1)^N for 1 <= r <= 8
196 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 turn(3N) = - turn(N)
202 turn(3N+r) = turn(r)*(-1)^N for r = 1 or 2
203 Similarly in any odd radix.
205
207 Math::PlanePath, Math::PlanePath::PeanoCurve,
208 Math::PlanePath::HilbertSides
209
211 <http://user42.tuxfamily.org/math-planepath/index.html>
212
214 Copyright 2019, 2020 Kevin Ryde
215 This file is part of Math-PlanePath.
217 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 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 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/>.
230perl v5.34.0 2021-07-22Math::PlanePath::PeanoDiagonals(3)