gistools/geometry/s2/
coords_internal.rs

1// The canonical Hilbert traversal order looks like an inverted 'U':
2// the subcells are visited in the order (0,0), (0,1), (1,1), (1,0).
3// The following tables encode the traversal order for various
4// orientations of the Hilbert curve (axes swapped and/or directions
5// of the axes reversed).
6
7/// Together these flags define a cell orientation.  If 'kSwapMask'
8/// is true, then canonical traversal order is flipped around the
9/// diagonal (i.e. i and j are swapped with each other).  If
10pub const K_SWAP_MASK: u8 = 0x01;
11/// 'kInvertMask' is true, then the traversal order is rotated by 180
12/// degrees (i.e. the bits of i and j are inverted, or equivalently,
13/// the axis directions are reversed).
14pub const K_INVERT_MASK: u8 = 0x02;
15
16/// kIJtoPos[orientation][ij] -> pos
17///
18/// Given a cell orientation and the (i,j)-index of a subcell (0=(0,0),
19/// 1=(0,1), 2=(1,0), 3=(1,1)), return the order in which this subcell is
20/// visited by the Hilbert curve (a position in the range [0..3]).
21pub const K_IJTO_POS: [[usize; 4]; 4] = [
22    // (0,0) (0,1) (1,0) (1,1)
23    [0, 1, 3, 2], // canonical order
24    [0, 3, 1, 2], // axes swapped
25    [2, 3, 1, 0], // bits inverted
26    [2, 1, 3, 0], // swapped & inverted
27];
28
29/// kPosToIJ[orientation][pos] -> ij
30///
31/// Return the (i,j) index of the subcell at the given position 'pos' in the
32/// Hilbert curve traversal order with the given orientation.  This is the
33/// inverse of the previous table:
34///
35///   kPosToIJ[r][kIJtoPos[r][ij]] == ij
36pub const K_POS_TO_IJ: [[usize; 4]; 4] = [
37    // 0  1  2  3
38    [0, 1, 3, 2], // canonical order:    (0,0), (0,1), (1,1), (1,0)
39    [0, 2, 3, 1], // axes swapped:       (0,0), (1,0), (1,1), (0,1)
40    [3, 2, 0, 1], // bits inverted:      (1,1), (1,0), (0,0), (0,1)
41    [3, 1, 0, 2], // swapped & inverted: (1,1), (0,1), (0,0), (1,0)
42];
43
44/// kPosToOrientation[pos] -> orientation_modifier
45///
46/// Return a modifier indicating how the orientation of the child subcell
47/// with the given traversal position [0..3] is related to the orientation
48/// of the parent cell.  The modifier should be XOR-ed with the parent
49/// orientation to obtain the curve orientation in the child.
50pub const K_POS_TO_ORIENTATION: [u8; 4] = [K_SWAP_MASK, 0, 0, K_INVERT_MASK + K_SWAP_MASK];
51
52/// The U,V,W axes for each face.
53pub const K_FACE_UVW_FACES: [[[i32; 2]; 3]; 6] = [
54    // Face 0
55    [
56        [4, 1], // U
57        [5, 2], // V
58        [3, 0], // W
59    ],
60    // Face 1
61    [
62        [0, 3], // U
63        [5, 2], // V
64        [4, 1], // W
65    ],
66    // Face 2
67    [
68        [0, 3], // U
69        [1, 4], // V
70        [5, 2], // W
71    ],
72    // Face 3
73    [
74        [2, 5], // U
75        [1, 4], // V
76        [0, 3], // W
77    ],
78    // Face 4
79    [
80        [2, 5], // U
81        [3, 0], // V
82        [1, 4], // W
83    ],
84    // Face 5
85    [
86        [4, 1], // U
87        [3, 0], // V
88        [2, 5], // W
89    ],
90];
91
92/// The precomputed neighbors of each face (see GetUVWFace).
93pub const K_FACE_UVW_AXES: [[[f64; 3]; 3]; 6] = [
94    // Face 0
95    [
96        [0.0, 1.0, 0.0], // U
97        [0.0, 0.0, 1.0], // V
98        [1.0, 0.0, 0.0], // W
99    ],
100    // Face 1
101    [
102        [-1.0, 0.0, 0.0], // U
103        [0.0, 0.0, 1.0],  // V
104        [0.0, 1.0, 0.0],  // W
105    ],
106    // Face 2
107    [
108        [-1.0, 0.0, 0.0], // U
109        [0.0, -1.0, 0.0], // V
110        [0.0, 0.0, 1.0],  // W
111    ],
112    // Face 3
113    [
114        [0.0, 0.0, -1.0], // U
115        [0.0, -1.0, 0.0], // V
116        [-1.0, 0.0, 0.0], // W
117    ],
118    // Face 4
119    [
120        [0.0, 0.0, -1.0], // U
121        [1.0, 0.0, 0.0],  // V
122        [0.0, -1.0, 0.0], // W
123    ],
124    // Face 5
125    [
126        [0.0, 1.0, 0.0],  // U
127        [1.0, 0.0, 0.0],  // V
128        [0.0, 0.0, -1.0], // W
129    ],
130];
131
132/// [1 << (2 * kLookupBits + 2)]u16;
133pub const LOOKUP_POS: [u16; 1024] = [
134    0, 1, 682, 683, 14, 4, 685, 679, 17, 58, 688, 667, 20, 61, 702, 663, 234, 64, 705, 619, 237,
135    78, 708, 615, 240, 81, 762, 603, 254, 84, 765, 599, 257, 938, 768, 427, 260, 941, 782, 423,
136    314, 944, 785, 411, 317, 958, 788, 407, 320, 961, 1002, 363, 334, 964, 1005, 359, 337, 1018,
137    1008, 347, 340, 1021, 1022, 343, 5, 15, 678, 684, 9, 8, 675, 674, 31, 54, 693, 668, 24, 51,
138    697, 658, 230, 69, 719, 620, 227, 73, 712, 610, 245, 95, 758, 604, 249, 88, 755, 594, 271, 934,
139    773, 428, 264, 931, 777, 418, 310, 949, 799, 412, 307, 953, 792, 402, 325, 975, 998, 364, 329,
140    968, 995, 354, 351, 1014, 1013, 348, 344, 1011, 1017, 338, 59, 16, 666, 689, 55, 30, 669, 692,
141    33, 32, 651, 650, 36, 46, 647, 653, 218, 123, 720, 625, 221, 119, 734, 628, 203, 97, 736, 586,
142    199, 100, 750, 589, 272, 922, 827, 433, 286, 925, 823, 436, 288, 907, 801, 394, 302, 903, 804,
143    397, 379, 976, 986, 369, 375, 990, 989, 372, 353, 992, 971, 330, 356, 1006, 967, 333, 60, 21,
144    662, 703, 50, 25, 659, 696, 47, 37, 652, 646, 40, 41, 642, 643, 214, 124, 725, 639, 211, 114,
145    729, 632, 204, 111, 741, 582, 194, 104, 745, 579, 277, 918, 828, 447, 281, 915, 818, 440, 293,
146    908, 815, 390, 297, 898, 808, 387, 380, 981, 982, 383, 370, 985, 979, 376, 367, 997, 972, 326,
147    360, 1001, 962, 323, 65, 235, 618, 704, 68, 231, 621, 718, 122, 219, 624, 721, 125, 215, 638,
148    724, 129, 128, 555, 554, 132, 142, 551, 557, 186, 145, 539, 560, 189, 148, 535, 574, 491, 874,
149    833, 448, 487, 877, 836, 462, 475, 880, 890, 465, 471, 894, 893, 468, 384, 811, 897, 298, 398,
150    807, 900, 301, 401, 795, 954, 304, 404, 791, 957, 318, 79, 236, 614, 709, 72, 226, 611, 713,
151    118, 220, 629, 735, 115, 210, 633, 728, 143, 133, 556, 550, 136, 137, 546, 547, 182, 159, 540,
152    565, 179, 152, 530, 569, 492, 870, 847, 453, 482, 867, 840, 457, 476, 885, 886, 479, 466, 889,
153    883, 472, 389, 812, 911, 294, 393, 802, 904, 291, 415, 796, 950, 309, 408, 786, 947, 313, 80,
154    241, 602, 763, 94, 244, 605, 759, 96, 202, 587, 737, 110, 205, 583, 740, 144, 187, 561, 538,
155    158, 183, 564, 541, 160, 161, 522, 523, 174, 164, 525, 519, 497, 858, 848, 507, 500, 861, 862,
156    503, 458, 843, 864, 481, 461, 839, 878, 484, 443, 817, 912, 282, 439, 820, 926, 285, 417, 778,
157    928, 267, 420, 781, 942, 263, 85, 255, 598, 764, 89, 248, 595, 754, 101, 198, 588, 751, 105,
158    195, 578, 744, 149, 188, 575, 534, 153, 178, 568, 531, 165, 175, 518, 524, 169, 168, 515, 514,
159    511, 854, 853, 508, 504, 851, 857, 498, 454, 844, 869, 495, 451, 834, 873, 488, 444, 831, 917,
160    278, 434, 824, 921, 275, 431, 774, 933, 268, 424, 771, 937, 258, 939, 256, 426, 769, 935, 270,
161    429, 772, 923, 273, 432, 826, 919, 276, 446, 829, 875, 490, 449, 832, 871, 493, 452, 846, 859,
162    496, 506, 849, 855, 510, 509, 852, 513, 512, 171, 170, 516, 526, 167, 173, 570, 529, 155, 176,
163    573, 532, 151, 190, 576, 746, 107, 193, 590, 749, 103, 196, 593, 752, 91, 250, 596, 766, 87,
164    253, 940, 261, 422, 783, 930, 265, 419, 776, 924, 287, 437, 822, 914, 280, 441, 819, 876, 486,
165    463, 837, 866, 483, 456, 841, 860, 501, 502, 863, 850, 505, 499, 856, 527, 517, 172, 166, 520,
166    521, 162, 163, 566, 543, 156, 181, 563, 536, 146, 185, 581, 742, 108, 207, 585, 739, 98, 200,
167    607, 757, 92, 246, 600, 761, 82, 243, 945, 315, 410, 784, 948, 311, 413, 798, 906, 289, 395,
168    800, 909, 292, 391, 814, 881, 474, 464, 891, 884, 477, 478, 887, 842, 459, 480, 865, 845, 455,
169    494, 868, 528, 571, 177, 154, 542, 567, 180, 157, 544, 545, 138, 139, 558, 548, 141, 135, 635,
170    730, 113, 208, 631, 733, 116, 222, 609, 715, 74, 224, 612, 711, 77, 238, 959, 316, 406, 789,
171    952, 306, 403, 793, 902, 303, 396, 805, 899, 296, 386, 809, 895, 470, 469, 892, 888, 467, 473,
172    882, 838, 460, 485, 879, 835, 450, 489, 872, 533, 572, 191, 150, 537, 562, 184, 147, 549, 559,
173    134, 140, 553, 552, 131, 130, 636, 726, 127, 213, 626, 723, 120, 217, 623, 716, 70, 229, 616,
174    706, 67, 233, 960, 321, 362, 1003, 974, 324, 365, 999, 977, 378, 368, 987, 980, 381, 382, 983,
175    810, 385, 299, 896, 813, 388, 295, 910, 816, 442, 283, 913, 830, 445, 279, 916, 747, 577, 192,
176    106, 743, 580, 206, 109, 731, 634, 209, 112, 727, 637, 212, 126, 640, 641, 42, 43, 654, 644,
177    45, 39, 657, 698, 48, 27, 660, 701, 62, 23, 965, 335, 358, 1004, 969, 328, 355, 994, 991, 374,
178    373, 988, 984, 371, 377, 978, 806, 399, 300, 901, 803, 392, 290, 905, 821, 438, 284, 927, 825,
179    435, 274, 920, 748, 591, 197, 102, 738, 584, 201, 99, 732, 630, 223, 117, 722, 627, 216, 121,
180    645, 655, 38, 44, 649, 648, 35, 34, 671, 694, 53, 28, 664, 691, 57, 18, 1019, 336, 346, 1009,
181    1015, 350, 349, 1012, 993, 352, 331, 970, 996, 366, 327, 973, 794, 400, 305, 955, 797, 414,
182    308, 951, 779, 416, 266, 929, 775, 430, 269, 932, 753, 592, 251, 90, 756, 606, 247, 93, 714,
183    608, 225, 75, 717, 622, 228, 71, 699, 656, 26, 49, 695, 670, 29, 52, 673, 672, 11, 10, 676,
184    686, 7, 13, 1020, 341, 342, 1023, 1010, 345, 339, 1016, 1007, 357, 332, 966, 1000, 361, 322,
185    963, 790, 405, 319, 956, 787, 409, 312, 946, 780, 421, 262, 943, 770, 425, 259, 936, 767, 597,
186    252, 86, 760, 601, 242, 83, 710, 613, 239, 76, 707, 617, 232, 66, 700, 661, 22, 63, 690, 665,
187    19, 56, 687, 677, 12, 6, 680, 681, 2, 3,
188];
189
190/// [1 << (2 * kLookupBits + 2)]u16;
191pub const LOOKUP_IJ: [u16; 1024] = [
192    0, 1, 1022, 1023, 65, 4, 959, 1018, 69, 68, 955, 954, 6, 67, 1016, 957, 9, 128, 1015, 894, 12,
193    193, 1010, 831, 76, 197, 946, 827, 75, 134, 949, 888, 137, 136, 887, 886, 140, 201, 882, 823,
194    204, 205, 818, 819, 203, 142, 821, 880, 198, 79, 824, 945, 135, 74, 889, 948, 131, 10, 893,
195    1012, 192, 13, 830, 1011, 257, 16, 767, 1006, 260, 81, 762, 943, 324, 85, 698, 939, 323, 22,
196    701, 1000, 384, 25, 638, 999, 449, 28, 575, 994, 453, 92, 571, 930, 390, 91, 632, 933, 392,
197    153, 630, 871, 457, 156, 567, 866, 461, 220, 563, 802, 398, 219, 624, 805, 335, 214, 689, 808,
198    330, 151, 692, 873, 266, 147, 756, 877, 269, 208, 755, 814, 273, 272, 751, 750, 276, 337, 746,
199    687, 340, 341, 682, 683, 339, 278, 685, 744, 400, 281, 622, 743, 465, 284, 559, 738, 469, 348,
200    555, 674, 406, 347, 616, 677, 408, 409, 614, 615, 473, 412, 551, 610, 477, 476, 547, 546, 414,
201    475, 608, 549, 351, 470, 673, 552, 346, 407, 676, 617, 282, 403, 740, 621, 285, 464, 739, 558,
202    222, 463, 800, 561, 159, 458, 865, 564, 155, 394, 869, 628, 216, 397, 806, 627, 215, 334, 809,
203    688, 210, 271, 812, 753, 146, 267, 876, 757, 149, 328, 875, 694, 87, 326, 937, 696, 82, 263,
204    940, 761, 18, 259, 1004, 765, 21, 320, 1003, 702, 24, 385, 998, 639, 89, 388, 935, 634, 93,
205    452, 931, 570, 30, 451, 992, 573, 33, 512, 991, 510, 36, 577, 986, 447, 100, 581, 922, 443, 99,
206    518, 925, 504, 160, 521, 862, 503, 225, 524, 799, 498, 229, 588, 795, 434, 166, 587, 856, 437,
207    168, 649, 854, 375, 233, 652, 791, 370, 237, 716, 787, 306, 174, 715, 848, 309, 111, 710, 913,
208    312, 106, 647, 916, 377, 42, 643, 980, 381, 45, 704, 979, 318, 48, 769, 974, 255, 113, 772,
209    911, 250, 117, 836, 907, 186, 54, 835, 968, 189, 57, 896, 967, 126, 60, 961, 962, 63, 124, 965,
210    898, 59, 123, 902, 901, 120, 185, 904, 839, 118, 188, 969, 834, 55, 252, 973, 770, 51, 251,
211    910, 773, 112, 246, 847, 776, 177, 183, 842, 841, 180, 179, 778, 845, 244, 240, 781, 782, 243,
212    304, 785, 718, 239, 369, 788, 655, 234, 373, 852, 651, 170, 310, 851, 712, 173, 313, 912, 711,
213    110, 316, 977, 706, 47, 380, 981, 642, 43, 379, 918, 645, 104, 441, 920, 583, 102, 444, 985,
214    578, 39, 508, 989, 514, 35, 507, 926, 517, 96, 502, 863, 520, 161, 439, 858, 585, 164, 435,
215    794, 589, 228, 496, 797, 526, 227, 495, 734, 529, 288, 490, 671, 532, 353, 426, 667, 596, 357,
216    429, 728, 595, 294, 366, 727, 656, 297, 303, 722, 721, 300, 299, 658, 725, 364, 360, 661, 662,
217    363, 358, 599, 664, 425, 295, 594, 729, 428, 291, 530, 733, 492, 352, 533, 670, 491, 417, 536,
218    607, 486, 420, 601, 602, 423, 484, 605, 538, 419, 483, 542, 541, 480, 545, 544, 479, 478, 548,
219    609, 474, 415, 612, 613, 410, 411, 611, 550, 413, 472, 672, 553, 350, 471, 737, 556, 287, 466,
220    741, 620, 283, 402, 678, 619, 344, 405, 680, 681, 342, 343, 745, 684, 279, 338, 749, 748, 275,
221    274, 686, 747, 336, 277, 623, 742, 401, 280, 618, 679, 404, 345, 554, 675, 468, 349, 557, 736,
222    467, 286, 560, 801, 462, 223, 625, 804, 399, 218, 629, 868, 395, 154, 566, 867, 456, 157, 569,
223    928, 455, 94, 572, 993, 450, 31, 636, 997, 386, 27, 635, 934, 389, 88, 697, 936, 327, 86, 700,
224    1001, 322, 23, 764, 1005, 258, 19, 763, 942, 261, 80, 758, 879, 264, 145, 695, 874, 329, 148,
225    691, 810, 333, 212, 752, 813, 270, 211, 816, 817, 206, 207, 881, 820, 143, 202, 885, 884, 139,
226    138, 822, 883, 200, 141, 825, 944, 199, 78, 828, 1009, 194, 15, 892, 1013, 130, 11, 891, 950,
227    133, 72, 953, 952, 71, 70, 956, 1017, 66, 7, 1020, 1021, 2, 3, 1019, 958, 5, 64, 1014, 895, 8,
228    129, 951, 890, 73, 132, 947, 826, 77, 196, 1008, 829, 14, 195, 1007, 766, 17, 256, 1002, 703,
229    20, 321, 938, 699, 84, 325, 941, 760, 83, 262, 878, 759, 144, 265, 815, 754, 209, 268, 811,
230    690, 213, 332, 872, 693, 150, 331, 870, 631, 152, 393, 807, 626, 217, 396, 803, 562, 221, 460,
231    864, 565, 158, 459, 929, 568, 95, 454, 932, 633, 90, 391, 996, 637, 26, 387, 995, 574, 29, 448,
232    990, 511, 32, 513, 927, 506, 97, 516, 923, 442, 101, 580, 984, 445, 38, 579, 983, 382, 41, 640,
233    978, 319, 44, 705, 914, 315, 108, 709, 917, 376, 107, 646, 855, 374, 169, 648, 850, 311, 172,
234    713, 786, 307, 236, 717, 789, 368, 235, 654, 792, 433, 230, 591, 857, 436, 167, 586, 861, 500,
235    163, 522, 798, 499, 224, 525, 735, 494, 289, 528, 730, 431, 292, 593, 666, 427, 356, 597, 669,
236    488, 355, 534, 606, 487, 416, 537, 543, 482, 481, 540, 539, 418, 485, 604, 600, 421, 422, 603,
237    598, 359, 424, 665, 535, 354, 489, 668, 531, 290, 493, 732, 592, 293, 430, 731, 657, 296, 367,
238    726, 660, 361, 362, 663, 724, 365, 298, 659, 723, 302, 301, 720, 719, 238, 305, 784, 714, 175,
239    308, 849, 650, 171, 372, 853, 653, 232, 371, 790, 590, 231, 432, 793, 527, 226, 497, 796, 523,
240    162, 501, 860, 584, 165, 438, 859, 582, 103, 440, 921, 519, 98, 505, 924, 515, 34, 509, 988,
241    576, 37, 446, 987, 641, 40, 383, 982, 644, 105, 378, 919, 708, 109, 314, 915, 707, 46, 317,
242    976, 768, 49, 254, 975, 833, 52, 191, 970, 837, 116, 187, 906, 774, 115, 248, 909, 777, 176,
243    247, 846, 780, 241, 242, 783, 844, 245, 178, 779, 843, 182, 181, 840, 905, 184, 119, 838, 908,
244    249, 114, 775, 972, 253, 50, 771, 971, 190, 53, 832, 966, 127, 56, 897, 903, 122, 121, 900,
245    899, 58, 125, 964, 960, 61, 62, 963,
246];
gistools/geometry/s2/coords_internal.rs

gistools/geometry/s2/
coords_internal.rs
