/src/h3/src/h3lib/lib/h3Index.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2016-2021 Uber Technologies, Inc. |
3 | | * |
4 | | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | | * you may not use this file except in compliance with the License. |
6 | | * You may obtain a copy of the License at |
7 | | * |
8 | | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | | * |
10 | | * Unless required by applicable law or agreed to in writing, software |
11 | | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | | * See the License for the specific language governing permissions and |
14 | | * limitations under the License. |
15 | | */ |
16 | | /** @file h3Index.c |
17 | | * @brief H3Index utility functions |
18 | | * (see h3api.h for the main library entry functions) |
19 | | */ |
20 | | #include "h3Index.h" |
21 | | |
22 | | #include <inttypes.h> |
23 | | #include <math.h> |
24 | | #include <stdlib.h> |
25 | | #include <string.h> |
26 | | |
27 | | #include "alloc.h" |
28 | | #include "baseCells.h" |
29 | | #include "faceijk.h" |
30 | | #include "h3Assert.h" |
31 | | #include "iterators.h" |
32 | | #include "mathExtensions.h" |
33 | | |
34 | | /** |
35 | | * Returns the H3 resolution of an H3 index. |
36 | | * @param h The H3 index. |
37 | | * @return The resolution of the H3 index argument. |
38 | | */ |
39 | 0 | int H3_EXPORT(getResolution)(H3Index h) { return H3_GET_RESOLUTION(h); } |
40 | | |
41 | | /** |
42 | | * Returns the H3 base cell "number" of an H3 cell (hexagon or pentagon). |
43 | | * |
44 | | * Note: Technically works on H3 edges, but will return base cell of the |
45 | | * origin cell. |
46 | | * |
47 | | * @param h The H3 cell. |
48 | | * @return The base cell "number" of the H3 cell argument. |
49 | | */ |
50 | 0 | int H3_EXPORT(getBaseCellNumber)(H3Index h) { return H3_GET_BASE_CELL(h); } |
51 | | |
52 | | /** |
53 | | * Converts a string representation of an H3 index into an H3 index. |
54 | | * @param str The string representation of an H3 index. |
55 | | * @return The H3 index corresponding to the string argument, or H3_NULL if |
56 | | * invalid. |
57 | | */ |
58 | 0 | H3Error H3_EXPORT(stringToH3)(const char *str, H3Index *out) { |
59 | 0 | H3Index h = H3_NULL; |
60 | | // If failed, h will be unmodified and we should return H3_NULL anyways. |
61 | 0 | int read = sscanf(str, "%" PRIx64, &h); |
62 | 0 | if (read != 1) { |
63 | 0 | return E_FAILED; |
64 | 0 | } |
65 | 0 | *out = h; |
66 | 0 | return E_SUCCESS; |
67 | 0 | } |
68 | | |
69 | | /** |
70 | | * Converts an H3 index into a string representation. |
71 | | * @param h The H3 index to convert. |
72 | | * @param str The string representation of the H3 index. |
73 | | * @param sz Size of the buffer `str` |
74 | | */ |
75 | 0 | H3Error H3_EXPORT(h3ToString)(H3Index h, char *str, size_t sz) { |
76 | | // An unsigned 64 bit integer will be expressed in at most |
77 | | // 16 digits plus 1 for the null terminator. |
78 | 0 | if (sz < 17) { |
79 | | // Buffer is potentially not large enough. |
80 | 0 | return E_MEMORY_BOUNDS; |
81 | 0 | } |
82 | 0 | sprintf(str, "%" PRIx64, h); |
83 | 0 | return E_SUCCESS; |
84 | 0 | } |
85 | | |
86 | | /** |
87 | | * Returns whether or not an H3 index is a valid cell (hexagon or pentagon). |
88 | | * @param h The H3 index to validate. |
89 | | * @return 1 if the H3 index if valid, and 0 if it is not. |
90 | | */ |
91 | 0 | int H3_EXPORT(isValidCell)(H3Index h) { |
92 | 0 | if (H3_GET_HIGH_BIT(h) != 0) return 0; |
93 | | |
94 | 0 | if (H3_GET_MODE(h) != H3_CELL_MODE) return 0; |
95 | | |
96 | 0 | if (H3_GET_RESERVED_BITS(h) != 0) return 0; |
97 | | |
98 | 0 | int baseCell = H3_GET_BASE_CELL(h); |
99 | 0 | if (NEVER(baseCell < 0) || baseCell >= NUM_BASE_CELLS) { |
100 | | // Base cells less than zero can not be represented in an index |
101 | 0 | return 0; |
102 | 0 | } |
103 | | |
104 | 0 | int res = H3_GET_RESOLUTION(h); |
105 | 0 | if (NEVER(res < 0 || res > MAX_H3_RES)) { |
106 | | // Resolutions less than zero can not be represented in an index |
107 | 0 | return 0; |
108 | 0 | } |
109 | | |
110 | 0 | bool foundFirstNonZeroDigit = false; |
111 | 0 | for (int r = 1; r <= res; r++) { |
112 | 0 | Direction digit = H3_GET_INDEX_DIGIT(h, r); |
113 | |
|
114 | 0 | if (!foundFirstNonZeroDigit && digit != CENTER_DIGIT) { |
115 | 0 | foundFirstNonZeroDigit = true; |
116 | 0 | if (_isBaseCellPentagon(baseCell) && digit == K_AXES_DIGIT) { |
117 | 0 | return 0; |
118 | 0 | } |
119 | 0 | } |
120 | | |
121 | 0 | if (NEVER(digit < CENTER_DIGIT) || digit >= NUM_DIGITS) return 0; |
122 | 0 | } |
123 | | |
124 | 0 | for (int r = res + 1; r <= MAX_H3_RES; r++) { |
125 | 0 | Direction digit = H3_GET_INDEX_DIGIT(h, r); |
126 | 0 | if (digit != INVALID_DIGIT) return 0; |
127 | 0 | } |
128 | | |
129 | 0 | return 1; |
130 | 0 | } |
131 | | |
132 | | /** |
133 | | * Initializes an H3 index. |
134 | | * @param hp The H3 index to initialize. |
135 | | * @param res The H3 resolution to initialize the index to. |
136 | | * @param baseCell The H3 base cell to initialize the index to. |
137 | | * @param initDigit The H3 digit (0-7) to initialize all of the index digits to. |
138 | | */ |
139 | 0 | void setH3Index(H3Index *hp, int res, int baseCell, Direction initDigit) { |
140 | 0 | H3Index h = H3_INIT; |
141 | 0 | H3_SET_MODE(h, H3_CELL_MODE); |
142 | 0 | H3_SET_RESOLUTION(h, res); |
143 | 0 | H3_SET_BASE_CELL(h, baseCell); |
144 | 0 | for (int r = 1; r <= res; r++) H3_SET_INDEX_DIGIT(h, r, initDigit); |
145 | 0 | *hp = h; |
146 | 0 | } |
147 | | |
148 | | /** |
149 | | * cellToParent produces the parent index for a given H3 index |
150 | | * |
151 | | * @param h H3Index to find parent of |
152 | | * @param parentRes The resolution to switch to (parent, grandparent, etc) |
153 | | * |
154 | | * @return H3Index of the parent, or H3_NULL if you actually asked for a child |
155 | | */ |
156 | 20.5k | H3Error H3_EXPORT(cellToParent)(H3Index h, int parentRes, H3Index *out) { |
157 | 20.5k | int childRes = H3_GET_RESOLUTION(h); |
158 | 20.5k | if (parentRes < 0 || parentRes > MAX_H3_RES) { |
159 | 7 | return E_RES_DOMAIN; |
160 | 20.5k | } else if (parentRes > childRes) { |
161 | 11 | return E_RES_MISMATCH; |
162 | 20.5k | } else if (parentRes == childRes) { |
163 | 3.92k | *out = h; |
164 | 3.92k | return E_SUCCESS; |
165 | 3.92k | } |
166 | 16.6k | H3Index parentH = H3_SET_RESOLUTION(h, parentRes); |
167 | 97.7k | for (int i = parentRes + 1; i <= childRes; i++) { |
168 | 81.0k | H3_SET_INDEX_DIGIT(parentH, i, H3_DIGIT_MASK); |
169 | 81.0k | } |
170 | 16.6k | *out = parentH; |
171 | 16.6k | return E_SUCCESS; |
172 | 20.5k | } |
173 | | |
174 | | /** |
175 | | * Determines whether one resolution is a valid child resolution for a cell. |
176 | | * Each resolution is considered a valid child resolution of itself. |
177 | | * |
178 | | * @param h h3Index parent cell |
179 | | * @param childRes int resolution of the child |
180 | | * |
181 | | * @return The validity of the child resolution |
182 | | */ |
183 | 899k | static bool _hasChildAtRes(H3Index h, int childRes) { |
184 | 899k | int parentRes = H3_GET_RESOLUTION(h); |
185 | 899k | if (childRes < parentRes || childRes > MAX_H3_RES) { |
186 | 223 | return false; |
187 | 223 | } |
188 | 899k | return true; |
189 | 899k | } |
190 | | |
191 | | /** |
192 | | * cellToChildrenSize returns the exact number of children for a cell at a |
193 | | * given child resolution. |
194 | | * |
195 | | * @param h H3Index to find the number of children of |
196 | | * @param childRes The child resolution you're interested in |
197 | | * |
198 | | * @return int Exact number of children (handles hexagons and pentagons |
199 | | * correctly) |
200 | | */ |
201 | 340k | H3Error H3_EXPORT(cellToChildrenSize)(H3Index h, int childRes, int64_t *out) { |
202 | 340k | if (!_hasChildAtRes(h, childRes)) return E_RES_DOMAIN; |
203 | | |
204 | 340k | int n = childRes - H3_GET_RESOLUTION(h); |
205 | | |
206 | 340k | if (H3_EXPORT(isPentagon)(h)) { |
207 | 3.34k | *out = 1 + 5 * (_ipow(7, n) - 1) / 6; |
208 | 337k | } else { |
209 | 337k | *out = _ipow(7, n); |
210 | 337k | } |
211 | 340k | return E_SUCCESS; |
212 | 340k | } |
213 | | |
214 | | /** |
215 | | * makeDirectChild takes an index and immediately returns the immediate child |
216 | | * index based on the specified cell number. Bit operations only, could generate |
217 | | * invalid indexes if not careful (deleted cell under a pentagon). |
218 | | * |
219 | | * @param h H3Index to find the direct child of |
220 | | * @param cellNumber int id of the direct child (0-6) |
221 | | * |
222 | | * @return The new H3Index for the child |
223 | | */ |
224 | 0 | H3Index makeDirectChild(H3Index h, int cellNumber) { |
225 | 0 | int childRes = H3_GET_RESOLUTION(h) + 1; |
226 | 0 | H3Index childH = H3_SET_RESOLUTION(h, childRes); |
227 | 0 | H3_SET_INDEX_DIGIT(childH, childRes, cellNumber); |
228 | 0 | return childH; |
229 | 0 | } |
230 | | |
231 | | /** |
232 | | * cellToChildren takes the given hexagon id and generates all of the children |
233 | | * at the specified resolution storing them into the provided memory pointer. |
234 | | * It's assumed that cellToChildrenSize was used to determine the allocation. |
235 | | * |
236 | | * @param h H3Index to find the children of |
237 | | * @param childRes int the child level to produce |
238 | | * @param children H3Index* the memory to store the resulting addresses in |
239 | | */ |
240 | 0 | H3Error H3_EXPORT(cellToChildren)(H3Index h, int childRes, H3Index *children) { |
241 | 0 | int64_t i = 0; |
242 | 0 | for (IterCellsChildren iter = iterInitParent(h, childRes); iter.h; |
243 | 0 | iterStepChild(&iter)) { |
244 | 0 | children[i] = iter.h; |
245 | 0 | i++; |
246 | 0 | } |
247 | 0 | return E_SUCCESS; |
248 | 0 | } |
249 | | |
250 | | /** |
251 | | * Zero out index digits from start to end, inclusive. |
252 | | * No-op if start > end. |
253 | | */ |
254 | 3.75k | H3Index _zeroIndexDigits(H3Index h, int start, int end) { |
255 | 3.75k | if (start > end) return h; |
256 | | |
257 | 2.62k | H3Index m = 0; |
258 | | |
259 | 2.62k | m = ~m; |
260 | 2.62k | m <<= H3_PER_DIGIT_OFFSET * (end - start + 1); |
261 | 2.62k | m = ~m; |
262 | 2.62k | m <<= H3_PER_DIGIT_OFFSET * (MAX_H3_RES - end); |
263 | 2.62k | m = ~m; |
264 | | |
265 | 2.62k | return h & m; |
266 | 3.75k | } |
267 | | |
268 | | /** |
269 | | * cellToCenterChild produces the center child index for a given H3 index at |
270 | | * the specified resolution |
271 | | * |
272 | | * @param h H3Index to find center child of |
273 | | * @param childRes The resolution to switch to |
274 | | * @param child H3Index of the center child |
275 | | * @return 0 (E_SUCCESS) on success |
276 | | */ |
277 | 0 | H3Error H3_EXPORT(cellToCenterChild)(H3Index h, int childRes, H3Index *child) { |
278 | 0 | if (!_hasChildAtRes(h, childRes)) return E_RES_DOMAIN; |
279 | | |
280 | 0 | h = _zeroIndexDigits(h, H3_GET_RESOLUTION(h) + 1, childRes); |
281 | 0 | H3_SET_RESOLUTION(h, childRes); |
282 | 0 | *child = h; |
283 | 0 | return E_SUCCESS; |
284 | 0 | } |
285 | | |
286 | | /** |
287 | | * compactCells takes a set of hexagons all at the same resolution and |
288 | | * compresses them by pruning full child branches to the parent level. This is |
289 | | * also done for all parents recursively to get the minimum number of hex |
290 | | * addresses that perfectly cover the defined space. |
291 | | * @param h3Set Set of hexagons |
292 | | * @param compactedSet The output array of compressed hexagons (preallocated) |
293 | | * @param numHexes The size of the input and output arrays (possible that no |
294 | | * contiguous regions exist in the set at all and no compression possible) |
295 | | * @return an error code on bad input data |
296 | | */ |
297 | | // todo: update internal implementation for int64_t |
298 | | H3Error H3_EXPORT(compactCells)(const H3Index *h3Set, H3Index *compactedSet, |
299 | 746 | const int64_t numHexes) { |
300 | 746 | if (numHexes == 0) { |
301 | 0 | return E_SUCCESS; |
302 | 0 | } |
303 | 746 | int res = H3_GET_RESOLUTION(h3Set[0]); |
304 | 746 | if (res == 0) { |
305 | | // No compaction possible, just copy the set to output |
306 | 979k | for (int i = 0; i < numHexes; i++) { |
307 | 979k | compactedSet[i] = h3Set[i]; |
308 | 979k | } |
309 | 104 | return E_SUCCESS; |
310 | 104 | } |
311 | 642 | H3Index *remainingHexes = H3_MEMORY(malloc)(numHexes * sizeof(H3Index)); |
312 | 642 | if (!remainingHexes) { |
313 | 0 | return E_MEMORY_ALLOC; |
314 | 0 | } |
315 | 642 | memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index)); |
316 | 642 | H3Index *hashSetArray = H3_MEMORY(calloc)(numHexes, sizeof(H3Index)); |
317 | 642 | if (!hashSetArray) { |
318 | 0 | H3_MEMORY(free)(remainingHexes); |
319 | 0 | return E_MEMORY_ALLOC; |
320 | 0 | } |
321 | 642 | H3Index *compactedSetOffset = compactedSet; |
322 | 642 | int numRemainingHexes = numHexes; |
323 | 876 | while (numRemainingHexes) { |
324 | 693 | res = H3_GET_RESOLUTION(remainingHexes[0]); |
325 | 693 | int parentRes = res - 1; |
326 | | |
327 | | // If parentRes is less than zero, we've compacted all the way up to the |
328 | | // base cells. Time to process the remaining cells. |
329 | 693 | if (parentRes >= 0) { |
330 | | // Put the parents of the hexagons into the temp array |
331 | | // via a hashing mechanism, and use the reserved bits |
332 | | // to track how many times a parent is duplicated |
333 | 750k | for (int i = 0; i < numRemainingHexes; i++) { |
334 | 749k | H3Index currIndex = remainingHexes[i]; |
335 | | // TODO: This case is coverable (reachable by fuzzer) |
336 | 749k | if (currIndex != 0) { |
337 | | // If the reserved bits were set by the caller, the |
338 | | // algorithm below may encounter undefined behavior |
339 | | // because it expects to have set the reserved bits |
340 | | // itself. |
341 | 11.5k | if (H3_GET_RESERVED_BITS(currIndex) != 0) { |
342 | 202 | H3_MEMORY(free)(remainingHexes); |
343 | 202 | H3_MEMORY(free)(hashSetArray); |
344 | 202 | return E_CELL_INVALID; |
345 | 202 | } |
346 | | |
347 | 11.3k | H3Index parent; |
348 | 11.3k | H3Error parentError = |
349 | 11.3k | H3_EXPORT(cellToParent)(currIndex, parentRes, &parent); |
350 | | // Should never be reachable as a result of the compact |
351 | | // algorithm. Can happen if cellToParent errors e.g. |
352 | | // because of incompatible resolutions. |
353 | 11.3k | if (parentError) { |
354 | 11 | H3_MEMORY(free)(remainingHexes); |
355 | 11 | H3_MEMORY(free)(hashSetArray); |
356 | 11 | return parentError; |
357 | 11 | } |
358 | | // Modulus hash the parent into the temp array |
359 | 11.3k | int loc = (int)(parent % numRemainingHexes); |
360 | 11.3k | int loopCount = 0; |
361 | 43.3k | while (hashSetArray[loc] != 0) { |
362 | 32.0k | if (NEVER(loopCount > numRemainingHexes)) { |
363 | | // This case should not be possible because at |
364 | | // most one index is placed into hashSetArray |
365 | | // per numRemainingHexes. |
366 | 0 | H3_MEMORY(free)(remainingHexes); |
367 | 0 | H3_MEMORY(free)(hashSetArray); |
368 | 0 | return E_FAILED; |
369 | 0 | } |
370 | 32.0k | H3Index tempIndex = |
371 | 32.0k | hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE; |
372 | 32.0k | if (tempIndex == parent) { |
373 | 5.50k | int count = |
374 | 5.50k | H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1; |
375 | 5.50k | int limitCount = 7; |
376 | 5.50k | if (H3_EXPORT(isPentagon)( |
377 | 5.50k | tempIndex & H3_RESERVED_MASK_NEGATIVE)) { |
378 | 2.10k | limitCount--; |
379 | 2.10k | } |
380 | | // One is added to count for this check to match |
381 | | // one being added to count later in this |
382 | | // function when checking for all children being |
383 | | // present. |
384 | 5.50k | if (count + 1 > limitCount) { |
385 | | // Only possible on duplicate input |
386 | 19 | H3_MEMORY(free)(remainingHexes); |
387 | 19 | H3_MEMORY(free)(hashSetArray); |
388 | 19 | return E_DUPLICATE_INPUT; |
389 | 19 | } |
390 | 5.48k | H3_SET_RESERVED_BITS(parent, count); |
391 | 5.48k | hashSetArray[loc] = H3_NULL; |
392 | 26.5k | } else { |
393 | 26.5k | loc = (loc + 1) % numRemainingHexes; |
394 | 26.5k | } |
395 | 32.0k | loopCount++; |
396 | 32.0k | } |
397 | 11.3k | hashSetArray[loc] = parent; |
398 | 11.3k | } |
399 | 749k | } |
400 | 680 | } |
401 | | |
402 | | // Determine which parent hexagons have a complete set |
403 | | // of children and put them in the compactableHexes array |
404 | 461 | int compactableCount = 0; |
405 | 461 | int maxCompactableCount = |
406 | 461 | numRemainingHexes / 6; // Somehow all pentagons; conservative |
407 | 461 | if (maxCompactableCount == 0) { |
408 | 220 | memcpy(compactedSetOffset, remainingHexes, |
409 | 220 | numRemainingHexes * sizeof(remainingHexes[0])); |
410 | 220 | break; |
411 | 220 | } |
412 | 241 | H3Index *compactableHexes = |
413 | 241 | H3_MEMORY(calloc)(maxCompactableCount, sizeof(H3Index)); |
414 | 241 | if (!compactableHexes) { |
415 | 0 | H3_MEMORY(free)(remainingHexes); |
416 | 0 | H3_MEMORY(free)(hashSetArray); |
417 | 0 | return E_MEMORY_ALLOC; |
418 | 0 | } |
419 | 674k | for (int i = 0; i < numRemainingHexes; i++) { |
420 | 674k | if (hashSetArray[i] == 0) continue; |
421 | 4.56k | int count = H3_GET_RESERVED_BITS(hashSetArray[i]) + 1; |
422 | | // Include the deleted direction for pentagons as implicitly "there" |
423 | 4.56k | if (H3_EXPORT(isPentagon)(hashSetArray[i] & |
424 | 4.56k | H3_RESERVED_MASK_NEGATIVE)) { |
425 | | // We need this later on, no need to recalculate |
426 | 1.11k | H3_SET_RESERVED_BITS(hashSetArray[i], count); |
427 | | // Increment count after setting the reserved bits, |
428 | | // since count is already incremented above, so it |
429 | | // will be the expected value for a complete hexagon. |
430 | 1.11k | count++; |
431 | 1.11k | } |
432 | 4.56k | if (count == 7) { |
433 | | // Bingo! Full set! |
434 | 544 | compactableHexes[compactableCount] = |
435 | 544 | hashSetArray[i] & H3_RESERVED_MASK_NEGATIVE; |
436 | 544 | compactableCount++; |
437 | 544 | } |
438 | 4.56k | } |
439 | | // Uncompactable hexes are immediately copied into the |
440 | | // output compactedSetOffset |
441 | 241 | int uncompactableCount = 0; |
442 | 674k | for (int i = 0; i < numRemainingHexes; i++) { |
443 | 674k | H3Index currIndex = remainingHexes[i]; |
444 | | // TODO: This case is coverable (reachable by fuzzer) |
445 | 674k | if (currIndex != H3_NULL) { |
446 | 9.21k | H3Index parent; |
447 | 9.21k | H3Error parentError = |
448 | 9.21k | H3_EXPORT(cellToParent)(currIndex, parentRes, &parent); |
449 | 9.21k | if (parentError) { |
450 | 7 | H3_MEMORY(free)(compactableHexes); |
451 | 7 | H3_MEMORY(free)(remainingHexes); |
452 | 7 | H3_MEMORY(free)(hashSetArray); |
453 | 7 | return parentError; |
454 | 7 | } |
455 | | // Modulus hash the parent into the temp array |
456 | | // to determine if this index was included in |
457 | | // the compactableHexes array |
458 | 9.20k | int loc = (int)(parent % numRemainingHexes); |
459 | 9.20k | int loopCount = 0; |
460 | 9.20k | bool isUncompactable = true; |
461 | 33.7k | do { |
462 | 33.7k | if (NEVER(loopCount > numRemainingHexes)) { |
463 | | // This case should not be possible because at most one |
464 | | // index is placed into hashSetArray per input hexagon. |
465 | 0 | H3_MEMORY(free)(compactableHexes); |
466 | 0 | H3_MEMORY(free)(remainingHexes); |
467 | 0 | H3_MEMORY(free)(hashSetArray); |
468 | 0 | return E_FAILED; |
469 | 0 | } |
470 | 33.7k | H3Index tempIndex = |
471 | 33.7k | hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE; |
472 | 33.7k | if (tempIndex == parent) { |
473 | 7.94k | int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1; |
474 | 7.94k | if (count == 7) { |
475 | 3.58k | isUncompactable = false; |
476 | 3.58k | } |
477 | 7.94k | break; |
478 | 25.7k | } else { |
479 | 25.7k | loc = (loc + 1) % numRemainingHexes; |
480 | 25.7k | } |
481 | 25.7k | loopCount++; |
482 | 25.7k | } while (hashSetArray[loc] != parent); |
483 | 9.20k | if (isUncompactable) { |
484 | 5.62k | compactedSetOffset[uncompactableCount] = remainingHexes[i]; |
485 | 5.62k | uncompactableCount++; |
486 | 5.62k | } |
487 | 9.20k | } |
488 | 674k | } |
489 | | // Set up for the next loop |
490 | 234 | memset(hashSetArray, 0, numHexes * sizeof(H3Index)); |
491 | 234 | compactedSetOffset += uncompactableCount; |
492 | 234 | memcpy(remainingHexes, compactableHexes, |
493 | 234 | compactableCount * sizeof(H3Index)); |
494 | 234 | numRemainingHexes = compactableCount; |
495 | 234 | H3_MEMORY(free)(compactableHexes); |
496 | 234 | } |
497 | 403 | H3_MEMORY(free)(remainingHexes); |
498 | 403 | H3_MEMORY(free)(hashSetArray); |
499 | 403 | return E_SUCCESS; |
500 | 642 | } |
501 | | |
502 | | /** |
503 | | * uncompactCells takes a compressed set of cells and expands back to the |
504 | | * original set of cells. |
505 | | * |
506 | | * Skips elements that are H3_NULL (i.e., 0). |
507 | | * |
508 | | * @param compactSet Set of compacted cells |
509 | | * @param numCompact The number of cells in the input compacted set |
510 | | * @param outSet Output array for decompressed cells (preallocated) |
511 | | * @param numOut The size of the output array to bound check against |
512 | | * @param res The H3 resolution to decompress to |
513 | | * @return An error code if output array is too small or any cell |
514 | | * is smaller than the output resolution. |
515 | | */ |
516 | | H3Error H3_EXPORT(uncompactCells)(const H3Index *compactedSet, |
517 | | const int64_t numCompacted, H3Index *outSet, |
518 | 403 | const int64_t numOut, const int res) { |
519 | 403 | int64_t i = 0; |
520 | | |
521 | 559k | for (int64_t j = 0; j < numCompacted; j++) { |
522 | 558k | if (!_hasChildAtRes(compactedSet[j], res)) return E_RES_MISMATCH; |
523 | | |
524 | 558k | for (IterCellsChildren iter = iterInitParent(compactedSet[j], res); |
525 | 179M | iter.h; i++, iterStepChild(&iter)) { |
526 | 178M | if (i >= numOut) return E_MEMORY_BOUNDS; // went too far; abort! |
527 | 178M | outSet[i] = iter.h; |
528 | 178M | } |
529 | 558k | } |
530 | 397 | return E_SUCCESS; |
531 | 403 | } |
532 | | |
533 | | /** |
534 | | * uncompactCellsSize takes a compacted set of hexagons and provides |
535 | | * the exact size of the uncompacted set of hexagons. |
536 | | * |
537 | | * @param compactedSet Set of hexagons |
538 | | * @param numHexes The number of hexes in the input set |
539 | | * @param res The hexagon resolution to decompress to |
540 | | * @param out The number of hexagons to allocate memory for |
541 | | * @returns E_SUCCESS on success, or another value on error |
542 | | */ |
543 | | H3Error H3_EXPORT(uncompactCellsSize)(const H3Index *compactedSet, |
544 | | const int64_t numCompacted, const int res, |
545 | 746 | int64_t *out) { |
546 | 746 | int64_t numOut = 0; |
547 | 1.60M | for (int64_t i = 0; i < numCompacted; i++) { |
548 | 1.60M | if (compactedSet[i] == H3_NULL) continue; |
549 | | |
550 | 340k | int64_t childrenSize; |
551 | 340k | H3Error childrenError = |
552 | 340k | H3_EXPORT(cellToChildrenSize)(compactedSet[i], res, &childrenSize); |
553 | 340k | if (childrenError) { |
554 | | // The parent res does not contain `res`. |
555 | 217 | return E_RES_MISMATCH; |
556 | 217 | } |
557 | 340k | numOut += childrenSize; |
558 | 340k | } |
559 | 529 | *out = numOut; |
560 | 529 | return E_SUCCESS; |
561 | 746 | } |
562 | | |
563 | | /** |
564 | | * isResClassIII takes a hexagon ID and determines if it is in a |
565 | | * Class III resolution (rotated versus the icosahedron and subject |
566 | | * to shape distortion adding extra points on icosahedron edges, making |
567 | | * them not true hexagons). |
568 | | * @param h The H3Index to check. |
569 | | * @return Returns 1 if the hexagon is class III, otherwise 0. |
570 | | */ |
571 | 0 | int H3_EXPORT(isResClassIII)(H3Index h) { return H3_GET_RESOLUTION(h) % 2; } |
572 | | |
573 | | /** |
574 | | * isPentagon takes an H3Index and determines if it is actually a pentagon. |
575 | | * @param h The H3Index to check. |
576 | | * @return Returns 1 if it is a pentagon, otherwise 0. |
577 | | */ |
578 | 354k | int H3_EXPORT(isPentagon)(H3Index h) { |
579 | 354k | return _isBaseCellPentagon(H3_GET_BASE_CELL(h)) && |
580 | 354k | !_h3LeadingNonZeroDigit(h); |
581 | 354k | } |
582 | | |
583 | | /** |
584 | | * Returns the highest resolution non-zero digit in an H3Index. |
585 | | * @param h The H3Index. |
586 | | * @return The highest resolution non-zero digit in the H3Index. |
587 | | */ |
588 | 25.6k | Direction _h3LeadingNonZeroDigit(H3Index h) { |
589 | 49.7k | for (int r = 1; r <= H3_GET_RESOLUTION(h); r++) |
590 | 41.9k | if (H3_GET_INDEX_DIGIT(h, r)) return H3_GET_INDEX_DIGIT(h, r); |
591 | | |
592 | | // if we're here it's all 0's |
593 | 7.85k | return CENTER_DIGIT; |
594 | 25.6k | } |
595 | | |
596 | | /** |
597 | | * Rotate an H3Index 60 degrees counter-clockwise about a pentagonal center. |
598 | | * @param h The H3Index. |
599 | | */ |
600 | 0 | H3Index _h3RotatePent60ccw(H3Index h) { |
601 | | // rotate in place; skips any leading 1 digits (k-axis) |
602 | |
|
603 | 0 | int foundFirstNonZeroDigit = 0; |
604 | 0 | for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) { |
605 | | // rotate this digit |
606 | 0 | H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(H3_GET_INDEX_DIGIT(h, r))); |
607 | | |
608 | | // look for the first non-zero digit so we |
609 | | // can adjust for deleted k-axes sequence |
610 | | // if necessary |
611 | 0 | if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) { |
612 | 0 | foundFirstNonZeroDigit = 1; |
613 | | |
614 | | // adjust for deleted k-axes sequence |
615 | 0 | if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) |
616 | 0 | h = _h3Rotate60ccw(h); |
617 | 0 | } |
618 | 0 | } |
619 | 0 | return h; |
620 | 0 | } |
621 | | |
622 | | /** |
623 | | * Rotate an H3Index 60 degrees clockwise about a pentagonal center. |
624 | | * @param h The H3Index. |
625 | | */ |
626 | 0 | H3Index _h3RotatePent60cw(H3Index h) { |
627 | | // rotate in place; skips any leading 1 digits (k-axis) |
628 | |
|
629 | 0 | int foundFirstNonZeroDigit = 0; |
630 | 0 | for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) { |
631 | | // rotate this digit |
632 | 0 | H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r))); |
633 | | |
634 | | // look for the first non-zero digit so we |
635 | | // can adjust for deleted k-axes sequence |
636 | | // if necessary |
637 | 0 | if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) { |
638 | 0 | foundFirstNonZeroDigit = 1; |
639 | | |
640 | | // adjust for deleted k-axes sequence |
641 | 0 | if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) h = _h3Rotate60cw(h); |
642 | 0 | } |
643 | 0 | } |
644 | 0 | return h; |
645 | 0 | } |
646 | | |
647 | | /** |
648 | | * Rotate an H3Index 60 degrees counter-clockwise. |
649 | | * @param h The H3Index. |
650 | | */ |
651 | 0 | H3Index _h3Rotate60ccw(H3Index h) { |
652 | 0 | for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) { |
653 | 0 | Direction oldDigit = H3_GET_INDEX_DIGIT(h, r); |
654 | 0 | H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(oldDigit)); |
655 | 0 | } |
656 | |
|
657 | 0 | return h; |
658 | 0 | } |
659 | | |
660 | | /** |
661 | | * Rotate an H3Index 60 degrees clockwise. |
662 | | * @param h The H3Index. |
663 | | */ |
664 | 0 | H3Index _h3Rotate60cw(H3Index h) { |
665 | 0 | for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) { |
666 | 0 | H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r))); |
667 | 0 | } |
668 | |
|
669 | 0 | return h; |
670 | 0 | } |
671 | | |
672 | | /** |
673 | | * Convert an FaceIJK address to the corresponding H3Index. |
674 | | * @param fijk The FaceIJK address. |
675 | | * @param res The cell resolution. |
676 | | * @return The encoded H3Index (or H3_NULL on failure). |
677 | | */ |
678 | 0 | H3Index _faceIjkToH3(const FaceIJK *fijk, int res) { |
679 | | // initialize the index |
680 | 0 | H3Index h = H3_INIT; |
681 | 0 | H3_SET_MODE(h, H3_CELL_MODE); |
682 | 0 | H3_SET_RESOLUTION(h, res); |
683 | | |
684 | | // check for res 0/base cell |
685 | 0 | if (res == 0) { |
686 | 0 | if (fijk->coord.i > MAX_FACE_COORD || fijk->coord.j > MAX_FACE_COORD || |
687 | 0 | fijk->coord.k > MAX_FACE_COORD) { |
688 | | // out of range input |
689 | 0 | return H3_NULL; |
690 | 0 | } |
691 | | |
692 | 0 | H3_SET_BASE_CELL(h, _faceIjkToBaseCell(fijk)); |
693 | 0 | return h; |
694 | 0 | } |
695 | | |
696 | | // we need to find the correct base cell FaceIJK for this H3 index; |
697 | | // start with the passed in face and resolution res ijk coordinates |
698 | | // in that face's coordinate system |
699 | 0 | FaceIJK fijkBC = *fijk; |
700 | | |
701 | | // build the H3Index from finest res up |
702 | | // adjust r for the fact that the res 0 base cell offsets the indexing |
703 | | // digits |
704 | 0 | CoordIJK *ijk = &fijkBC.coord; |
705 | 0 | for (int r = res - 1; r >= 0; r--) { |
706 | 0 | CoordIJK lastIJK = *ijk; |
707 | 0 | CoordIJK lastCenter; |
708 | 0 | if (isResolutionClassIII(r + 1)) { |
709 | | // rotate ccw |
710 | 0 | _upAp7(ijk); |
711 | 0 | lastCenter = *ijk; |
712 | 0 | _downAp7(&lastCenter); |
713 | 0 | } else { |
714 | | // rotate cw |
715 | 0 | _upAp7r(ijk); |
716 | 0 | lastCenter = *ijk; |
717 | 0 | _downAp7r(&lastCenter); |
718 | 0 | } |
719 | |
|
720 | 0 | CoordIJK diff; |
721 | 0 | _ijkSub(&lastIJK, &lastCenter, &diff); |
722 | 0 | _ijkNormalize(&diff); |
723 | |
|
724 | 0 | H3_SET_INDEX_DIGIT(h, r + 1, _unitIjkToDigit(&diff)); |
725 | 0 | } |
726 | | |
727 | | // fijkBC should now hold the IJK of the base cell in the |
728 | | // coordinate system of the current face |
729 | |
|
730 | 0 | if (fijkBC.coord.i > MAX_FACE_COORD || fijkBC.coord.j > MAX_FACE_COORD || |
731 | 0 | fijkBC.coord.k > MAX_FACE_COORD) { |
732 | | // out of range input |
733 | 0 | return H3_NULL; |
734 | 0 | } |
735 | | |
736 | | // lookup the correct base cell |
737 | 0 | int baseCell = _faceIjkToBaseCell(&fijkBC); |
738 | 0 | H3_SET_BASE_CELL(h, baseCell); |
739 | | |
740 | | // rotate if necessary to get canonical base cell orientation |
741 | | // for this base cell |
742 | 0 | int numRots = _faceIjkToBaseCellCCWrot60(&fijkBC); |
743 | 0 | if (_isBaseCellPentagon(baseCell)) { |
744 | | // force rotation out of missing k-axes sub-sequence |
745 | 0 | if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) { |
746 | | // check for a cw/ccw offset face; default is ccw |
747 | 0 | if (_baseCellIsCwOffset(baseCell, fijkBC.face)) { |
748 | 0 | h = _h3Rotate60cw(h); |
749 | 0 | } else { |
750 | 0 | h = _h3Rotate60ccw(h); |
751 | 0 | } |
752 | 0 | } |
753 | |
|
754 | 0 | for (int i = 0; i < numRots; i++) h = _h3RotatePent60ccw(h); |
755 | 0 | } else { |
756 | 0 | for (int i = 0; i < numRots; i++) { |
757 | 0 | h = _h3Rotate60ccw(h); |
758 | 0 | } |
759 | 0 | } |
760 | |
|
761 | 0 | return h; |
762 | 0 | } |
763 | | |
764 | | /** |
765 | | * Encodes a coordinate on the sphere to the H3 index of the containing cell at |
766 | | * the specified resolution. |
767 | | * |
768 | | * Returns 0 on invalid input. |
769 | | * |
770 | | * @param g The spherical coordinates to encode. |
771 | | * @param res The desired H3 resolution for the encoding. |
772 | | * @param out The encoded H3Index. |
773 | | * @returns E_SUCCESS (0) on success, another value otherwise |
774 | | */ |
775 | 0 | H3Error H3_EXPORT(latLngToCell)(const LatLng *g, int res, H3Index *out) { |
776 | 0 | if (res < 0 || res > MAX_H3_RES) { |
777 | 0 | return E_RES_DOMAIN; |
778 | 0 | } |
779 | 0 | if (!isfinite(g->lat) || !isfinite(g->lng)) { |
780 | 0 | return E_LATLNG_DOMAIN; |
781 | 0 | } |
782 | | |
783 | 0 | FaceIJK fijk; |
784 | 0 | _geoToFaceIjk(g, res, &fijk); |
785 | 0 | *out = _faceIjkToH3(&fijk, res); |
786 | 0 | if (ALWAYS(*out)) { |
787 | 0 | return E_SUCCESS; |
788 | 0 | } else { |
789 | 0 | return E_FAILED; |
790 | 0 | } |
791 | 0 | } |
792 | | |
793 | | /** |
794 | | * Convert an H3Index to the FaceIJK address on a specified icosahedral face. |
795 | | * @param h The H3Index. |
796 | | * @param fijk The FaceIJK address, initialized with the desired face |
797 | | * and normalized base cell coordinates. |
798 | | * @return Returns 1 if the possibility of overage exists, otherwise 0. |
799 | | */ |
800 | 0 | int _h3ToFaceIjkWithInitializedFijk(H3Index h, FaceIJK *fijk) { |
801 | 0 | CoordIJK *ijk = &fijk->coord; |
802 | 0 | int res = H3_GET_RESOLUTION(h); |
803 | | |
804 | | // center base cell hierarchy is entirely on this face |
805 | 0 | int possibleOverage = 1; |
806 | 0 | if (!_isBaseCellPentagon(H3_GET_BASE_CELL(h)) && |
807 | 0 | (res == 0 || |
808 | 0 | (fijk->coord.i == 0 && fijk->coord.j == 0 && fijk->coord.k == 0))) |
809 | 0 | possibleOverage = 0; |
810 | |
|
811 | 0 | for (int r = 1; r <= res; r++) { |
812 | 0 | if (isResolutionClassIII(r)) { |
813 | | // Class III == rotate ccw |
814 | 0 | _downAp7(ijk); |
815 | 0 | } else { |
816 | | // Class II == rotate cw |
817 | 0 | _downAp7r(ijk); |
818 | 0 | } |
819 | |
|
820 | 0 | _neighbor(ijk, H3_GET_INDEX_DIGIT(h, r)); |
821 | 0 | } |
822 | |
|
823 | 0 | return possibleOverage; |
824 | 0 | } |
825 | | |
826 | | /** |
827 | | * Convert an H3Index to a FaceIJK address. |
828 | | * @param h The H3Index. |
829 | | * @param fijk The corresponding FaceIJK address. |
830 | | */ |
831 | 0 | H3Error _h3ToFaceIjk(H3Index h, FaceIJK *fijk) { |
832 | 0 | int baseCell = H3_GET_BASE_CELL(h); |
833 | 0 | if (NEVER(baseCell < 0) || baseCell >= NUM_BASE_CELLS) { |
834 | | // Base cells less than zero can not be represented in an index |
835 | | // To prevent reading uninitialized memory, we zero the output. |
836 | 0 | fijk->face = 0; |
837 | 0 | fijk->coord.i = fijk->coord.j = fijk->coord.k = 0; |
838 | 0 | return E_CELL_INVALID; |
839 | 0 | } |
840 | | // adjust for the pentagonal missing sequence; all of sub-sequence 5 needs |
841 | | // to be adjusted (and some of sub-sequence 4 below) |
842 | 0 | if (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 5) |
843 | 0 | h = _h3Rotate60cw(h); |
844 | | |
845 | | // start with the "home" face and ijk+ coordinates for the base cell of c |
846 | 0 | *fijk = baseCellData[baseCell].homeFijk; |
847 | 0 | if (!_h3ToFaceIjkWithInitializedFijk(h, fijk)) |
848 | 0 | return E_SUCCESS; // no overage is possible; h lies on this face |
849 | | |
850 | | // if we're here we have the potential for an "overage"; i.e., it is |
851 | | // possible that c lies on an adjacent face |
852 | | |
853 | 0 | CoordIJK origIJK = fijk->coord; |
854 | | |
855 | | // if we're in Class III, drop into the next finer Class II grid |
856 | 0 | int res = H3_GET_RESOLUTION(h); |
857 | 0 | if (isResolutionClassIII(res)) { |
858 | | // Class III |
859 | 0 | _downAp7r(&fijk->coord); |
860 | 0 | res++; |
861 | 0 | } |
862 | | |
863 | | // adjust for overage if needed |
864 | | // a pentagon base cell with a leading 4 digit requires special handling |
865 | 0 | int pentLeading4 = |
866 | 0 | (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 4); |
867 | 0 | if (_adjustOverageClassII(fijk, res, pentLeading4, 0) != NO_OVERAGE) { |
868 | | // if the base cell is a pentagon we have the potential for secondary |
869 | | // overages |
870 | 0 | if (_isBaseCellPentagon(baseCell)) { |
871 | 0 | while (_adjustOverageClassII(fijk, res, 0, 0) != NO_OVERAGE) |
872 | 0 | continue; |
873 | 0 | } |
874 | |
|
875 | 0 | if (res != H3_GET_RESOLUTION(h)) _upAp7r(&fijk->coord); |
876 | 0 | } else if (res != H3_GET_RESOLUTION(h)) { |
877 | 0 | fijk->coord = origIJK; |
878 | 0 | } |
879 | 0 | return E_SUCCESS; |
880 | 0 | } |
881 | | |
882 | | /** |
883 | | * Determines the spherical coordinates of the center point of an H3 index. |
884 | | * |
885 | | * @param h3 The H3 index. |
886 | | * @param g The spherical coordinates of the H3 cell center. |
887 | | */ |
888 | 0 | H3Error H3_EXPORT(cellToLatLng)(H3Index h3, LatLng *g) { |
889 | 0 | FaceIJK fijk; |
890 | 0 | H3Error e = _h3ToFaceIjk(h3, &fijk); |
891 | 0 | if (e) { |
892 | 0 | return e; |
893 | 0 | } |
894 | 0 | _faceIjkToGeo(&fijk, H3_GET_RESOLUTION(h3), g); |
895 | 0 | return E_SUCCESS; |
896 | 0 | } |
897 | | |
898 | | /** |
899 | | * Determines the cell boundary in spherical coordinates for an H3 index. |
900 | | * |
901 | | * @param h3 The H3 index. |
902 | | * @param cb The boundary of the H3 cell in spherical coordinates. |
903 | | */ |
904 | 0 | H3Error H3_EXPORT(cellToBoundary)(H3Index h3, CellBoundary *cb) { |
905 | 0 | FaceIJK fijk; |
906 | 0 | H3Error e = _h3ToFaceIjk(h3, &fijk); |
907 | 0 | if (e) { |
908 | 0 | return e; |
909 | 0 | } |
910 | 0 | if (H3_EXPORT(isPentagon)(h3)) { |
911 | 0 | _faceIjkPentToCellBoundary(&fijk, H3_GET_RESOLUTION(h3), 0, |
912 | 0 | NUM_PENT_VERTS, cb); |
913 | 0 | } else { |
914 | 0 | _faceIjkToCellBoundary(&fijk, H3_GET_RESOLUTION(h3), 0, NUM_HEX_VERTS, |
915 | 0 | cb); |
916 | 0 | } |
917 | 0 | return E_SUCCESS; |
918 | 0 | } |
919 | | |
920 | | /** |
921 | | * Returns the max number of possible icosahedron faces an H3 index |
922 | | * may intersect. |
923 | | * |
924 | | * @return int count of faces |
925 | | */ |
926 | 0 | H3Error H3_EXPORT(maxFaceCount)(H3Index h3, int *out) { |
927 | | // a pentagon always intersects 5 faces, a hexagon never intersects more |
928 | | // than 2 (but may only intersect 1) |
929 | 0 | *out = H3_EXPORT(isPentagon)(h3) ? 5 : 2; |
930 | 0 | return E_SUCCESS; |
931 | 0 | } |
932 | | |
933 | | /** |
934 | | * Find all icosahedron faces intersected by a given H3 index, represented |
935 | | * as integers from 0-19. The array is sparse; since 0 is a valid value, |
936 | | * invalid array values are represented as -1. It is the responsibility of |
937 | | * the caller to filter out invalid values. |
938 | | * |
939 | | * @param h3 The H3 index |
940 | | * @param out Output array. Must be of size maxFaceCount(h3). |
941 | | */ |
942 | 0 | H3Error H3_EXPORT(getIcosahedronFaces)(H3Index h3, int *out) { |
943 | 0 | int res = H3_GET_RESOLUTION(h3); |
944 | 0 | int isPent = H3_EXPORT(isPentagon)(h3); |
945 | | |
946 | | // We can't use the vertex-based approach here for class II pentagons, |
947 | | // because all their vertices are on the icosahedron edges. Their |
948 | | // direct child pentagons cross the same faces, so use those instead. |
949 | 0 | if (isPent && !isResolutionClassIII(res)) { |
950 | | // Note that this would not work for res 15, but this is only run on |
951 | | // Class II pentagons, it should never be invoked for a res 15 index. |
952 | 0 | H3Index childPentagon = makeDirectChild(h3, 0); |
953 | 0 | return H3_EXPORT(getIcosahedronFaces)(childPentagon, out); |
954 | 0 | } |
955 | | |
956 | | // convert to FaceIJK |
957 | 0 | FaceIJK fijk; |
958 | 0 | H3Error err = _h3ToFaceIjk(h3, &fijk); |
959 | 0 | if (err) { |
960 | 0 | return err; |
961 | 0 | } |
962 | | |
963 | | // Get all vertices as FaceIJK addresses. For simplicity, always |
964 | | // initialize the array with 6 verts, ignoring the last one for pentagons |
965 | 0 | FaceIJK fijkVerts[NUM_HEX_VERTS]; |
966 | 0 | int vertexCount; |
967 | |
|
968 | 0 | if (isPent) { |
969 | 0 | vertexCount = NUM_PENT_VERTS; |
970 | 0 | _faceIjkPentToVerts(&fijk, &res, fijkVerts); |
971 | 0 | } else { |
972 | 0 | vertexCount = NUM_HEX_VERTS; |
973 | 0 | _faceIjkToVerts(&fijk, &res, fijkVerts); |
974 | 0 | } |
975 | | |
976 | | // We may not use all of the slots in the output array, |
977 | | // so fill with invalid values to indicate unused slots |
978 | 0 | int faceCount; |
979 | 0 | H3Error maxFaceCountError = H3_EXPORT(maxFaceCount)(h3, &faceCount); |
980 | 0 | if (NEVER(maxFaceCountError != E_SUCCESS)) { |
981 | 0 | return maxFaceCountError; |
982 | 0 | } |
983 | 0 | for (int i = 0; i < faceCount; i++) { |
984 | 0 | out[i] = INVALID_FACE; |
985 | 0 | } |
986 | | |
987 | | // add each vertex face, using the output array as a hash set |
988 | 0 | for (int i = 0; i < vertexCount; i++) { |
989 | 0 | FaceIJK *vert = &fijkVerts[i]; |
990 | | |
991 | | // Adjust overage, determining whether this vertex is |
992 | | // on another face |
993 | 0 | if (isPent) { |
994 | 0 | _adjustPentVertOverage(vert, res); |
995 | 0 | } else { |
996 | 0 | _adjustOverageClassII(vert, res, 0, 1); |
997 | 0 | } |
998 | | |
999 | | // Save the face to the output array |
1000 | 0 | int face = vert->face; |
1001 | 0 | int pos = 0; |
1002 | | // Find the first empty output position, or the first position |
1003 | | // matching the current face |
1004 | 0 | while (out[pos] != INVALID_FACE && out[pos] != face) { |
1005 | 0 | pos++; |
1006 | 0 | if (pos >= faceCount) { |
1007 | | // Mismatch between the heuristic used in maxFaceCount and |
1008 | | // calculation here - indicates an invalid index. |
1009 | 0 | return E_FAILED; |
1010 | 0 | } |
1011 | 0 | } |
1012 | 0 | out[pos] = face; |
1013 | 0 | } |
1014 | 0 | return E_SUCCESS; |
1015 | 0 | } |
1016 | | |
1017 | | /** |
1018 | | * pentagonCount returns the number of pentagons (same at any resolution) |
1019 | | * |
1020 | | * @return int count of pentagon indexes |
1021 | | */ |
1022 | 0 | int H3_EXPORT(pentagonCount)() { return NUM_PENTAGONS; } |
1023 | | |
1024 | | /** |
1025 | | * Generates all pentagons at the specified resolution |
1026 | | * |
1027 | | * @param res The resolution to produce pentagons at. |
1028 | | * @param out Output array. Must be of size pentagonCount(). |
1029 | | */ |
1030 | 0 | H3Error H3_EXPORT(getPentagons)(int res, H3Index *out) { |
1031 | 0 | if (res < 0 || res > MAX_H3_RES) { |
1032 | 0 | return E_RES_DOMAIN; |
1033 | 0 | } |
1034 | 0 | int i = 0; |
1035 | 0 | for (int bc = 0; bc < NUM_BASE_CELLS; bc++) { |
1036 | 0 | if (_isBaseCellPentagon(bc)) { |
1037 | 0 | H3Index pentagon; |
1038 | 0 | setH3Index(&pentagon, res, bc, 0); |
1039 | 0 | out[i++] = pentagon; |
1040 | 0 | } |
1041 | 0 | } |
1042 | 0 | return E_SUCCESS; |
1043 | 0 | } |
1044 | | |
1045 | | /** |
1046 | | * Returns whether or not a resolution is a Class III grid. Note that odd |
1047 | | * resolutions are Class III and even resolutions are Class II. |
1048 | | * @param res The H3 resolution. |
1049 | | * @return 1 if the resolution is a Class III grid, and 0 if the resolution is |
1050 | | * a Class II grid. |
1051 | | */ |
1052 | 0 | int isResolutionClassIII(int res) { return res % 2; } |
1053 | | |
1054 | | /** |
1055 | | * Validate a child position in the context of a given parent, returning |
1056 | | * an error if validation fails. |
1057 | | */ |
1058 | | static H3Error validateChildPos(int64_t childPos, H3Index parent, |
1059 | 0 | int childRes) { |
1060 | 0 | int64_t maxChildCount; |
1061 | 0 | H3Error sizeError = |
1062 | 0 | H3_EXPORT(cellToChildrenSize)(parent, childRes, &maxChildCount); |
1063 | 0 | if (NEVER(sizeError)) { |
1064 | 0 | return sizeError; |
1065 | 0 | } |
1066 | 0 | if (childPos < 0 || childPos >= maxChildCount) { |
1067 | 0 | return E_DOMAIN; |
1068 | 0 | } |
1069 | 0 | return E_SUCCESS; |
1070 | 0 | } |
1071 | | |
1072 | | /** |
1073 | | * Returns the position of the cell within an ordered list of all children of |
1074 | | * the cell's parent at the specified resolution |
1075 | | */ |
1076 | 0 | H3Error H3_EXPORT(cellToChildPos)(H3Index child, int parentRes, int64_t *out) { |
1077 | 0 | int childRes = H3_GET_RESOLUTION(child); |
1078 | | // Get the parent at res. This will catch any resolution errors |
1079 | 0 | H3Index originalParent; |
1080 | 0 | H3Error parentError = |
1081 | 0 | H3_EXPORT(cellToParent(child, parentRes, &originalParent)); |
1082 | 0 | if (parentError) { |
1083 | 0 | return parentError; |
1084 | 0 | } |
1085 | | |
1086 | | // Define the initial parent. Note that these variables are reassigned |
1087 | | // within the loop. |
1088 | 0 | H3Index parent = originalParent; |
1089 | 0 | int parentIsPentagon = H3_EXPORT(isPentagon)(parent); |
1090 | | |
1091 | | // Walk up the resolution digits, incrementing the index |
1092 | 0 | *out = 0; |
1093 | 0 | if (parentIsPentagon) { |
1094 | | // Pentagon logic. Pentagon parents skip the 1 digit, so the offsets are |
1095 | | // different from hexagons |
1096 | 0 | for (int res = childRes; res > parentRes; res--) { |
1097 | 0 | H3Error parentError = |
1098 | 0 | H3_EXPORT(cellToParent(child, res - 1, &parent)); |
1099 | 0 | if (NEVER(parentError)) { |
1100 | 0 | return parentError; |
1101 | 0 | } |
1102 | | |
1103 | 0 | parentIsPentagon = H3_EXPORT(isPentagon)(parent); |
1104 | 0 | int rawDigit = H3_GET_INDEX_DIGIT(child, res); |
1105 | | // Validate the digit before proceeding |
1106 | 0 | if (rawDigit == INVALID_DIGIT || |
1107 | 0 | (parentIsPentagon && rawDigit == K_AXES_DIGIT)) { |
1108 | 0 | return E_CELL_INVALID; |
1109 | 0 | } |
1110 | 0 | int digit = |
1111 | 0 | parentIsPentagon && rawDigit > 0 ? rawDigit - 1 : rawDigit; |
1112 | 0 | if (digit != CENTER_DIGIT) { |
1113 | 0 | int64_t hexChildCount = _ipow(7, childRes - res); |
1114 | | // The offset for the 0-digit slot depends on whether the |
1115 | | // current index is the child of a pentagon. If so, the offset |
1116 | | // is based on the count of pentagon children, otherwise, |
1117 | | // hexagon children. |
1118 | 0 | *out += (parentIsPentagon |
1119 | 0 | ? // pentagon children. See the explanation |
1120 | | // for getNumCells in h3api.h.in |
1121 | 0 | 1 + (5 * (hexChildCount - 1)) / 6 |
1122 | 0 | : // one hexagon's children |
1123 | 0 | hexChildCount) + |
1124 | | // the other hexagon children |
1125 | 0 | (digit - 1) * hexChildCount; |
1126 | 0 | } |
1127 | 0 | } |
1128 | 0 | } else { |
1129 | | // Hexagon logic. Offsets are simple powers of 7 |
1130 | 0 | for (int res = childRes; res > parentRes; res--) { |
1131 | 0 | int digit = H3_GET_INDEX_DIGIT(child, res); |
1132 | 0 | if (digit == INVALID_DIGIT) { |
1133 | 0 | return E_CELL_INVALID; |
1134 | 0 | } |
1135 | 0 | *out += digit * _ipow(7, childRes - res); |
1136 | 0 | } |
1137 | 0 | } |
1138 | | |
1139 | 0 | if (NEVER(validateChildPos(*out, originalParent, childRes))) { |
1140 | | // This is the result of an internal error, so return E_FAILED |
1141 | | // instead of the validation error |
1142 | 0 | return E_FAILED; |
1143 | 0 | } |
1144 | | |
1145 | 0 | return E_SUCCESS; |
1146 | 0 | } |
1147 | | |
1148 | | /** |
1149 | | * Returns the child cell at a given position within an ordered list of all |
1150 | | * children at the specified resolution */ |
1151 | | H3Error H3_EXPORT(childPosToCell)(int64_t childPos, H3Index parent, |
1152 | 0 | int childRes, H3Index *child) { |
1153 | | // Validate resolution |
1154 | 0 | if (childRes < 0 || childRes > MAX_H3_RES) { |
1155 | 0 | return E_RES_DOMAIN; |
1156 | 0 | } |
1157 | | // Validate parent resolution |
1158 | 0 | int parentRes = H3_GET_RESOLUTION(parent); |
1159 | 0 | if (childRes < parentRes) { |
1160 | 0 | return E_RES_MISMATCH; |
1161 | 0 | } |
1162 | | // Validate child pos |
1163 | 0 | H3Error childPosErr = validateChildPos(childPos, parent, childRes); |
1164 | 0 | if (childPosErr) { |
1165 | 0 | return childPosErr; |
1166 | 0 | } |
1167 | | |
1168 | 0 | int resOffset = childRes - parentRes; |
1169 | |
|
1170 | 0 | *child = parent; |
1171 | 0 | int64_t idx = childPos; |
1172 | |
|
1173 | 0 | H3_SET_RESOLUTION(*child, childRes); |
1174 | |
|
1175 | 0 | if (H3_EXPORT(isPentagon)(parent)) { |
1176 | | // Pentagon tile logic. Pentagon tiles skip the 1 digit, so the offsets |
1177 | | // are different |
1178 | 0 | bool inPent = true; |
1179 | 0 | for (int res = 1; res <= resOffset; res++) { |
1180 | 0 | int64_t resWidth = _ipow(7, resOffset - res); |
1181 | 0 | if (inPent) { |
1182 | | // While we are inside a parent pentagon, we need to check if |
1183 | | // this cell is a pentagon, and if not, we need to offset its |
1184 | | // digit to account for the skipped direction |
1185 | 0 | int64_t pentWidth = 1 + (5 * (resWidth - 1)) / 6; |
1186 | 0 | if (idx < pentWidth) { |
1187 | 0 | H3_SET_INDEX_DIGIT(*child, parentRes + res, 0); |
1188 | 0 | } else { |
1189 | 0 | idx -= pentWidth; |
1190 | 0 | inPent = false; |
1191 | 0 | H3_SET_INDEX_DIGIT(*child, parentRes + res, |
1192 | 0 | (idx / resWidth) + 2); |
1193 | 0 | idx %= resWidth; |
1194 | 0 | } |
1195 | 0 | } else { |
1196 | | // We're no longer inside a pentagon, continue as for hex |
1197 | 0 | H3_SET_INDEX_DIGIT(*child, parentRes + res, idx / resWidth); |
1198 | 0 | idx %= resWidth; |
1199 | 0 | } |
1200 | 0 | } |
1201 | 0 | } else { |
1202 | | // Hexagon tile logic. Offsets are simple powers of 7 |
1203 | 0 | for (int res = 1; res <= resOffset; res++) { |
1204 | 0 | int64_t resWidth = _ipow(7, resOffset - res); |
1205 | 0 | H3_SET_INDEX_DIGIT(*child, parentRes + res, idx / resWidth); |
1206 | 0 | idx %= resWidth; |
1207 | 0 | } |
1208 | 0 | } |
1209 | |
|
1210 | 0 | return E_SUCCESS; |
1211 | 0 | } |