Math::PlanePath::CornerReplicate(3pm)

1Math::PlanePath::CornerURseeprliCcoantter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::CornerReplicate(3)
2
3
4

NAME

6       Math::PlanePath::CornerReplicate -- replicating U parts
7

SYNOPSIS

9        use Math::PlanePath::CornerReplicate;
10        my $path = Math::PlanePath::CornerReplicate->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This path is a self-similar replicating corner fill with 2x2 blocks.
15       It's sometimes called a "U order" since the base N=0 to N=3 is like a
16       "U" (sideways).
17
18            7  | 63--62  59--58  47--46  43--42
19               |      |       |       |       |
20            6  | 60--61  56--57  44--45  40--41
21               |          |               |
22            5  | 51--50  55--54  35--34  39--38
23               |      |       |       |       |
24            4  | 48--49  52--53  32--33  36--37
25               |                  |
26            3  | 15--14  11--10  31--30  27--26
27               |      |       |       |       |
28            2  | 12--13   8-- 9  28--29  24--25
29               |          |               |
30            1  |  3-- 2   7-- 6  19--18  23--22
31               |      |       |       |       |
32           Y=0 |  0-- 1   4-- 5  16--17  20--21
33               +--------------------------------
34                 X=0  1   2   3   4   5   6   7
35
36       The pattern is the initial N=0 to N=3 section,
37
38           +-------+-------+
39           |       |       |
40           |   3   |   2   |
41           |       |       |
42           +-------+-------+
43           |       |       |
44           |   0   |   1   |
45           |       |       |
46           +-------+-------+
47
48       It repeats as 2x2 blocks arranged in the same pattern, then 4x4 blocks,
49       etc.  There's no rotations or reflections within sub-parts.
50
51       X axis N=0,1,4,5,16,17,etc is all the integers which use only digits 0
52       and 1 in base 4.  For example N=17 is 101 in base 4.
53
54       Y axis N=0,3,12,15,48,etc is all the integers which use only digits 0
55       and 3 in base 4.  For example N=51 is 303 in base 4.
56
57       The X=Y diagonal N=0,2,8,10,32,34,etc is all the integers which use
58       only digits 0 and 2 in base 4.
59
60       The X axis is the same as the "ZOrderCurve".  The Y axis here is the
61       X=Y diagonal of the "ZOrderCurve", and conversely the X=Y diagonal here
62       is the Y axis of the "ZOrderCurve".
63
64       The N value at a given X,Y is converted to or from the "ZOrderCurve" by
65       transforming base-4 digit values 2<->3.  This can be done by a bitwise
66       "X xor Y".  When Y has a 1-bit the xor swaps 2<->3 in N.
67
68           ZOrder X  = CRep X xor CRep Y
69           ZOrder Y  = CRep Y
70
71           CRep X  = ZOrder X xor ZOrder Y
72           CRep Y  = ZOrder Y
73
74       See Math::PlanePath::LCornerReplicate for a rotating corner form.
75
76   Level Ranges
77       A given replication extends to
78
79           Nlevel = 4^level - 1
80           0 <= X < 2^level
81           0 <= Y < 2^level
82
83   Hamming Distance
84       The Hamming distance between two integers X and Y is the number of bit
85       positions where the two values differ when written in binary.  In this
86       corner replicate each bit-pair of N becomes a bit of X and a bit of Y,
87
88              N      X   Y
89           ------   --- ---
90           0 = 00    0   0
91           1 = 01    1   0     <- difference 1 bit
92           2 = 10    1   1
93           3 = 11    0   1     <- difference 1 bit
94
95       So the Hamming distance is the number of base4 bit-pairs of N which are
96       01 or 11.  Counting bit positions from 0 for least significant bit,
97       this is the 1-bits in even positions,
98
99           HammingDist(X,Y) = count 1-bits at even bit positions in N
100                            = 0,1,0,1, 1,2,1,2, 0,1,0,1, 1,2,1,2, ... (A139351)
101

FUNCTIONS

103       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
104       classes.
105
106       "$path = Math::PlanePath::CornerReplicate->new ()"
107           Create and return a new path object.
108
109       "($x,$y) = $path->n_to_xy ($n)"
110           Return the X,Y coordinates of point number $n on the path.  Points
111           begin at 0 and if "$n < 0" then the return is an empty list.
112
113       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
114           The returned range is exact, meaning $n_lo and $n_hi are the
115           smallest and biggest in the rectangle.
116
117   Level Methods
118       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
119           Return "(0, 4**$level - 1)".
120

FORMULAS

122   N to dX,dY
123       The change dX,dY is given by N in base 4 count trailing 3s and the
124       digit above those trailing 3s.
125
126           N = ...[d]333...333      base 4
127                     \--exp--/
128
129       When N to N+1 crosses between 4^k blocks it goes as follows.  Within a
130       block the pattern is the same, since there's no rotations or transposes
131       etc.
132
133           N, N+1        X      Y        dX       dY       dSum     dDiffXY
134           --------   -----  -------   -----  --------    ------    -------
135           033..33       0    2^k-1      2^k  -(2^k-1)        +1    2*2^k-1
136           100..00      2^k       0
137
138           133..33      2^k    2^k-1       0       +1         +1       -1
139           200..00      2^k    2^k
140
141           133..33      2^k  2*2^k-1    -2^k     1-2^k   -(2^k-1)      -1
142           200..00       0     2^k
143
144           133..33       0   2*2^k-1   2*2^k -(2*2^k-1)       +1    4*2^k-1
145           200..00    2*2^k      0
146
147       It can be noted dSum=dX+dY the change in X+Y is at most +1, taking
148       values 1, -1, -3, -7, -15, etc.  The crossing from block 2 to 3 drops
149       back, such as at N=47="233" to N=48="300".  Everywhere else it advances
150       by +1 anti-diagonal.
151
152       The difference dDiffXY=dX-dY the change in X-Y decreases at most -1,
153       taking similar values -1, 1, 3, 7, 15, etc but in a different order to
154       dSum.
155

OEIS

157       This path is in Sloane's Online Encyclopedia of Integer Sequences as
158
159           <http://oeis.org/A000695> (etc)
160
161           A059906    Y coordinate
162           A059905    X xor Y, being ZOrderCurve X
163           A139351    HammingDist(X,Y), count 1-bits at even positions in N
164
165           A000695    N on X axis, base 4 digits 0,1 only
166           A001196    N on Y axis, base 4 digits 0,3 only
167           A062880    N on diagonal, base 4 digits 0,2 only
168           A163241    permutation base-4 flip 2<->3,
169                        converts N to ZOrderCurve N, and back
170
171           A048647    permutation N at transpose Y,X
172                        base4 digits 1<->3
173

HOME PAGE

180       <http://user42.tuxfamily.org/math-planepath/index.html>
181

LICENSE

183       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
184
185       This file is part of Math-PlanePath.
186
187       Math-PlanePath is free software; you can redistribute it and/or modify
188       it under the terms of the GNU General Public License as published by
189       the Free Software Foundation; either version 3, or (at your option) any
190       later version.
191
192       Math-PlanePath is distributed in the hope that it will be useful, but
193       WITHOUT ANY WARRANTY; without even the implied warranty of
194       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
195       General Public License for more details.
196
197       You should have received a copy of the GNU General Public License along
198       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
199
200
201
202perl v5.30.0                      2019-08-17Math::PlanePath::CornerReplicate(3)