OmniSciDB  a5dc49c757
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
h3Index.hpp
Go to the documentation of this file.
1 /*
2  * Copyright 2016-2019 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  */
21 
22 // #include <faceijk.h>
23 // #include <inttypes.h>
24 // #include <math.h>
25 // #include <stdlib.h>
26 // #include <string.h>
27 
28 // #include "alloc.h"
30 // #include "faceijk.h"
31 // #include "mathExtensions.h"
32 
33 // /**
34 // * Returns the H3 resolution of an H3 index.
35 // * @param h The H3 index.
36 // * @return The resolution of the H3 index argument.
37 // */
38 // int H3_EXPORT(h3GetResolution)(H3Index h) { return H3_GET_RESOLUTION(h); }
39 
40 // /**
41 // * Returns the H3 base cell "number" of an H3 cell (hexagon or pentagon).
42 // *
43 // * Note: Technically works on H3 edges, but will return base cell of the
44 // * origin cell.
45 // *
46 // * @param h The H3 cell.
47 // * @return The base cell "number" of the H3 cell argument.
48 // */
49 // int H3_EXPORT(h3GetBaseCell)(H3Index h) { return H3_GET_BASE_CELL(h); }
50 
51 // /**
52 // * Converts a string representation of an H3 index into an H3 index.
53 // * @param str The string representation of an H3 index.
54 // * @return The H3 index corresponding to the string argument, or H3_NULL if
55 // * invalid.
56 // */
57 // H3Index H3_EXPORT(stringToH3)(const char* str) {
58 // H3Index h = H3_NULL;
59 // // If failed, h will be unmodified and we should return H3_NULL anyways.
60 // sscanf(str, "%" PRIx64, &h);
61 // return h;
62 // }
63 
64 // /**
65 // * Converts an H3 index into a string representation.
66 // * @param h The H3 index to convert.
67 // * @param str The string representation of the H3 index.
68 // * @param sz Size of the buffer `str`
69 // */
70 // void H3_EXPORT(h3ToString)(H3Index h, char* str, size_t sz) {
71 // // An unsigned 64 bit integer will be expressed in at most
72 // // 16 digits plus 1 for the null terminator.
73 // if (sz < 17) {
74 // // Buffer is potentially not large enough.
75 // return;
76 // }
77 // sprintf(str, "%" PRIx64, h);
78 // }
79 
80 // /**
81 // * Returns whether or not an H3 index is a valid cell (hexagon or pentagon).
82 // * @param h The H3 index to validate.
83 // * @return 1 if the H3 index if valid, and 0 if it is not.
84 // */
85 // int H3_EXPORT(h3IsValid)(H3Index h) {
86 // if (H3_GET_HIGH_BIT(h) != 0) return 0;
87 
88 // if (H3_GET_MODE(h) != H3_HEXAGON_MODE) return 0;
89 
90 // if (H3_GET_RESERVED_BITS(h) != 0) return 0;
91 
92 // int baseCell = H3_GET_BASE_CELL(h);
93 // if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) return 0;
94 
95 // int res = H3_GET_RESOLUTION(h);
96 // if (res < 0 || res > MAX_H3_RES) return 0;
97 
98 // bool foundFirstNonZeroDigit = false;
99 // for (int r = 1; r <= res; r++) {
100 // Direction digit = H3_GET_INDEX_DIGIT(h, r);
101 
102 // if (!foundFirstNonZeroDigit && digit != CENTER_DIGIT) {
103 // foundFirstNonZeroDigit = true;
104 // if (_isBaseCellPentagon(baseCell) && digit == K_AXES_DIGIT) {
105 // return 0;
106 // }
107 // }
108 
109 // if (digit < CENTER_DIGIT || digit >= NUM_DIGITS) return 0;
110 // }
111 
112 // for (int r = res + 1; r <= MAX_H3_RES; r++) {
113 // Direction digit = H3_GET_INDEX_DIGIT(h, r);
114 // if (digit != INVALID_DIGIT) return 0;
115 // }
116 
117 // return 1;
118 // }
119 
120 // /**
121 // * Initializes an H3 index.
122 // * @param hp The H3 index to initialize.
123 // * @param res The H3 resolution to initialize the index to.
124 // * @param baseCell The H3 base cell to initialize the index to.
125 // * @param initDigit The H3 digit (0-7) to initialize all of the index digits to.
126 // */
127 // void setH3Index(H3Index* hp, int res, int baseCell, Direction initDigit) {
128 // H3Index h = H3_INIT;
129 // H3_SET_MODE(h, H3_HEXAGON_MODE);
130 // H3_SET_RESOLUTION(h, res);
131 // H3_SET_BASE_CELL(h, baseCell);
132 // for (int r = 1; r <= res; r++) H3_SET_INDEX_DIGIT(h, r, initDigit);
133 // *hp = h;
134 // }
135 
145  int childRes = H3_GET_RESOLUTION(h);
146  if (parentRes > childRes) {
147  return H3_NULL;
148  } else if (parentRes == childRes) {
149  return h;
150  } else if (parentRes < 0 || parentRes > MAX_H3_RES) {
151  return H3_NULL;
152  }
153  H3Index parentH = H3_SET_RESOLUTION(h, parentRes);
154  for (int i = parentRes + 1; i <= childRes; i++) {
155  H3_SET_INDEX_DIGIT(parentH, i, H3_DIGIT_MASK);
156  }
157  return parentH;
158 }
159 
160 // /**
161 // * Determines whether one resolution is a valid child resolution of another.
162 // * Each resolution is considered a valid child resolution of itself.
163 // *
164 // * @param parentRes int resolution of the parent
165 // * @param childRes int resolution of the child
166 // *
167 // * @return The validity of the child resolution
168 // */
169 // static bool _isValidChildRes(int parentRes, int childRes) {
170 // if (childRes < parentRes || childRes > MAX_H3_RES) {
171 // return false;
172 // }
173 // return true;
174 // }
175 
176 // /**
177 // * maxH3ToChildrenSize returns the maximum number of children possible for a
178 // * given child level.
179 // *
180 // * @param h H3Index to find the number of children of
181 // * @param childRes The resolution of the child level you're interested in
182 // *
183 // * @return int count of maximum number of children (equal for hexagons, less for
184 // * pentagons
185 // */
186 // int64_t H3_EXPORT(maxH3ToChildrenSize)(H3Index h, int childRes) {
187 // int parentRes = H3_GET_RESOLUTION(h);
188 // if (!_isValidChildRes(parentRes, childRes)) {
189 // return 0;
190 // }
191 // return _ipow(7, (childRes - parentRes));
192 // }
193 
194 // /**
195 // * makeDirectChild takes an index and immediately returns the immediate child
196 // * index based on the specified cell number. Bit operations only, could generate
197 // * invalid indexes if not careful (deleted cell under a pentagon).
198 // *
199 // * @param h H3Index to find the direct child of
200 // * @param cellNumber int id of the direct child (0-6)
201 // *
202 // * @return The new H3Index for the child
203 // */
204 // H3Index makeDirectChild(H3Index h, int cellNumber) {
205 // int childRes = H3_GET_RESOLUTION(h) + 1;
206 // H3Index childH = H3_SET_RESOLUTION(h, childRes);
207 // H3_SET_INDEX_DIGIT(childH, childRes, cellNumber);
208 // return childH;
209 // }
210 
211 // /**
212 // * h3ToChildren takes the given hexagon id and generates all of the children
213 // * at the specified resolution storing them into the provided memory pointer.
214 // * It's assumed that maxH3ToChildrenSize was used to determine the allocation.
215 // *
216 // * @param h H3Index to find the children of
217 // * @param childRes int the child level to produce
218 // * @param children H3Index* the memory to store the resulting addresses in
219 // */
220 // void H3_EXPORT(h3ToChildren)(H3Index h, int childRes, H3Index* children) {
221 // int parentRes = H3_GET_RESOLUTION(h);
222 // if (!_isValidChildRes(parentRes, childRes)) {
223 // return;
224 // } else if (parentRes == childRes) {
225 // *children = h;
226 // return;
227 // }
228 // int bufferSize = H3_EXPORT(maxH3ToChildrenSize)(h, childRes);
229 // int bufferChildStep = (bufferSize / 7);
230 // int isAPentagon = H3_EXPORT(h3IsPentagon)(h);
231 // for (int i = 0; i < 7; i++) {
232 // if (isAPentagon && i == K_AXES_DIGIT) {
233 // H3Index* nextChild = children + bufferChildStep;
234 // while (children < nextChild) {
235 // *children = H3_NULL;
236 // children++;
237 // }
238 // } else {
239 // H3_EXPORT(h3ToChildren)(makeDirectChild(h, i), childRes, children);
240 // children += bufferChildStep;
241 // }
242 // }
243 // }
244 
245 // /**
246 // * h3ToCenterChild produces the center child index for a given H3 index at
247 // * the specified resolution
248 // *
249 // * @param h H3Index to find center child of
250 // * @param childRes The resolution to switch to
251 // *
252 // * @return H3Index of the center child, or H3_NULL if you actually asked for a
253 // * parent
254 // */
255 // H3Index H3_EXPORT(h3ToCenterChild)(H3Index h, int childRes) {
256 // int parentRes = H3_GET_RESOLUTION(h);
257 // if (!_isValidChildRes(parentRes, childRes)) {
258 // return H3_NULL;
259 // } else if (childRes == parentRes) {
260 // return h;
261 // }
262 // H3Index child = H3_SET_RESOLUTION(h, childRes);
263 // for (int i = parentRes + 1; i <= childRes; i++) {
264 // H3_SET_INDEX_DIGIT(child, i, 0);
265 // }
266 // return child;
267 // }
268 
269 // /**
270 // * compact takes a set of hexagons all at the same resolution and compresses
271 // * them by pruning full child branches to the parent level. This is also done
272 // * for all parents recursively to get the minimum number of hex addresses that
273 // * perfectly cover the defined space.
274 // * @param h3Set Set of hexagons
275 // * @param compactedSet The output array of compressed hexagons (preallocated)
276 // * @param numHexes The size of the input and output arrays (possible that no
277 // * contiguous regions exist in the set at all and no compression possible)
278 // * @return an error code on bad input data
279 // */
280 // int H3_EXPORT(compact)(const H3Index* h3Set, H3Index* compactedSet,
281 // const int numHexes) {
282 // if (numHexes == 0) {
283 // return COMPACT_SUCCESS;
284 // }
285 // int res = H3_GET_RESOLUTION(h3Set[0]);
286 // if (res == 0) {
287 // // No compaction possible, just copy the set to output
288 // for (int i = 0; i < numHexes; i++) {
289 // compactedSet[i] = h3Set[i];
290 // }
291 // return COMPACT_SUCCESS;
292 // }
293 // H3Index* remainingHexes = H3_MEMORY(malloc)(numHexes * sizeof(H3Index));
294 // if (!remainingHexes) {
295 // return COMPACT_ALLOC_FAILED;
296 // }
297 // memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
298 // H3Index* hashSetArray = H3_MEMORY(calloc)(numHexes, sizeof(H3Index));
299 // if (!hashSetArray) {
300 // H3_MEMORY(free)(remainingHexes);
301 // return COMPACT_ALLOC_FAILED;
302 // }
303 // H3Index* compactedSetOffset = compactedSet;
304 // int numRemainingHexes = numHexes;
305 // while (numRemainingHexes) {
306 // res = H3_GET_RESOLUTION(remainingHexes[0]);
307 // int parentRes = res - 1;
308 // // Put the parents of the hexagons into the temp array
309 // // via a hashing mechanism, and use the reserved bits
310 // // to track how many times a parent is duplicated
311 // for (int i = 0; i < numRemainingHexes; i++) {
312 // H3Index currIndex = remainingHexes[i];
313 // if (currIndex != 0) {
314 // H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
315 // // Modulus hash the parent into the temp array
316 // int loc = (int)(parent % numRemainingHexes);
317 // int loopCount = 0;
318 // while (hashSetArray[loc] != 0) {
319 // if (loopCount > numRemainingHexes) { // LCOV_EXCL_BR_LINE
320 // // LCOV_EXCL_START
321 // // This case should not be possible because at most one
322 // // index is placed into hashSetArray per
323 // // numRemainingHexes.
324 // H3_MEMORY(free)(remainingHexes);
325 // H3_MEMORY(free)(hashSetArray);
326 // return COMPACT_LOOP_EXCEEDED;
327 // // LCOV_EXCL_STOP
328 // }
329 // H3Index tempIndex =
330 // hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
331 // if (tempIndex == parent) {
332 // int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
333 // int limitCount = 7;
334 // if (H3_EXPORT(h3IsPentagon)(
335 // tempIndex & H3_RESERVED_MASK_NEGATIVE)) {
336 // limitCount--;
337 // }
338 // // One is added to count for this check to match one
339 // // being added to count later in this function when
340 // // checking for all children being present.
341 // if (count + 1 > limitCount) {
342 // // Only possible on duplicate input
343 // H3_MEMORY(free)(remainingHexes);
344 // H3_MEMORY(free)(hashSetArray);
345 // return COMPACT_DUPLICATE;
346 // }
347 // H3_SET_RESERVED_BITS(parent, count);
348 // hashSetArray[loc] = H3_NULL;
349 // } else {
350 // loc = (loc + 1) % numRemainingHexes;
351 // }
352 // loopCount++;
353 // }
354 // hashSetArray[loc] = parent;
355 // }
356 // }
357 // // Determine which parent hexagons have a complete set
358 // // of children and put them in the compactableHexes array
359 // int compactableCount = 0;
360 // int maxCompactableCount =
361 // numRemainingHexes / 6; // Somehow all pentagons; conservative
362 // if (maxCompactableCount == 0) {
363 // memcpy(compactedSetOffset, remainingHexes,
364 // numRemainingHexes * sizeof(remainingHexes[0]));
365 // break;
366 // }
367 // H3Index* compactableHexes =
368 // H3_MEMORY(calloc)(maxCompactableCount, sizeof(H3Index));
369 // if (!compactableHexes) {
370 // H3_MEMORY(free)(remainingHexes);
371 // H3_MEMORY(free)(hashSetArray);
372 // return COMPACT_ALLOC_FAILED;
373 // }
374 // for (int i = 0; i < numRemainingHexes; i++) {
375 // if (hashSetArray[i] == 0) continue;
376 // int count = H3_GET_RESERVED_BITS(hashSetArray[i]) + 1;
377 // // Include the deleted direction for pentagons as implicitly "there"
378 // if (H3_EXPORT(h3IsPentagon)(hashSetArray[i] &
379 // H3_RESERVED_MASK_NEGATIVE)) {
380 // // We need this later on, no need to recalculate
381 // H3_SET_RESERVED_BITS(hashSetArray[i], count);
382 // // Increment count after setting the reserved bits,
383 // // since count is already incremented above, so it
384 // // will be the expected value for a complete hexagon.
385 // count++;
386 // }
387 // if (count == 7) {
388 // // Bingo! Full set!
389 // compactableHexes[compactableCount] =
390 // hashSetArray[i] & H3_RESERVED_MASK_NEGATIVE;
391 // compactableCount++;
392 // }
393 // }
394 // // Uncompactable hexes are immediately copied into the
395 // // output compactedSetOffset
396 // int uncompactableCount = 0;
397 // for (int i = 0; i < numRemainingHexes; i++) {
398 // H3Index currIndex = remainingHexes[i];
399 // if (currIndex != H3_NULL) {
400 // H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
401 // // Modulus hash the parent into the temp array
402 // // to determine if this index was included in
403 // // the compactableHexes array
404 // int loc = (int)(parent % numRemainingHexes);
405 // int loopCount = 0;
406 // bool isUncompactable = true;
407 // do {
408 // if (loopCount > numRemainingHexes) { // LCOV_EXCL_BR_LINE
409 // // LCOV_EXCL_START
410 // // This case should not be possible because at most one
411 // // index is placed into hashSetArray per input hexagon.
412 // H3_MEMORY(free)(compactableHexes);
413 // H3_MEMORY(free)(remainingHexes);
414 // H3_MEMORY(free)(hashSetArray);
415 // return COMPACT_LOOP_EXCEEDED;
416 // // LCOV_EXCL_STOP
417 // }
418 // H3Index tempIndex =
419 // hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
420 // if (tempIndex == parent) {
421 // int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
422 // if (count == 7) {
423 // isUncompactable = false;
424 // }
425 // break;
426 // } else {
427 // loc = (loc + 1) % numRemainingHexes;
428 // }
429 // loopCount++;
430 // } while (hashSetArray[loc] != parent);
431 // if (isUncompactable) {
432 // compactedSetOffset[uncompactableCount] = remainingHexes[i];
433 // uncompactableCount++;
434 // }
435 // }
436 // }
437 // // Set up for the next loop
438 // memset(hashSetArray, 0, numHexes * sizeof(H3Index));
439 // compactedSetOffset += uncompactableCount;
440 // memcpy(remainingHexes, compactableHexes,
441 // compactableCount * sizeof(H3Index));
442 // numRemainingHexes = compactableCount;
443 // H3_MEMORY(free)(compactableHexes);
444 // }
445 // H3_MEMORY(free)(remainingHexes);
446 // H3_MEMORY(free)(hashSetArray);
447 // return COMPACT_SUCCESS;
448 // }
449 
450 // /**
451 // * uncompact takes a compressed set of hexagons and expands back to the
452 // * original set of hexagons.
453 // * @param compactedSet Set of hexagons
454 // * @param numHexes The number of hexes in the input set
455 // * @param h3Set Output array of decompressed hexagons (preallocated)
456 // * @param maxHexes The size of the output array to bound check against
457 // * @param res The hexagon resolution to decompress to
458 // * @return An error code if output array is too small or any hexagon is
459 // * smaller than the output resolution.
460 // */
461 // int H3_EXPORT(uncompact)(const H3Index* compactedSet, const int numHexes,
462 // H3Index* h3Set, const int maxHexes, const int res) {
463 // int outOffset = 0;
464 // for (int i = 0; i < numHexes; i++) {
465 // if (compactedSet[i] == 0) continue;
466 // if (outOffset >= maxHexes) {
467 // // We went too far, abort!
468 // return -1;
469 // }
470 // int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
471 // if (!_isValidChildRes(currentRes, res)) {
472 // // Nonsensical. Abort.
473 // return -2;
474 // }
475 // if (currentRes == res) {
476 // // Just copy and move along
477 // h3Set[outOffset] = compactedSet[i];
478 // outOffset++;
479 // } else {
480 // // Bigger hexagon to reduce in size
481 // int numHexesToGen =
482 // H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
483 // if (outOffset + numHexesToGen > maxHexes) {
484 // // We're about to go too far, abort!
485 // return -1;
486 // }
487 // H3_EXPORT(h3ToChildren)(compactedSet[i], res, h3Set + outOffset);
488 // outOffset += numHexesToGen;
489 // }
490 // }
491 // return 0;
492 // }
493 
494 // /**
495 // * maxUncompactSize takes a compacted set of hexagons are provides an
496 // * upper-bound estimate of the size of the uncompacted set of hexagons.
497 // * @param compactedSet Set of hexagons
498 // * @param numHexes The number of hexes in the input set
499 // * @param res The hexagon resolution to decompress to
500 // * @return The number of hexagons to allocate memory for, or a negative
501 // * number if an error occurs.
502 // */
503 // int H3_EXPORT(maxUncompactSize)(const H3Index* compactedSet, const int numHexes,
504 // const int res) {
505 // int maxNumHexagons = 0;
506 // for (int i = 0; i < numHexes; i++) {
507 // if (compactedSet[i] == 0) continue;
508 // int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
509 // if (!_isValidChildRes(currentRes, res)) {
510 // // Nonsensical. Abort.
511 // return -1;
512 // }
513 // if (currentRes == res) {
514 // maxNumHexagons++;
515 // } else {
516 // // Bigger hexagon to reduce in size
517 // int numHexesToGen =
518 // H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
519 // maxNumHexagons += numHexesToGen;
520 // }
521 // }
522 // return maxNumHexagons;
523 // }
524 
525 // /**
526 // * h3IsResClassIII takes a hexagon ID and determines if it is in a
527 // * Class III resolution (rotated versus the icosahedron and subject
528 // * to shape distortion adding extra points on icosahedron edges, making
529 // * them not true hexagons).
530 // * @param h The H3Index to check.
531 // * @return Returns 1 if the hexagon is class III, otherwise 0.
532 // */
533 // int H3_EXPORT(h3IsResClassIII)(H3Index h) { return H3_GET_RESOLUTION(h) % 2; }
534 
535 // /**
536 // * h3IsPentagon takes an H3Index and determines if it is actually a
537 // * pentagon.
538 // * @param h The H3Index to check.
539 // * @return Returns 1 if it is a pentagon, otherwise 0.
540 // */
541 // int H3_EXPORT(h3IsPentagon)(H3Index h) {
542 // return _isBaseCellPentagon(H3_GET_BASE_CELL(h)) &&
543 // !_h3LeadingNonZeroDigit(h);
544 // }
545 
552  for (int r = 1; r <= H3_GET_RESOLUTION(h); r++)
553  if (H3_GET_INDEX_DIGIT(h, r))
554  return H3_GET_INDEX_DIGIT(h, r);
555 
556  // if we're here it's all 0's
557  return CENTER_DIGIT;
558 }
559 
565  // rotate in place; skips any leading 1 digits (k-axis)
566 
567  int foundFirstNonZeroDigit = 0;
568  for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
569  // rotate this digit
571 
572  // look for the first non-zero digit so we
573  // can adjust for deleted k-axes sequence
574  // if necessary
575  if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
576  foundFirstNonZeroDigit = 1;
577 
578  // adjust for deleted k-axes sequence
580  h = _h3Rotate60ccw(h);
581  }
582  }
583  return h;
584 }
585 
591  // rotate in place; skips any leading 1 digits (k-axis)
592 
593  int foundFirstNonZeroDigit = 0;
594  for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
595  // rotate this digit
597 
598  // look for the first non-zero digit so we
599  // can adjust for deleted k-axes sequence
600  // if necessary
601  if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
602  foundFirstNonZeroDigit = 1;
603 
604  // adjust for deleted k-axes sequence
606  h = _h3Rotate60cw(h);
607  }
608  }
609  return h;
610 }
611 
617  for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
618  Direction oldDigit = H3_GET_INDEX_DIGIT(h, r);
619  H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(oldDigit));
620  }
621 
622  return h;
623 }
624 
630  for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
632  }
633 
634  return h;
635 }
636 
644  // initialize the index
645  H3Index h = H3_INIT;
647  H3_SET_RESOLUTION(h, res);
648 
649  // check for res 0/base cell
650  if (res == 0) {
651  if (fijk[I_INDEX] > MAX_FACE_COORD || fijk[J_INDEX] > MAX_FACE_COORD ||
652  fijk[K_INDEX] > MAX_FACE_COORD) {
653  // out of range input
654  return H3_NULL;
655  }
656 
658  return h;
659  }
660 
661  // we need to find the correct base cell FaceIJK for this H3 index;
662  // start with the passed in face and resolution res ijk coordinates
663  // in that face's coordinate system
664  FaceIJK(fijkBC) = FaceIJK_clone(fijk);
665 
666  // build the H3Index from finest res up
667  // adjust r for the fact that the res 0 base cell offsets the indexing
668  // digits
669  CoordIJK_ptr(ijk) = fijkBC;
670  for (int r = res - 1; r >= 0; r--) {
671  CoordIJK(lastIJK) = CoordIJK_clone(ijk);
672  CoordIJK(lastCenter);
673  if (isResClassIII(r + 1)) {
674  // rotate ccw
675  _upAp7(ijk);
676  CoordIJK_copy(lastCenter, ijk);
677  _downAp7(lastCenter);
678  } else {
679  // rotate cw
680  _upAp7r(ijk);
681  CoordIJK_copy(lastCenter, ijk);
682  _downAp7r(lastCenter);
683  }
684 
685  CoordIJK(diff);
686  _ijkSub(lastIJK, lastCenter, diff);
687  _ijkNormalize(diff);
688 
689  H3_SET_INDEX_DIGIT(h, r + 1, _unitIjkToDigit(diff));
690  }
691 
692  // fijkBC should now hold the IJK of the base cell in the
693  // coordinate system of the current face
694 
695  if (fijkBC[I_INDEX] > MAX_FACE_COORD || fijkBC[J_INDEX] > MAX_FACE_COORD ||
696  fijkBC[K_INDEX] > MAX_FACE_COORD) {
697  // out of range input
698  return H3_NULL;
699  }
700 
701  // lookup the correct base cell
702  int baseCell = _faceIjkToBaseCell(fijkBC);
703  H3_SET_BASE_CELL(h, baseCell);
704 
705  // rotate if necessary to get canonical base cell orientation
706  // for this base cell
707  int numRots = _faceIjkToBaseCellCCWrot60(fijkBC);
708  if (_isBaseCellPentagon(baseCell)) {
709  // force rotation out of missing k-axes sub-sequence
711  // check for a cw/ccw offset face; default is ccw
712  if (_baseCellIsCwOffset(baseCell, fijkBC[FACE_INDEX])) {
713  h = _h3Rotate60cw(h);
714  } else {
715  h = _h3Rotate60ccw(h);
716  }
717  }
718 
719  for (int i = 0; i < numRots; i++)
720  h = _h3RotatePent60ccw(h);
721  } else {
722  for (int i = 0; i < numRots; i++) {
723  h = _h3Rotate60ccw(h);
724  }
725  }
726 
727  return h;
728 }
729 
731  const double lat,
732  int res) {
733  if (res < 0 || res > MAX_H3_RES) {
734  return H3_NULL;
735  }
736  if (!std::isfinite(lat) || !std::isfinite(lon)) {
737  return H3_NULL;
738  }
739 
740  FaceIJK(fijk);
741  GeoCoord(g) = {degsToRads(lat), degsToRads(lon)};
742  _geoToFaceIjk(g, res, fijk);
743  return _faceIjkToH3(fijk, res);
744 }
745 
754  int* ijk = fijk;
755  int res = H3_GET_RESOLUTION(h);
756 
757  // center base cell hierarchy is entirely on this face
758  int possibleOverage = 1;
760  (res == 0 || (fijk[I_INDEX] == 0 && fijk[J_INDEX] == 0 && fijk[K_INDEX] == 0)))
761  possibleOverage = 0;
762 
763  for (int r = 1; r <= res; r++) {
764  if (isResClassIII(r)) {
765  // Class III == rotate ccw
766  _downAp7(ijk);
767  } else {
768  // Class II == rotate cw
769  _downAp7r(ijk);
770  }
771 
772  _neighbor(ijk, H3_GET_INDEX_DIGIT(h, r));
773  }
774 
775  return possibleOverage;
776 }
777 
784  int baseCell = H3_GET_BASE_CELL(h);
785  // adjust for the pentagonal missing sequence; all of sub-sequence 5 needs
786  // to be adjusted (and some of sub-sequence 4 below)
787  if (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 5)
788  h = _h3Rotate60cw(h);
789 
790  // start with the "home" face and ijk+ coordinates for the base cell of c
791  FaceIJK_copy(fijk, baseCellData[baseCell].homeFijk);
792  if (!_h3ToFaceIjkWithInitializedFijk(h, fijk))
793  return true; // no overage is possible; h lies on this face
794 
795  // if we're here we have the potential for an "overage"; i.e., it is
796  // possible that c lies on an adjacent face
797 
798  CoordIJK(origIJK) = CoordIJK_clone(fijk);
799 
800  // if we're in Class III, drop into the next finer Class II grid
801  int res = H3_GET_RESOLUTION(h);
802  if (isResClassIII(res)) {
803  // Class III
804  _downAp7r(fijk);
805  res++;
806  }
807 
808  // adjust for overage if needed
809  // a pentagon base cell with a leading 4 digit requires special handling
810  int pentLeading4 = (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 4);
811  if (_adjustOverageClassII(fijk, res, pentLeading4, 0) != NO_OVERAGE) {
812  // if the base cell is a pentagon we have the potential for secondary
813  // overages
814  if (_isBaseCellPentagon(baseCell)) {
815  while (_adjustOverageClassII(fijk, res, 0, 0) != NO_OVERAGE)
816  continue;
817  }
818 
819  if (res != H3_GET_RESOLUTION(h))
820  _upAp7r(fijk);
821  } else if (res != H3_GET_RESOLUTION(h)) {
822  CoordIJK_copy(fijk, origIJK);
823  }
824  return true;
825 }
826 
835  FaceIJK(fijk);
836  _h3ToFaceIjk(h3, fijk);
837  _faceIjkToGeo(fijk, H3_GET_RESOLUTION(h3), g);
838  return true;
839 }
840 
854  GeoCoord(g);
855  _h3ToGeo(h3, g);
856 
857  // and pack as two 9.22 fixed-point values into 64-bits. Going to preserve 6 decimal
858  // places (hence the 1000000.0 magic number). Lon range will be 0-360 and lat 0-180 in
859  // order to keep the cast to int64_t positive for easier packing. We could add extra
860  // precision if we use a uint64_t, but unfortunately uint64_t is an unsupported type
861  // thru calcite. The +0.5 is for rounding.
862  int64_t decimal_lon =
863  static_cast<int64_t>((radsToDegs(g[LON_INDEX]) + 180.0f) * 1000000.0 + 0.5);
864  int64_t decimal_lat =
865  static_cast<int64_t>((radsToDegs(g[LAT_INDEX]) + 90.f) * 1000000.0 + 0.5);
866  return (decimal_lon & 0xFFFFFFFF) | ((decimal_lat & 0XFFFFFFFF) << 32);
867 }
868 
876  GeoCoord(g);
877  _h3ToGeo(h3, g);
878  return radsToDegs(g[LON_INDEX]);
879 }
880 
888  GeoCoord(g);
889  _h3ToGeo(h3, g);
890  return radsToDegs(g[LAT_INDEX]);
891 }
892 
893 // /**
894 // * Determines the cell boundary in spherical coordinates for an H3 index.
895 // *
896 // * @param h3 The H3 index.
897 // * @param gb The boundary of the H3 cell in spherical coordinates.
898 // */
899 // void H3_EXPORT(h3ToGeoBoundary)(H3Index h3, GeoBoundary* gb) {
900 // FaceIJK fijk;
901 // _h3ToFaceIjk(h3, &fijk);
902 // if (H3_EXPORT(h3IsPentagon)(h3)) {
903 // _faceIjkPentToGeoBoundary(&fijk, H3_GET_RESOLUTION(h3), 0,
904 // NUM_PENT_VERTS, gb);
905 // } else {
906 // _faceIjkToGeoBoundary(&fijk, H3_GET_RESOLUTION(h3), 0, NUM_HEX_VERTS,
907 // gb);
908 // }
909 // }
910 
911 // /**
912 // * Returns the max number of possible icosahedron faces an H3 index
913 // * may intersect.
914 // *
915 // * @return int count of faces
916 // */
917 // int H3_EXPORT(maxFaceCount)(H3Index h3) {
918 // // a pentagon always intersects 5 faces, a hexagon never intersects more
919 // // than 2 (but may only intersect 1)
920 // return H3_EXPORT(h3IsPentagon)(h3) ? 5 : 2;
921 // }
922 
923 // /**
924 // * Find all icosahedron faces intersected by a given H3 index, represented
925 // * as integers from 0-19. The array is sparse; since 0 is a valid value,
926 // * invalid array values are represented as -1. It is the responsibility of
927 // * the caller to filter out invalid values.
928 // *
929 // * @param h3 The H3 index
930 // * @param out Output array. Must be of size maxFaceCount(h3).
931 // */
932 // void H3_EXPORT(h3GetFaces)(H3Index h3, int* out) {
933 // int res = H3_GET_RESOLUTION(h3);
934 // int isPentagon = H3_EXPORT(h3IsPentagon)(h3);
935 
936 // // We can't use the vertex-based approach here for class II pentagons,
937 // // because all their vertices are on the icosahedron edges. Their
938 // // direct child pentagons cross the same faces, so use those instead.
939 // if (isPentagon && !isResClassIII(res)) {
940 // // Note that this would not work for res 15, but this is only run on
941 // // Class II pentagons, it should never be invoked for a res 15 index.
942 // H3Index childPentagon = makeDirectChild(h3, 0);
943 // H3_EXPORT(h3GetFaces)(childPentagon, out);
944 // return;
945 // }
946 
947 // // convert to FaceIJK
948 // FaceIJK fijk;
949 // _h3ToFaceIjk(h3, &fijk);
950 
951 // // Get all vertices as FaceIJK addresses. For simplicity, always
952 // // initialize the array with 6 verts, ignoring the last one for pentagons
953 // FaceIJK fijkVerts[NUM_HEX_VERTS];
954 // int vertexCount;
955 
956 // if (isPentagon) {
957 // vertexCount = NUM_PENT_VERTS;
958 // _faceIjkPentToVerts(&fijk, &res, fijkVerts);
959 // } else {
960 // vertexCount = NUM_HEX_VERTS;
961 // _faceIjkToVerts(&fijk, &res, fijkVerts);
962 // }
963 
964 // // We may not use all of the slots in the output array,
965 // // so fill with invalid values to indicate unused slots
966 // int faceCount = H3_EXPORT(maxFaceCount)(h3);
967 // for (int i = 0; i < faceCount; i++) {
968 // out[i] = INVALID_FACE;
969 // }
970 
971 // // add each vertex face, using the output array as a hash set
972 // for (int i = 0; i < vertexCount; i++) {
973 // FaceIJK* vert = &fijkVerts[i];
974 
975 // // Adjust overage, determining whether this vertex is
976 // // on another face
977 // if (isPentagon) {
978 // _adjustPentVertOverage(vert, res);
979 // } else {
980 // _adjustOverageClassII(vert, res, 0, 1);
981 // }
982 
983 // // Save the face to the output array
984 // int face = vert->face;
985 // int pos = 0;
986 // // Find the first empty output position, or the first position
987 // // matching the current face
988 // while (out[pos] != INVALID_FACE && out[pos] != face) pos++;
989 // out[pos] = face;
990 // }
991 // }
992 
993 // /**
994 // * pentagonIndexCount returns the number of pentagons (same at any resolution)
995 // *
996 // * @return int count of pentagon indexes
997 // */
998 // int H3_EXPORT(pentagonIndexCount)() { return NUM_PENTAGONS; }
999 
1000 // /**
1001 // * Generates all pentagons at the specified resolution
1002 // *
1003 // * @param res The resolution to produce pentagons at.
1004 // * @param out Output array. Must be of size pentagonIndexCount().
1005 // */
1006 // void H3_EXPORT(getPentagonIndexes)(int res, H3Index* out) {
1007 // int i = 0;
1008 // for (int bc = 0; bc < NUM_BASE_CELLS; bc++) {
1009 // if (_isBaseCellPentagon(bc)) {
1010 // H3Index pentagon;
1011 // setH3Index(&pentagon, res, bc, 0);
1012 // out[i++] = pentagon;
1013 // }
1014 // }
1015 // }
#define H3_SET_INDEX_DIGIT(h3, res, digit)
Definition: h3Index.h:157
#define H3_HEXAGON_MODE
Definition: constants.h:82
EXTENSION_NOINLINE bool _h3ToGeo(H3Index h3, GeoCoord(g))
Definition: h3Index.hpp:834
EXTENSION_INLINE int _h3LeadingNonZeroDigit(H3Index h)
Definition: h3Index.hpp:551
EXTENSION_NOINLINE int _h3ToFaceIjkWithInitializedFijk(H3Index h, FaceIJK(fijk))
Definition: h3Index.hpp:753
#define GeoCoord(variable_name)
Definition: h3api.h:94
EXTENSION_NOINLINE H3Index _h3RotatePent60cw(H3Index h)
Definition: h3Index.hpp:590
EXTENSION_NOINLINE int _unitIjkToDigit(const CoordIJK(ijk))
Definition: coordijk.hpp:266
EXTENSION_INLINE int isResClassIII(int res)
Definition: faceijk.hpp:350
EXTENSION_NOINLINE double H3_EXPORT() h3ToLat(H3Index h3)
Definition: h3Index.hpp:887
#define EXTENSION_NOINLINE
Definition: heavydbTypes.h:58
#define FaceIJK(variable_name)
Definition: faceijk.h:36
H3Index functions.
EXTENSION_INLINE bool _ijkSub(const CoordIJK(h1), const CoordIJK(h2), CoordIJK(diff))
Definition: coordijk.hpp:198
#define H3_EXPORT(name)
Definition: h3api.h:43
EXTENSION_NOINLINE bool _neighbor(CoordIJK(ijk), int digit)
Definition: coordijk.hpp:372
EXTENSION_NOINLINE double H3_EXPORT() h3ToLon(H3Index h3)
Definition: h3Index.hpp:875
#define J_INDEX
Definition: coordijk.h:43
EXTENSION_NOINLINE H3Index H3_EXPORT() geoToH3(const double lon, const double lat, int res)
find the H3 index of the resolution res cell containing the lat/lng
Definition: h3Index.hpp:730
EXTENSION_INLINE double H3_EXPORT() radsToDegs(double radians)
converts radians to degrees
Definition: geoCoord.hpp:111
#define H3_SET_RESOLUTION(h3, res)
Definition: h3Index.h:133
EXTENSION_NOINLINE bool _downAp7r(CoordIJK(ijk))
Definition: coordijk.hpp:348
#define H3_SET_BASE_CELL(h3, bc)
Definition: h3Index.h:122
EXTENSION_NOINLINE H3Index _faceIjkToH3(const FaceIJK(fijk), int res)
Definition: h3Index.hpp:643
#define H3Index
the H3Index fits within a 64-bit unsigned integer
Definition: h3api.h:75
EXTENSION_NOINLINE H3Index H3_EXPORT() h3ToParent(H3Index h, int parentRes)
returns the parent (or grandparent, etc) hexagon of the given hexagon
Definition: h3Index.hpp:144
EXTENSION_NOINLINE int64_t H3_EXPORT() h3ToGeoPacked(H3Index h3)
find the lat/lon center point g of the cell h3
Definition: h3Index.hpp:853
EXTENSION_NOINLINE int _rotate60ccw(int digit)
Definition: coordijk.hpp:429
#define LAT_INDEX
Definition: h3api.h:92
DEVICE const BaseCellData baseCellData[NUM_BASE_CELLS]
Resolution 0 base cell data table.
Definition: baseCells.hpp:697
#define H3_GET_BASE_CELL(h3)
Definition: h3Index.h:117
#define CoordIJK_clone(ijk)
Definition: coordijk.h:47
#define MAX_FACE_COORD
Definition: baseCells.h:45
#define EXTENSION_INLINE
Definition: heavydbTypes.h:57
#define FaceIJK_copy(dest_ijk, src_ijk)
Definition: faceijk.h:39
EXTENSION_NOINLINE H3Index _h3RotatePent60ccw(H3Index h)
Definition: h3Index.hpp:564
#define I_INDEX
Definition: coordijk.h:42
#define CoordIJK_ptr(variable_name)
Definition: coordijk.h:46
EXTENSION_NOINLINE bool _h3ToFaceIjk(H3Index h, FaceIJK(fijk))
Definition: h3Index.hpp:783
Direction
H3 digit representing ijk+ axes direction. Values will be within the lowest 3 bits of an integer...
Definition: coordijk.h:75
EXTENSION_INLINE int _isBaseCellPentagon(int baseCell)
Return whether or not the indicated base cell is a pentagon.
Definition: baseCells.hpp:824
EXTENSION_NOINLINE int _rotate60cw(int digit)
Definition: coordijk.hpp:453
Base cell related lookup tables and access functions.
#define CoordIJK(variable_name)
Definition: coordijk.h:45
#define CoordIJK_copy(dest_ijk, src_ijk)
Definition: coordijk.h:49
EXTENSION_INLINE bool _baseCellIsCwOffset(int baseCell, int testFace)
Find the FaceIJK given a base cell.
Definition: baseCells.hpp:887
EXTENSION_INLINE int _faceIjkToBaseCellCCWrot60(const FaceIJK(h))
Find base cell given FaceIJK.
Definition: baseCells.hpp:854
#define H3_DIGIT_MASK
Definition: h3Index.h:80
#define H3_GET_INDEX_DIGIT(h3, res)
Definition: h3Index.h:139
#define FACE_INDEX
Definition: faceijk.h:35
EXTENSION_NOINLINE bool _faceIjkToGeo(const FaceIJK(h), int res, GeoCoord(g))
Definition: faceijk.hpp:495
EXTENSION_NOINLINE bool _downAp7(CoordIJK(ijk))
Definition: coordijk.hpp:325
#define MAX_H3_RES
Definition: constants.h:68
#define FaceIJK_clone(fijk)
Definition: faceijk.h:37
EXTENSION_NOINLINE bool _upAp7(CoordIJK(ijk))
Definition: coordijk.hpp:287
#define K_INDEX
Definition: coordijk.h:44
#define LON_INDEX
Definition: h3api.h:93
#define H3_INIT
Definition: h3Index.h:90
#define H3_NULL
Definition: h3Index.h:165
EXTENSION_INLINE double H3_EXPORT() degsToRads(double degrees)
converts degrees to radians
Definition: geoCoord.hpp:101
EXTENSION_NOINLINE bool _upAp7r(CoordIJK(ijk))
Definition: coordijk.hpp:306
EXTENSION_INLINE int _faceIjkToBaseCell(const FaceIJK(h))
Return whether the indicated base cell is a pentagon where all neighbors are oriented towards it...
Definition: baseCells.hpp:842
#define H3_SET_MODE(h3, v)
Definition: h3Index.h:111
EXTENSION_NOINLINE int _adjustOverageClassII(FaceIJK(fijk), int res, int pentLeading4, int substrate)
Definition: faceijk.hpp:864
EXTENSION_NOINLINE bool _geoToFaceIjk(const GeoCoord(g), int res, FaceIJK(h))
Definition: faceijk.hpp:362
EXTENSION_NOINLINE H3Index _h3Rotate60cw(H3Index h)
Definition: h3Index.hpp:629
EXTENSION_NOINLINE bool _ijkNormalize(CoordIJK(c))
Definition: coordijk.hpp:224
#define H3_GET_RESOLUTION(h3)
Definition: h3Index.h:128
EXTENSION_NOINLINE H3Index _h3Rotate60ccw(H3Index h)
Definition: h3Index.hpp:616