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 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. 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 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 what type of Gray code is used. The
148 choices are
149 "reflected" increment to radix-1 then decrement (default)
151 "modular" increment to radix-1 then cycle back to 0
152 For example in decimal,
154 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 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 In binary the modular and reflected forms are the same (see "Equivalent
180 Combinations" below).
181 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 Equivalent Combinations
188 Some option combinations are equivalent,
189 condition equivalent
191 --------- ----------
192 radix=2 modular==reflected
193 and TsF==Fs, Ts==FsT
194 radix>2 odd, reflected TsF==FsT, Ts==Fs, sT==sF
196 because T==F
197 radix>2 even, reflected TsF==Fs, Ts==FsT
199 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 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 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 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 The net effect for distinct paths is
228 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 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 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 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 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 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 A099896 N values by PeanoCurve radix=2 order
338 A100280 inverse permutation
339 apply_type="FsT", radix=3, gray_type=modular
341 A208665 N values on X=Y diagonal, base 9 digits 0,3,6
342 Gray code conversions themselves (not directly offered by the PlanePath
344 code here) are variously
345 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
357 Math::PlanePath, Math::PlanePath::ZOrderCurve,
358 Math::PlanePath::PeanoCurve, Math::PlanePath::CornerReplicate
359
361 <http://user42.tuxfamily.org/math-planepath/index.html>
362
364 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
365 This file is part of Math-PlanePath.
367 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 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 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/>.
380perl v5.30.0 2019-08-17 Math::PlanePath::GrayCode(3)