Provided by: libmath-planepath-perl_129-1_all 
NAME
Math::PlanePath::PeanoDiagonals -- 3x3 self-similar quadrant traversal across squares
SYNOPSIS
use Math::PlanePath::PeanoDiagonals;
my $path = Math::PlanePath::PeanoDiagonals->new;
my ($x, $y) = $path->n_to_xy (123);
# or another radix digits ...
my $path5 = Math::PlanePath::PeanoDiagonals->new (radix => 5);
DESCRIPTION
This path is the Peano curve with segments going diagonally across unit squares.
Giuseppe Peano, "Sur Une Courbe, Qui Remplit Toute Une Aire Plane", Mathematische
Annalen, volume 36, number 1, 1890, pages 157-160. DOI 10.1007/BF01199438.
<https://link.springer.com/article/10.1007/BF01199438>, <https://eudml.org/doc/157489>
Points N are at each corner of the squares, so even locations (X+Y even),
9 | 61,425 63,423 65,421 79,407 81,405
8 | 60 58,62 64,68 66,78 76,80
7 | 55,59 57,69 67,71 73,77 75,87
6 | 54 52,56 38,70 36,72 34,74
5 | 49,53 39,51 37,41 31,35 33,129
4 | 48 46,50 40,44 30,42 28,32
3 | 7,47 9,45 11,43 25,29 27,135
2 | 6 4,8 10,14 12,24 22,26
1 | 1,5 3,15 13,17 19,23 21,141
Y=0 | 0 2 16 18 20
+----------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9
Moore (figure 3) draws this form, though here is transposed so first unit squares go East.
E. H. Moore, "On Certain Crinkly Curves", Transactions of the American Mathematical
Society, volume 1, number 1, 1900, pages 72-90.
<http://www.ams.org/journals/tran/1900-001-01/S0002-9947-1900-1500526-4/>,
<http://www.ams.org/journals/tran/1900-001-04/S0002-9947-1900-1500428-3/>
Segments between the initial points can be illustrated,
| \ \
+--- 47,7 ----+--- 45,9 --
| ^ | \ | ^ | \
| / | \ | / | v
| / | v | / | ...
6 -----+---- 4,8 ----+--
| ^ | / | ^ |
| \ | / | \ |
| \ | v | \ |
+-----5,1 ----+---- 3,15
| ^ | \ | ^ |
| / | \ | / |
| / | v | / |
N=0------+------2------+--
Segment N=0 to N=1 goes from the origin X=0,Y=0 up to X=1,Y=1, then N=2 is down again to
X=2,Y=0, and so on. The plain PeanoCurve is the middle of each square, so points N + 1/2
here (and reckoning the first such midpoint as the origin).
The rule for block reversals is described with PeanoCurve. N is split to an X and Y digit
alternately. If the sum of Y digits above is odd then the X digit is reversed, and vice
versa X odd is Y reversed.
A plain diagonal is North-East per N=0 to 1. Diagonals are mirrored according to the
final sum of all digits. If sum of Y digits is odd then mirror horizontally. If sum of X
digits is odd then mirror vertically. Such mirroring is X+1 and/or Y+1 as compared to the
plain PeanoCurve.
An integer N is at the start of the segment with its final reversal. Fractional N follows
the diagonal across its unit square.
As noted above all locations are even (X+Y even). Those on the axes are visited once and
all others twice.
Diamond Shape
Some authors take this diagonals form and raw it rotated -45 degrees so that the segments
are X,Y aligned, and the pattern fills a wedge shape between diagonals X=Y and X=-Y (for
X>=0).
6----7,47
| |
| |
0---1,5---4,8---9,45
| | |
| | ...
2----3,15
In terms of the coordinates here, this is (X+Y)/2, (Y-X)/2.
Even Radix
In an even radix, the mirror rule for diagonals across unit squares is applied the same
way. But in this case the end of one segment does not always coincide with the start of
the next.
+---15,125----+---13,127-- 16 -----+----18,98-
| / | ^ | / | ^ | \ | ^ | \
| / | \ | / | \ | \ | / | \
| v | \ | v | \ | v | / | v
+----- 9 --- 14 --- 11 --- 12 --- 17 -----+-- ...
| ^ | \ | ^ | \ |
| / | \ | / | \ |
| / | v | / | v |
8 ---- 7 --- 10 ---- 5 -----+---
| / | ^ | / | ^ |
| / | \ | / | \ | radix => 4
| v | \ | v | \ |
+----- 1 ---- 6 ---- 3 ---- 4 --
| ^ | \ | ^ | \ |
| / | \ | / | \ |
| / | v | / | v |
N=0------+----- 2 -----+------+---
The first row N=0 to N=3 goes left to right. The next row N=4 to N=7 is a horizontal
mirror image to go right to left. N = 3.99.. < 4 follows its diagonal across its unit
square, so approaches X=3.99,Y=0. There is then a discontinuity up to N=4 at X=4,Y=1.
Block N=0 to N=15 repeats starting N=16, with vertical mirror image. There is a bigger
discontinuity between N=15 to N=16 (like there is in even radix PeanoCurve).
Some double-visited points occur, such as N=15 and N=125 both at X=1,Y=4. This is when
the 4x16 block N=0 to 64 is copied above, mirrored horizontally.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
"$path = Math::PlanePath::PeanoDiagonals->new ()"
"$path = Math::PlanePath::PeanoDiagonals->new (radix => $r)"
Create and return a new path object.
The optional "radix" parameter gives the base for digit splitting. The default is
ternary, "radix => 3".
"($x,$y) = $path->n_to_xy ($n)"
Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if
"$n < 0" then the return is an empty list.
Fractional $n gives an X,Y position along the diagonals across unit squares.
"($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
Return a range of N values which covers the rectangle with corners at $x1,$y1 and
$x2,$y2. If the X,Y values are not integers then the curve is treated as unit squares
centred on each integer point and squares which are partly covered by the given
rectangle are included.
In the current implementation, the returned range is an over-estimate, so that $n_lo
might be smaller than the smallest actually in the rectangle, and $n_hi bigger than
the actual biggest.
Level Methods
"($n_lo, $n_hi) = $path->level_to_n_range($level)"
Return "(0, $radix**(2*$level) - 1)".
FORMULAS
N to Turn
The curve turns left or right 90 degrees at each point N >= 1. The turn is 90 degrees
turn(N) = (-1)^(N + number of low ternary 0s of N)
= -1,1,1,1,-1,-1,-1,1,-1,1,-1,-1,-1,1,1,1,-1,1
by 90 degrees (+1 left, -1 right)
The power of -1 means left or right flip for each low ternary 0 of N, and flip again if N
is odd. Odd N is an odd number of ternary 1 digits.
This formula follows from the turns in a new low base-9 digit. For a segment crossing a
given unit square, the expanded segments have the same start and end directions, so
existing turns, now 9*N, are unchanged. Then 9*N+r goes as r in the base figure, but
flipped L<->R when N odd since blocks are mirrored alternately.
turn(9N) = turn(N)
turn(9N+r) = turn(r)*(-1)^N for 1 <= r <= 8
Or in terms of base 3, a single new low ternary digit is a transpose of what's above, and
the base figure turns r=1,2 are L<->R when N above is odd.
turn(3N) = - turn(N)
turn(3N+r) = turn(r)*(-1)^N for r = 1 or 2
Similarly in any odd radix.
SEE ALSO
Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertSides
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2019, 2020 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it under the terms
of the GNU General Public License as published by the Free Software Foundation; either
version 3, or (at your option) any later version.
Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-
PlanePath. If not, see <http://www.gnu.org/licenses/>.