1Math::PlanePath::GrayCoUdsee(r3)Contributed Perl DocumenMtaatthi:o:nPlanePath::GrayCode(3)
2
3
4

NAME

6       Math::PlanePath::GrayCode -- Gray code coordinates
7

SYNOPSIS

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

DESCRIPTION

15       This is a mapping of N to X,Y using Gray codes.
16
17             7  |  63-62 57-56 39-38 33-32
18                |      |  |        |  |
19             6  |  60-61 58-59 36-37 34-35
20                |
21             5  |  51-50 53-52 43-42 45-44
22                |      |  |        |  |
23             4  |  48-49 54-55 40-41 46-47
24                |
25             3  |  15-14  9--8 23-22 17-16
26                |      |  |        |  |
27             2  |  12-13 10-11 20-21 18-19
28                |
29             1  |   3--2  5--4 27-26 29-28
30                |      |  |        |  |
31            Y=0 |   0--1  6--7 24-25 30-31
32                |
33                +-------------------------
34                  X=0  1  2  3  4  5  6  7
35
36       The default is the form by Faloutsos which is an X,Y split in binary
37       reflected Gray code.
38
39           Christos Faloutsos, "Gray Codes for Partial Match and Range
40           Queries", IEEE Transactions on Software Engineering (TSE), volume
41           14, number 10, October 1988, pages 1381-1393.  DOI 10.1109/32.6184
42
43       N is converted to a Gray code, then split by bits to X,Y, and those X,Y
44       converted back from Gray to integer indices.  Stepping from N to N+1
45       changes just one bit of the Gray code and therefore changes just one of
46       X or Y each time.
47
48       Y axis N=0,3,12,15,48,etc are values with only digits 0,3 in base 4.  X
49       axis N=0,1,6,7,24,25,etc are values 2k and 2k+1 where k uses only
50       digits 0,3 in base 4.
51
52   Radix
53       The default is binary.  The "radix => $r" option can select another
54       radix.  This is used for both the Gray code and the digit splitting.
55       For example "radix => 4",
56
57           radix => 4
58
59             |
60           127-126-125-124  99--98--97--96--95--94--93--92  67--66--65--64
61                         |   |                           |   |
62           120-121-122-123 100-101-102-103  88--89--90--91  68--69--70--71
63             |                           |   |                           |
64           119-118-117-116 107-106-105-104  87--86--85--84  75--74--73--72
65                         |   |                           |   |
66           112-113-114-115 108-109-110-111  80--81--82--83  76--77--78--79
67
68            15--14--13--12  19--18--17--16  47--46--45--44  51--50--49--48
69                         |   |                           |   |
70             8-- 9--10--11  20--21--22--23  40--41--42--43  52--53--54--55
71             |                           |   |                           |
72             7-- 6-- 5-- 4  27--26--25--24  39--38--37--36  59--58--57--56
73                         |   |                           |   |
74             0-- 1-- 2-- 3  28--29--30--31--32--33--34--35  60--61--62--63
75
76   Apply Type
77       Option "apply_type => $str" controls how Gray codes are applied to N
78       and X,Y.  It can be one of
79
80           "TsF"    to Gray, split, from Gray  (default)
81           "Ts"     to Gray, split
82           "Fs"     from Gray, split
83           "FsT"    from Gray, split, to Gray
84            "sT"    split, to Gray
85            "sF"    split, from Gray
86
87       "T" means integer-to-Gray, "F" means integer-from-Gray, and omitted
88       means no transformation.  For example the following is "Ts" which means
89       N to Gray then split, leaving Gray coded values for X,Y.
90
91           apply_type => "Ts"
92
93            7  |  51--50  52--53  44--45  43--42
94               |       |       |       |       |
95            6  |  48--49  55--54  47--46  40--41
96               |
97            5  |  60--61  59--58  35--34  36--37  ...-66
98               |       |       |       |       |       |
99            4  |  63--62  56--57  32--33  39--38  64--65
100               |
101            3  |  12--13  11--10  19--18  20--21
102               |       |       |       |       |
103            2  |  15--14   8-- 9  16--17  23--22
104               |
105            1  |   3-- 2   4-- 5  28--29  27--26
106               |       |       |       |       |
107           Y=0 |   0-- 1   7-- 6  31--30  24--25
108               |
109               +---------------------------------
110                 X=0   1   2   3   4   5   6   7
111
112       This "Ts" is quite attractive because a step from N to N+1 changes just
113       one bit in X or Y alternately, giving 2-D single-bit changes.  For
114       example N=19 at X=4 followed by N=20 at X=6 is a single bit change in
115       X.
116
117       N=0,2,8,10,etc on the leading diagonal X=Y is numbers using only digits
118       0,2 in base 4.  N=0,3,15,12,etc on the Y axis is numbers using only
119       digits 0,3 in base 4, but in a Gray code order.
120
121       The "Fs", "FsT" and "sF" forms effectively treat the input N as a Gray
122       code and convert from it to integers, either before or after split.
123       For "Fs" the effect is little Z parts in various orientations.
124
125           apply_type => "sF"
126
127            7  |  32--33  37--36  52--53  49--48
128               |    /       \       /       \
129            6  |  34--35  39--38  54--55  51--50
130               |
131            5  |  42--43  47--46  62--63  59--58
132               |    \       /       \       /
133            4  |  40--41  45--44  60--61  57--56
134               |
135            3  |   8-- 9  13--12  28--29  25--24
136               |    /       \       /       \
137            2  |  10--11  15--14  30--31  27--26
138               |
139            1  |   2-- 3   7-- 6  22--23  19--18
140               |    \       /       \       /
141           Y=0 |   0-- 1   5-- 4  20--21  17--16
142               |
143               +---------------------------------
144                 X=0   1   2   3   4   5   6   7
145
146   Gray Type
147       The "gray_type" option selects what type of Gray code is used.  The
148       choices are
149
150           "reflected"     increment to radix-1 then decrement (default)
151           "modular"       increment to radix-1 then cycle back to 0
152
153       For example in decimal,
154
155           integer       Gray         Gray
156                      "reflected"   "modular"
157           -------    -----------   ---------
158              0            0            0
159              1            1            1
160              2            2            2
161            ...          ...          ...
162              8            8            8
163              9            9            9
164             10           19           19
165             11           18           10
166             12           17           11
167             13           16           12
168             14           15           13
169            ...          ...          ...
170             17           12           16
171             18           11           17
172             19           10           18
173
174       Notice on reaching "19" the reflected type runs the least significant
175       digit downwards from 9 to 0, which is a reverse or reflection of the
176       preceding 0 to 9 upwards.  The modular form instead continues to
177       increment that least significant digit, wrapping around from 9 to 0.
178
179       In binary the modular and reflected forms are the same (see "Equivalent
180       Combinations" below).
181
182       There's various other systematic ways to make a Gray code changing a
183       single digit successively.  But many ways are implicitly based on a
184       pre-determined fixed number of bits or digits, which doesn't suit an
185       unlimited path as given here.
186
187   Equivalent Combinations
188       Some option combinations are equivalent,
189
190           condition                  equivalent
191           ---------                  ----------
192           radix=2                    modular==reflected
193                                      and TsF==Fs, Ts==FsT
194
195           radix>2 odd, reflected     TsF==FsT, Ts==Fs, sT==sF
196                                      because T==F
197
198           radix>2 even, reflected    TsF==Fs, Ts==FsT
199
200       In radix=2 binary the "modular" and "reflected" Gray codes are the same
201       because there's only digits 0 and 1 so going forward or backward is the
202       same.
203
204       For odd radix and reflected Gray code, the "to Gray" and "from Gray"
205       operations are the same.  For example the following table is ternary
206       radix=3.  Notice how integer value 012 maps to Gray code 010, and in
207       turn integer 010 maps to Gray code 012.  All values are either pairs
208       like that or unchanged like 021.
209
210           integer      Gray
211                     "reflected"       (written in ternary)
212             000       000
213             001       001
214             002       002
215             010       012
216             011       011
217             012       010
218             020       020
219             021       021
220             022       022
221
222       For even radix and reflected Gray code, "TsF" is equivalent to "Fs",
223       and also "Ts" equivalent to "FsT".  This arises from the way the
224       reversing behaves when split across digits of two X,Y values.  (In
225       higher dimensions such as a split to 3-D X,Y,Z it's not the same.)
226
227       The net effect for distinct paths is
228
229           condition         distinct combinations
230           ---------         ---------------------
231           radix=2           four TsF==Fs, Ts==FsT, sT, sF
232           radix>2 odd       / three reflected TsF==FsT, Ts==Fs, sT==sF
233                             \ six modular TsF, Ts, Fs, FsT, sT, sF
234           radix>2 even      / four reflected TsF==Fs, Ts==FsT, sT, sF
235                             \ six modular TsF, Ts, Fs, FsT, sT, sF
236
237   Peano Curve
238       In "radix => 3" and other odd radices the "reflected" Gray type gives
239       the Peano curve (see Math::PlanePath::PeanoCurve).  The "reflected"
240       encoding is equivalent to Peano's "xk" and "yk" complementing.
241
242           radix => 3, gray_type => "reflected"
243
244            |
245           53--52--51  38--37--36--35--34--33
246                    |   |                   |
247           48--49--50  39--40--41  30--31--32
248            |                   |   |
249           47--46--45--44--43--42  29--28--27
250                                            |
251            6-- 7-- 8-- 9--10--11  24--25--26
252            |                   |   |
253            5-- 4-- 3  14--13--12  23--22--21
254                    |   |                   |
255            0-- 1-- 2  15--16--17--18--19--20
256

FUNCTIONS

258       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
259       classes.
260
261       "$path = Math::PlanePath::GrayCode->new ()"
262       "$path = Math::PlanePath::GrayCode->new (radix => $r, apply_type =>
263       $str, gray_type => $str)"
264           Create and return a new path object.
265
266       "($x,$y) = $path->n_to_xy ($n)"
267           Return the X,Y coordinates of point number $n on the path.  Points
268           begin at 0 and if "$n < 0" then the return is an empty list.
269
270       "$n = $path->n_start ()"
271           Return the first N on the path, which is 0.
272
273   Level Methods
274       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
275           Return "(0, $radix**(2*$level) - 1)".
276

FORMULAS

278   Turn
279       The turns in the default binary TsF curve are either to the left +90 or
280       a reverse 180.  For example at N=2 the curve turns left, then at N=3 it
281       reverses back 180 to go to N=4.  The turn is given by the low zero bits
282       of (N+1)/2,
283
284           count_low_0_bits(floor((N+1)/2))
285             if even then turn 90 left
286             if odd  then turn 180 reverse
287
288       Or equivalently
289
290           floor((N+1)/2) lowest non-zero digit in base 4,
291             1 or 3 = turn 90 left
292             2      = turn 180 reverse
293
294       The 180 degree reversals are all horizontal.  They occur because at
295       those N the three N-1,N,N+1 converted to Gray code have the same bits
296       at odd positions and therefore the same Y coordinate.
297
298       See "N to Turn" in Math::PlanePath::KochCurve for similar turns based
299       on low zero bits (but by +60 and -120 degrees).
300

OEIS

302       This path is in Sloane's Online Encyclopedia of Integer Sequences in a
303       few forms,
304
305           <http://oeis.org/A163233> (etc)
306
307           apply_type="TsF" (="Fs"), radix=2  (the defaults)
308             A059905    X xor Y
309             A039963    turn sequence, 1=+90 left, 0=180 reverse
310             A035263    turn undoubled, at N=2n and N=2n+1
311             A065882    base4 lowest non-zero,
312                          turn undoubled 1,3=left 2=180rev at N=2n,2n+1
313             A003159    (N+1)/2 of positions of Left turns,
314                          being n with even number of low 0 bits
315             A036554    (N+1)/2 of positions of Right turns
316                          being n with odd number of low 0 bits
317
318       The turn sequence goes in pairs, so N=1 and N=2 left then N=3 and N=4
319       reverse.  A039963 includes that repetition, A035263 is just one copy of
320       each and so is the turn at each pair N=2k and N=2k+1.  There's many
321       sequences like A065882 which when taken mod2 equal the "count low
322       0-bits odd/even" which is the same undoubled turn sequence.
323
324           apply_type="sF", radix=2
325             A163233    N values by diagonals, same axis start
326             A163234     inverse permutation
327             A163235    N values by diagonals, opp axis start
328             A163236     inverse permutation
329             A163242    N sums along diagonals
330             A163478     those sums divided by 3
331
332             A163237    N values by diagonals, same axis, flip digits 2,3
333             A163238     inverse permutation
334             A163239    N values by diagonals, opp axis, flip digits 2,3
335             A163240     inverse permutation
336
337             A099896    N values by PeanoCurve radix=2 order
338             A100280     inverse permutation
339
340           apply_type="FsT", radix=3, gray_type=modular
341             A208665    N values on X=Y diagonal, base 9 digits 0,3,6
342
343       Gray code conversions themselves (not directly offered by the PlanePath
344       code here) are variously
345
346           A003188  binary
347           A014550  binary with values written in binary
348           A006068    inverse, Gray->integer
349           A128173  ternary reflected (its own inverse)
350           A105530  ternary modular
351           A105529    inverse, Gray->integer
352           A003100  decimal reflected
353           A174025    inverse, Gray->integer
354           A098488  decimal modular
355

SEE ALSO

357       Math::PlanePath, Math::PlanePath::ZOrderCurve,
358       Math::PlanePath::PeanoCurve, Math::PlanePath::CornerReplicate
359

HOME PAGE

361       <http://user42.tuxfamily.org/math-planepath/index.html>
362

LICENSE

364       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
365
366       This file is part of Math-PlanePath.
367
368       Math-PlanePath is free software; you can redistribute it and/or modify
369       it under the terms of the GNU General Public License as published by
370       the Free Software Foundation; either version 3, or (at your option) any
371       later version.
372
373       Math-PlanePath is distributed in the hope that it will be useful, but
374       WITHOUT ANY WARRANTY; without even the implied warranty of
375       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
376       General Public License for more details.
377
378       You should have received a copy of the GNU General Public License along
379       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
380
381
382
383perl v5.30.1                      2020-01-30      Math::PlanePath::GrayCode(3)
Impressum