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 path 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.  Option "radix => $r" can select another radix.
54       This radix is used for both the Gray code and the digit splitting.  For
55       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 the type of Gray code.  The choices are
148
149           "reflected"     increment to radix-1 then decrement (default)
150           "modular"       increment to radix-1 then cycle back to 0
151
152       For example in decimal,
153
154           integer       Gray         Gray
155                      "reflected"   "modular"
156           -------    -----------   ---------
157              0            0            0
158              1            1            1
159              2            2            2
160            ...          ...          ...
161              8            8            8
162              9            9            9
163             10           19           19
164             11           18           10
165             12           17           11
166             13           16           12
167             14           15           13
168            ...          ...          ...
169             17           12           16
170             18           11           17
171             19           10           18
172
173       Notice on reaching "19" the reflected type runs the least significant
174       digit back down from 9 to 0, which is a reverse or reflection of the
175       preceding 0 to 9 upwards.  The modular form instead continues to
176       increment that least significant digit, wrapping around from 9 to 0.
177
178       In binary, the modular and reflected forms are the same (see
179       "Equivalent Combinations" below).
180
181       There's various other systematic ways to make a Gray code changing a
182       single digit successively.  But many ways are implicitly based on a
183       pre-determined fixed number of bits or digits, which doesn't suit an
184       unlimited path like here.
185
186   Equivalent Combinations
187       Some option combinations are equivalent,
188
189           condition                  equivalent
190           ---------                  ----------
191           radix=2                    modular==reflected
192                                      and TsF==Fs, Ts==FsT
193
194           radix>2 odd, reflected     TsF==FsT, Ts==Fs, sT==sF
195                                      because T==F
196
197           radix>2 even, reflected    TsF==Fs, Ts==FsT
198
199       In radix=2 binary, the "modular" and "reflected" Gray codes are the
200       same because there's only digits 0 and 1 so going forward or backward
201       is the same.
202
203       For odd radix and reflected Gray code, the "to Gray" and "from Gray"
204       operations are the same.  For example the following table is ternary
205       radix=3.  Notice how integer value 012 maps to Gray code 010, and in
206       turn integer 010 maps to Gray code 012.  All values are either pairs
207       like that or unchanged like 021.
208
209           integer      Gray
210                     "reflected"       (written in ternary)
211             000        000
212             001        001
213             002        002
214             010        012
215             011        011
216             012        010
217             020        020
218             021        021
219             022        022
220
221       For even radix and reflected Gray code, "TsF" is equivalent to "Fs",
222       and also "Ts" equivalent to "FsT".  This arises from the way the
223       reversing behaves when split across digits of two X,Y values.  (In
224       higher dimensions such as a split to 3-D X,Y,Z it's not the same.)
225
226       The net effect for distinct paths is
227
228           condition         distinct combinations
229           ---------         ---------------------
230           radix=2           four TsF==Fs, Ts==FsT, sT, sF
231           radix>2 odd       / three reflected TsF==FsT, Ts==Fs, sT==sF
232                             \ six modular TsF, Ts, Fs, FsT, sT, sF
233           radix>2 even      / four reflected TsF==Fs, Ts==FsT, sT, sF
234                             \ six modular TsF, Ts, Fs, FsT, sT, sF
235
236   Peano Curve
237       In "radix => 3" and other odd radices, the "reflected" Gray type gives
238       the Peano curve (see Math::PlanePath::PeanoCurve).  This is since the
239       "reflected" encoding is equivalent to Peano's "xk" and "yk"
240       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       TsF 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="Ts", radix=2
325             A309952    X coordinate (XOR bit pairs)
326
327           apply_type="sF", radix=2
328             A163233    N values by diagonals, same axis start
329             A163234     inverse permutation
330             A163235    N values by diagonals, opp axis start
331             A163236     inverse permutation
332             A163242    N sums along diagonals
333             A163478     those sums divided by 3
334
335             A163237    N values by diagonals, same axis, flip digits 2,3
336             A163238     inverse permutation
337             A163239    N values by diagonals, opp axis, flip digits 2,3
338             A163240     inverse permutation
339
340             A099896    N values by PeanoCurve radix=2 order
341             A100280     inverse permutation
342
343           apply_type="FsT", radix=3, gray_type=modular
344             A208665    N values on X=Y diagonal, base 9 digits 0,3,6
345
346       Gray code conversions themselves (not directly offered by the PlanePath
347       code here) are variously
348
349           A003188  binary
350           A014550  binary written in binary
351           A055975    increments
352           A006068    inverse, Gray->integer
353           A128173  ternary reflected (its own inverse)
354           A105530  ternary modular
355           A105529    inverse, Gray->integer
356           A003100  decimal reflected
357           A174025    inverse, Gray->integer
358           A098488  decimal modular
359           A226134    inverse, Gray->integer
360

SEE ALSO

362       Math::PlanePath, Math::PlanePath::ZOrderCurve,
363       Math::PlanePath::PeanoCurve, Math::PlanePath::CornerReplicate
364

HOME PAGE

366       <http://user42.tuxfamily.org/math-planepath/index.html>
367

LICENSE

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