1Math::PlanePath::GrayCoUdsee(r3)Contributed Perl DocumenMtaatthi:o:nPlanePath::GrayCode(3)
2
6 Math::PlanePath::GrayCode -- Gray code coordinates
7
9 use Math::PlanePath::GrayCode;
10 my $path = Math::PlanePath::GrayCode->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path is a mapping of N to X,Y using Gray codes.
16 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 The default is the form by Faloutsos which is an X,Y split in binary
37 reflected Gray code.
38 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 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 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 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 radix => 4
58 |
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 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 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 "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 "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 apply_type => "Ts"
92 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 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 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 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 apply_type => "sF"
126 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 Gray Type
147 The "gray_type" option selects the type of Gray code. The choices are
148 "reflected" increment to radix-1 then decrement (default)
150 "modular" increment to radix-1 then cycle back to 0
151 For example in decimal,
153 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 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 In binary, the modular and reflected forms are the same (see
179 "Equivalent Combinations" below).
180 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 Equivalent Combinations
187 Some option combinations are equivalent,
188 condition equivalent
190 --------- ----------
191 radix=2 modular==reflected
192 and TsF==Fs, Ts==FsT
193 radix>2 odd, reflected TsF==FsT, Ts==Fs, sT==sF
195 because T==F
196 radix>2 even, reflected TsF==Fs, Ts==FsT
198 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 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 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 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 The net effect for distinct paths is
227 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 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 radix => 3, gray_type => "reflected"
243 |
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
258 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
259 classes.
260 "$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 "($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 "$n = $path->n_start ()"
271 Return the first N on the path, which is 0.
272 Level Methods
274 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
275 Return "(0, $radix**(2*$level) - 1)".
276
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 count_low_0_bits(floor((N+1)/2))
285 if even then turn 90 left
286 if odd then turn 180 reverse
287 Or equivalently
289 floor((N+1)/2) lowest non-zero digit in base 4,
291 1 or 3 = turn 90 left
292 2 = turn 180 reverse
293 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 See "N to Turn" in Math::PlanePath::KochCurve for similar turns based
299 on low zero bits (but by +60 and -120 degrees).
300
302 This path is in Sloane's Online Encyclopedia of Integer Sequences in a
303 few forms,
304 <http://oeis.org/A163233> (etc)
306 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 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 apply_type="Ts", radix=2
325 A309952 X coordinate (XOR bit pairs)
326 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 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 A099896 N values by PeanoCurve radix=2 order
341 A100280 inverse permutation
342 apply_type="FsT", radix=3, gray_type=modular
344 A208665 N values on X=Y diagonal, base 9 digits 0,3,6
345 Gray code conversions themselves (not directly offered by the PlanePath
347 code here) are variously
348 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
362 Math::PlanePath, Math::PlanePath::ZOrderCurve,
363 Math::PlanePath::PeanoCurve, Math::PlanePath::CornerReplicate
364
366 <http://user42.tuxfamily.org/math-planepath/index.html>
367
369 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
370 Kevin Ryde
371 This file is part of Math-PlanePath.
373 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 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 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/>.
386perl v5.32.1 2021-01-27 Math::PlanePath::GrayCode(3)