1/*
2 * Copyright 2016-2018 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#include <faceijk.h>
22#include <inttypes.h>
23#include <math.h>
24#include <stdlib.h>
25#include <string.h>
26#include "baseCells.h"
27#include "faceijk.h"
28#include "mathExtensions.h"
29#include "stackAlloc.h"
30
31/**
32 * Returns the H3 resolution of an H3 index.
33 * @param h The H3 index.
34 * @return The resolution of the H3 index argument.
35 */
36int H3_EXPORT(h3GetResolution)(H3Index h) { return H3_GET_RESOLUTION(h); }
37
38/**
39 * Returns the H3 base cell number of an H3 index.
40 * @param h The H3 index.
41 * @return The base cell of the H3 index argument.
42 */
43int H3_EXPORT(h3GetBaseCell)(H3Index h) { return H3_GET_BASE_CELL(h); }
44
45/**
46 * Converts a string representation of an H3 index into an H3 index.
47 * @param str The string representation of an H3 index.
48 * @return The H3 index corresponding to the string argument, or 0 if invalid.
49 */
50H3Index H3_EXPORT(stringToH3)(const char* str) {
51 H3Index h = H3_INVALID_INDEX;
52 // If failed, h will be unmodified and we should return 0 anyways.
53 sscanf(str, "%" PRIx64, &h);
54 return h;
55}
56
57/**
58 * Converts an H3 index into a string representation.
59 * @param h The H3 index to convert.
60 * @param str The string representation of the H3 index.
61 * @param sz Size of the buffer `str`
62 */
63void H3_EXPORT(h3ToString)(H3Index h, char* str, size_t sz) {
64 // An unsigned 64 bit integer will be expressed in at most
65 // 16 digits plus 1 for the null terminator.
66 if (sz < 17) {
67 // Buffer is potentially not large enough.
68 return;
69 }
70 sprintf(str, "%" PRIx64, h);
71}
72
73/**
74 * Returns whether or not an H3 index is valid.
75 * @param h The H3 index to validate.
76 * @return 1 if the H3 index if valid, and 0 if it is not.
77 */
78int H3_EXPORT(h3IsValid)(H3Index h) {
79 if (H3_GET_MODE(h) != H3_HEXAGON_MODE) return 0;
80
81 int baseCell = H3_GET_BASE_CELL(h);
82 if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) return 0;
83
84 int res = H3_GET_RESOLUTION(h);
85 if (res < 0 || res > MAX_H3_RES) return 0;
86
87 bool foundFirstNonZeroDigit = false;
88 for (int r = 1; r <= res; r++) {
89 Direction digit = H3_GET_INDEX_DIGIT(h, r);
90
91 if (!foundFirstNonZeroDigit && digit != CENTER_DIGIT) {
92 foundFirstNonZeroDigit = true;
93 if (_isBaseCellPentagon(baseCell) && digit == K_AXES_DIGIT) {
94 return 0;
95 }
96 }
97
98 if (digit < CENTER_DIGIT || digit >= NUM_DIGITS) return 0;
99 }
100
101 for (int r = res + 1; r <= MAX_H3_RES; r++) {
102 Direction digit = H3_GET_INDEX_DIGIT(h, r);
103 if (digit != INVALID_DIGIT) return 0;
104 }
105
106 return 1;
107}
108
109/**
110 * Initializes an H3 index.
111 * @param hp The H3 index to initialize.
112 * @param res The H3 resolution to initialize the index to.
113 * @param baseCell The H3 base cell to initialize the index to.
114 * @param initDigit The H3 digit (0-7) to initialize all of the index digits to.
115 */
116void setH3Index(H3Index* hp, int res, int baseCell, Direction initDigit) {
117 H3Index h = H3_INIT;
118 H3_SET_MODE(h, H3_HEXAGON_MODE);
119 H3_SET_RESOLUTION(h, res);
120 H3_SET_BASE_CELL(h, baseCell);
121 for (int r = 1; r <= res; r++) H3_SET_INDEX_DIGIT(h, r, initDigit);
122 *hp = h;
123}
124
125/**
126 * h3ToParent produces the parent index for a given H3 index
127 *
128 * @param h H3Index to find parent of
129 * @param parentRes The resolution to switch to (parent, grandparent, etc)
130 *
131 * @return H3Index of the parent, or 0 if you actually asked for a child
132 */
133H3Index H3_EXPORT(h3ToParent)(H3Index h, int parentRes) {
134 int childRes = H3_GET_RESOLUTION(h);
135 if (parentRes > childRes) {
136 return H3_INVALID_INDEX;
137 } else if (parentRes == childRes) {
138 return h;
139 } else if (parentRes < 0 || parentRes > MAX_H3_RES) {
140 return H3_INVALID_INDEX;
141 }
142 H3Index parentH = H3_SET_RESOLUTION(h, parentRes);
143 for (int i = parentRes + 1; i <= childRes; i++) {
144 H3_SET_INDEX_DIGIT(parentH, i, H3_DIGIT_MASK);
145 }
146 return parentH;
147}
148
149/**
150 * maxH3ToChildrenSize returns the maximum number of children possible for a
151 * given child level.
152 *
153 * @param h H3Index to find the number of children of
154 * @param childRes The resolution of the child level you're interested in
155 *
156 * @return int count of maximum number of children (equal for hexagons, less for
157 * pentagons
158 */
159int H3_EXPORT(maxH3ToChildrenSize)(H3Index h, int childRes) {
160 int parentRes = H3_GET_RESOLUTION(h);
161 if (parentRes > childRes) {
162 return 0;
163 }
164 return _ipow(7, (childRes - parentRes));
165}
166
167/**
168 * makeDirectChild takes an index and immediately returns the immediate child
169 * index based on the specified cell number. Bit operations only, could generate
170 * invalid indexes if not careful (deleted cell under a pentagon).
171 *
172 * @param h H3Index to find the direct child of
173 * @param cellNumber int id of the direct child (0-6)
174 *
175 * @return The new H3Index for the child
176 */
177H3Index makeDirectChild(H3Index h, int cellNumber) {
178 int childRes = H3_GET_RESOLUTION(h) + 1;
179 H3Index childH = H3_SET_RESOLUTION(h, childRes);
180 H3_SET_INDEX_DIGIT(childH, childRes, cellNumber);
181 return childH;
182}
183
184/**
185 * h3ToChildren takes the given hexagon id and generates all of the children
186 * at the specified resolution storing them into the provided memory pointer.
187 * It's assumed that maxH3ToChildrenSize was used to determine the allocation.
188 *
189 * @param h H3Index to find the children of
190 * @param childRes int the child level to produce
191 * @param children H3Index* the memory to store the resulting addresses in
192 */
193void H3_EXPORT(h3ToChildren)(H3Index h, int childRes, H3Index* children) {
194 int parentRes = H3_GET_RESOLUTION(h);
195 if (parentRes > childRes) {
196 return;
197 } else if (parentRes == childRes) {
198 *children = h;
199 return;
200 }
201 int bufferSize = H3_EXPORT(maxH3ToChildrenSize)(h, childRes);
202 int bufferChildStep = (bufferSize / 7);
203 int isAPentagon = H3_EXPORT(h3IsPentagon)(h);
204 for (int i = 0; i < 7; i++) {
205 if (isAPentagon && i == K_AXES_DIGIT) {
206 H3Index* nextChild = children + bufferChildStep;
207 while (children < nextChild) {
208 *children = H3_INVALID_INDEX;
209 children++;
210 }
211 } else {
212 H3_EXPORT(h3ToChildren)(makeDirectChild(h, i), childRes, children);
213 children += bufferChildStep;
214 }
215 }
216}
217
218/**
219 * compact takes a set of hexagons all at the same resolution and compresses
220 * them by pruning full child branches to the parent level. This is also done
221 * for all parents recursively to get the minimum number of hex addresses that
222 * perfectly cover the defined space.
223 * @param h3Set Set of hexagons
224 * @param compactedSet The output array of compressed hexagons (preallocated)
225 * @param numHexes The size of the input and output arrays (possible that no
226 * contiguous regions exist in the set at all and no compression possible)
227 * @return an error code on bad input data
228 */
229int H3_EXPORT(compact)(const H3Index* h3Set, H3Index* compactedSet,
230 const int numHexes) {
231 int res = H3_GET_RESOLUTION(h3Set[0]);
232 if (res == 0) {
233 // No compaction possible, just copy the set to output
234 for (int i = 0; i < numHexes; i++) {
235 compactedSet[i] = h3Set[i];
236 }
237 return 0;
238 }
239 H3Index* remainingHexes = malloc(numHexes * sizeof(H3Index));
240 memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
241 H3Index* hashSetArray = calloc(numHexes, sizeof(H3Index));
242 H3Index* compactedSetOffset = compactedSet;
243 int numRemainingHexes = numHexes;
244 while (numRemainingHexes) {
245 res = H3_GET_RESOLUTION(remainingHexes[0]);
246 int parentRes = res - 1;
247 // Put the parents of the hexagons into the temp array
248 // via a hashing mechanism, and use the reserved bits
249 // to track how many times a parent is duplicated
250 for (int i = 0; i < numRemainingHexes; i++) {
251 H3Index currIndex = remainingHexes[i];
252 if (currIndex != 0) {
253 H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
254 // Modulus hash the parent into the temp array
255 int loc = (int)(parent % numRemainingHexes);
256 int loopCount = 0;
257 while (hashSetArray[loc] != 0) {
258 if (loopCount > numRemainingHexes) {
259 // LCOV_EXCL_START
260 // This case should not be possible because at most one
261 // index is placed into hashSetArray per
262 // numRemainingHexes.
263 free(remainingHexes);
264 free(hashSetArray);
265 return -1;
266 // LCOV_EXCL_STOP
267 }
268 H3Index tempIndex =
269 hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
270 if (tempIndex == parent) {
271 int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
272 if (count > 7) {
273 // Only possible on duplicate input
274 free(remainingHexes);
275 free(hashSetArray);
276 return -2;
277 }
278 H3_SET_RESERVED_BITS(parent, count);
279 hashSetArray[loc] = H3_INVALID_INDEX;
280 } else {
281 loc = (loc + 1) % numRemainingHexes;
282 }
283 loopCount++;
284 }
285 hashSetArray[loc] = parent;
286 }
287 }
288 // Determine which parent hexagons have a complete set
289 // of children and put them in the compactableHexes array
290 int compactableCount = 0;
291 int maxCompactableCount =
292 numRemainingHexes / 6; // Somehow all pentagons; conservative
293 if (maxCompactableCount == 0) {
294 memcpy(compactedSetOffset, remainingHexes,
295 numRemainingHexes * sizeof(remainingHexes[0]));
296 break;
297 }
298 H3Index* compactableHexes =
299 malloc(maxCompactableCount * sizeof(H3Index));
300 for (int i = 0; i < numRemainingHexes; i++) {
301 if (hashSetArray[i] == 0) continue;
302 int count = H3_GET_RESERVED_BITS(hashSetArray[i]) + 1;
303 // Include the deleted direction for pentagons as implicitly "there"
304 if (H3_EXPORT(h3IsPentagon)(hashSetArray[i] &
305 H3_RESERVED_MASK_NEGATIVE)) {
306 // We need this later on, no need to recalculate
307 H3_SET_RESERVED_BITS(hashSetArray[i], count);
308 // Increment count after setting the reserved bits,
309 // since count is already incremented above, so it
310 // will be the expected value for a complete hexagon.
311 count++;
312 }
313 if (count == 7) {
314 // Bingo! Full set!
315 compactableHexes[compactableCount] =
316 hashSetArray[i] & H3_RESERVED_MASK_NEGATIVE;
317 compactableCount++;
318 }
319 }
320 // Uncompactable hexes are immediately copied into the
321 // output compactedSetOffset
322 int uncompactableCount = 0;
323 for (int i = 0; i < numRemainingHexes; i++) {
324 H3Index currIndex = remainingHexes[i];
325 if (currIndex != H3_INVALID_INDEX) {
326 H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
327 // Modulus hash the parent into the temp array
328 // to determine if this index was included in
329 // the compactableHexes array
330 int loc = (int)(parent % numRemainingHexes);
331 int loopCount = 0;
332 bool isUncompactable = true;
333 do {
334 if (loopCount > numRemainingHexes) {
335 // LCOV_EXCL_START
336 // This case should not be possible because at most one
337 // index is placed into hashSetArray per input hexagon.
338 free(compactableHexes);
339 free(remainingHexes);
340 free(hashSetArray);
341 return -1; // Only possible on duplicate input
342 // LCOV_EXCL_STOP
343 }
344 H3Index tempIndex =
345 hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
346 if (tempIndex == parent) {
347 int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
348 if (count == 7) {
349 isUncompactable = false;
350 }
351 break;
352 } else {
353 loc = (loc + 1) % numRemainingHexes;
354 }
355 loopCount++;
356 } while (hashSetArray[loc] != parent);
357 if (isUncompactable) {
358 compactedSetOffset[uncompactableCount] = remainingHexes[i];
359 uncompactableCount++;
360 }
361 }
362 }
363 // Set up for the next loop
364 memset(hashSetArray, 0, numHexes * sizeof(H3Index));
365 compactedSetOffset += uncompactableCount;
366 memcpy(remainingHexes, compactableHexes,
367 compactableCount * sizeof(H3Index));
368 numRemainingHexes = compactableCount;
369 free(compactableHexes);
370 }
371 free(remainingHexes);
372 free(hashSetArray);
373 return 0;
374}
375
376/**
377 * uncompact takes a compressed set of hexagons and expands back to the
378 * original set of hexagons.
379 * @param compactedSet Set of hexagons
380 * @param numHexes The number of hexes in the input set
381 * @param h3Set Output array of decompressed hexagons (preallocated)
382 * @param maxHexes The size of the output array to bound check against
383 * @param res The hexagon resolution to decompress to
384 * @return An error code if output array is too small or any hexagon is
385 * smaller than the output resolution.
386 */
387int H3_EXPORT(uncompact)(const H3Index* compactedSet, const int numHexes,
388 H3Index* h3Set, const int maxHexes, const int res) {
389 int outOffset = 0;
390 for (int i = 0; i < numHexes; i++) {
391 if (outOffset >= maxHexes) {
392 // We went too far, abort!
393 return -1;
394 }
395 if (compactedSet[i] == 0) continue;
396 int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
397 if (currentRes > res) {
398 // Nonsensical. Abort.
399 return -2;
400 }
401 if (currentRes == res) {
402 // Just copy and move along
403 h3Set[outOffset] = compactedSet[i];
404 outOffset++;
405 } else {
406 // Bigger hexagon to reduce in size
407 int numHexesToGen =
408 H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
409 if (outOffset + numHexesToGen > maxHexes) {
410 // We're about to go too far, abort!
411 return -1;
412 }
413 H3_EXPORT(h3ToChildren)(compactedSet[i], res, h3Set + outOffset);
414 outOffset += numHexesToGen;
415 }
416 }
417 return 0;
418}
419
420/**
421 * maxUncompactSize takes a compacted set of hexagons are provides an
422 * upper-bound estimate of the size of the uncompacted set of hexagons.
423 * @param compactedSet Set of hexagons
424 * @param numHexes The number of hexes in the input set
425 * @param res The hexagon resolution to decompress to
426 * @return The number of hexagons to allocate memory for, or a negative
427 * number if an error occurs.
428 */
429int H3_EXPORT(maxUncompactSize)(const H3Index* compactedSet, const int numHexes,
430 const int res) {
431 int maxNumHexagons = 0;
432 for (int i = 0; i < numHexes; i++) {
433 if (compactedSet[i] == 0) continue;
434 int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
435 if (currentRes > res) {
436 // Nonsensical. Abort.
437 return -1;
438 }
439 if (currentRes == res) {
440 maxNumHexagons++;
441 } else {
442 // Bigger hexagon to reduce in size
443 int numHexesToGen =
444 H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
445 maxNumHexagons += numHexesToGen;
446 }
447 }
448 return maxNumHexagons;
449}
450
451/**
452 * h3IsResClassIII takes a hexagon ID and determines if it is in a
453 * Class III resolution (rotated versus the icosahedron and subject
454 * to shape distortion adding extra points on icosahedron edges, making
455 * them not true hexagons).
456 * @param h The H3Index to check.
457 * @return Returns 1 if the hexagon is class III, otherwise 0.
458 */
459int H3_EXPORT(h3IsResClassIII)(H3Index h) { return H3_GET_RESOLUTION(h) % 2; }
460
461/**
462 * h3IsPentagon takes an H3Index and determines if it is actually a
463 * pentagon.
464 * @param h The H3Index to check.
465 * @return Returns 1 if it is a pentagon, otherwise 0.
466 */
467int H3_EXPORT(h3IsPentagon)(H3Index h) {
468 return _isBaseCellPentagon(H3_GET_BASE_CELL(h)) &&
469 !_h3LeadingNonZeroDigit(h);
470}
471
472/**
473 * Returns the highest resolution non-zero digit in an H3Index.
474 * @param h The H3Index.
475 * @return The highest resolution non-zero digit in the H3Index.
476 */
477Direction _h3LeadingNonZeroDigit(H3Index h) {
478 for (int r = 1; r <= H3_GET_RESOLUTION(h); r++)
479 if (H3_GET_INDEX_DIGIT(h, r)) return H3_GET_INDEX_DIGIT(h, r);
480
481 // if we're here it's all 0's
482 return CENTER_DIGIT;
483}
484
485/**
486 * Rotate an H3Index 60 degrees counter-clockwise about a pentagonal center.
487 * @param h The H3Index.
488 */
489H3Index _h3RotatePent60ccw(H3Index h) {
490 // rotate in place; skips any leading 1 digits (k-axis)
491
492 int foundFirstNonZeroDigit = 0;
493 for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
494 // rotate this digit
495 H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(H3_GET_INDEX_DIGIT(h, r)));
496
497 // look for the first non-zero digit so we
498 // can adjust for deleted k-axes sequence
499 // if necessary
500 if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
501 foundFirstNonZeroDigit = 1;
502
503 // adjust for deleted k-axes sequence
504 if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT)
505 h = _h3Rotate60ccw(h);
506 }
507 }
508 return h;
509}
510
511/**
512 * Rotate an H3Index 60 degrees clockwise about a pentagonal center.
513 * @param h The H3Index.
514 */
515H3Index _h3RotatePent60cw(H3Index h) {
516 // rotate in place; skips any leading 1 digits (k-axis)
517
518 int foundFirstNonZeroDigit = 0;
519 for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
520 // rotate this digit
521 H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r)));
522
523 // look for the first non-zero digit so we
524 // can adjust for deleted k-axes sequence
525 // if necessary
526 if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
527 foundFirstNonZeroDigit = 1;
528
529 // adjust for deleted k-axes sequence
530 if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) h = _h3Rotate60cw(h);
531 }
532 }
533 return h;
534}
535
536/**
537 * Rotate an H3Index 60 degrees counter-clockwise.
538 * @param h The H3Index.
539 */
540H3Index _h3Rotate60ccw(H3Index h) {
541 for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
542 Direction oldDigit = H3_GET_INDEX_DIGIT(h, r);
543 H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(oldDigit));
544 }
545
546 return h;
547}
548
549/**
550 * Rotate an H3Index 60 degrees clockwise.
551 * @param h The H3Index.
552 */
553H3Index _h3Rotate60cw(H3Index h) {
554 for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
555 H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r)));
556 }
557
558 return h;
559}
560
561/**
562 * Convert an FaceIJK address to the corresponding H3Index.
563 * @param fijk The FaceIJK address.
564 * @param res The cell resolution.
565 * @return The encoded H3Index (or 0 on failure).
566 */
567H3Index _faceIjkToH3(const FaceIJK* fijk, int res) {
568 // initialize the index
569 H3Index h = H3_INIT;
570 H3_SET_MODE(h, H3_HEXAGON_MODE);
571 H3_SET_RESOLUTION(h, res);
572
573 // check for res 0/base cell
574 if (res == 0) {
575 if (fijk->coord.i > MAX_FACE_COORD || fijk->coord.j > MAX_FACE_COORD ||
576 fijk->coord.k > MAX_FACE_COORD) {
577 // out of range input
578 return H3_INVALID_INDEX;
579 }
580
581 H3_SET_BASE_CELL(h, _faceIjkToBaseCell(fijk));
582 return h;
583 }
584
585 // we need to find the correct base cell FaceIJK for this H3 index;
586 // start with the passed in face and resolution res ijk coordinates
587 // in that face's coordinate system
588 FaceIJK fijkBC = *fijk;
589
590 // build the H3Index from finest res up
591 // adjust r for the fact that the res 0 base cell offsets the indexing
592 // digits
593 CoordIJK* ijk = &fijkBC.coord;
594 for (int r = res - 1; r >= 0; r--) {
595 CoordIJK lastIJK = *ijk;
596 CoordIJK lastCenter;
597 if (isResClassIII(r + 1)) {
598 // rotate ccw
599 _upAp7(ijk);
600 lastCenter = *ijk;
601 _downAp7(&lastCenter);
602 } else {
603 // rotate cw
604 _upAp7r(ijk);
605 lastCenter = *ijk;
606 _downAp7r(&lastCenter);
607 }
608
609 CoordIJK diff;
610 _ijkSub(&lastIJK, &lastCenter, &diff);
611 _ijkNormalize(&diff);
612
613 H3_SET_INDEX_DIGIT(h, r + 1, _unitIjkToDigit(&diff));
614 }
615
616 // fijkBC should now hold the IJK of the base cell in the
617 // coordinate system of the current face
618
619 if (fijkBC.coord.i > MAX_FACE_COORD || fijkBC.coord.j > MAX_FACE_COORD ||
620 fijkBC.coord.k > MAX_FACE_COORD) {
621 // out of range input
622 return H3_INVALID_INDEX;
623 }
624
625 // lookup the correct base cell
626 int baseCell = _faceIjkToBaseCell(&fijkBC);
627 H3_SET_BASE_CELL(h, baseCell);
628
629 // rotate if necessary to get canonical base cell orientation
630 // for this base cell
631 int numRots = _faceIjkToBaseCellCCWrot60(&fijkBC);
632 if (_isBaseCellPentagon(baseCell)) {
633 // force rotation out of missing k-axes sub-sequence
634 if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) {
635 // check for a cw/ccw offset face; default is ccw
636 if (_baseCellIsCwOffset(baseCell, fijkBC.face)) {
637 h = _h3Rotate60cw(h);
638 } else {
639 h = _h3Rotate60ccw(h);
640 }
641 }
642
643 for (int i = 0; i < numRots; i++) h = _h3RotatePent60ccw(h);
644 } else {
645 for (int i = 0; i < numRots; i++) {
646 h = _h3Rotate60ccw(h);
647 }
648 }
649
650 return h;
651}
652
653/**
654 * Encodes a coordinate on the sphere to the H3 index of the containing cell at
655 * the specified resolution.
656 *
657 * Returns 0 on invalid input.
658 *
659 * @param g The spherical coordinates to encode.
660 * @param res The desired H3 resolution for the encoding.
661 * @return The encoded H3Index (or 0 on failure).
662 */
663H3Index H3_EXPORT(geoToH3)(const GeoCoord* g, int res) {
664 if (res < 0 || res > MAX_H3_RES) {
665 return H3_INVALID_INDEX;
666 }
667 if (!isfinite(g->lat) || !isfinite(g->lon)) {
668 return H3_INVALID_INDEX;
669 }
670
671 FaceIJK fijk;
672 _geoToFaceIjk(g, res, &fijk);
673 return _faceIjkToH3(&fijk, res);
674}
675
676/**
677 * Convert an H3Index to the FaceIJK address on a specified icosahedral face.
678 * @param h The H3Index.
679 * @param fijk The FaceIJK address, initialized with the desired face
680 * and normalized base cell coordinates.
681 * @return Returns 1 if the possibility of overage exists, otherwise 0.
682 */
683int _h3ToFaceIjkWithInitializedFijk(H3Index h, FaceIJK* fijk) {
684 CoordIJK* ijk = &fijk->coord;
685 int res = H3_GET_RESOLUTION(h);
686
687 // center base cell hierarchy is entirely on this face
688 int possibleOverage = 1;
689 if (!_isBaseCellPentagon(H3_GET_BASE_CELL(h)) &&
690 (res == 0 ||
691 (fijk->coord.i == 0 && fijk->coord.j == 0 && fijk->coord.k == 0)))
692 possibleOverage = 0;
693
694 for (int r = 1; r <= res; r++) {
695 if (isResClassIII(r)) {
696 // Class III == rotate ccw
697 _downAp7(ijk);
698 } else {
699 // Class II == rotate cw
700 _downAp7r(ijk);
701 }
702
703 _neighbor(ijk, H3_GET_INDEX_DIGIT(h, r));
704 }
705
706 return possibleOverage;
707}
708
709/**
710 * Convert an H3Index to a FaceIJK address.
711 * @param h The H3Index.
712 * @param fijk The corresponding FaceIJK address.
713 */
714void _h3ToFaceIjk(H3Index h, FaceIJK* fijk) {
715 int baseCell = H3_GET_BASE_CELL(h);
716 // adjust for the pentagonal missing sequence; all of sub-sequence 5 needs
717 // to be adjusted (and some of sub-sequence 4 below)
718 if (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 5)
719 h = _h3Rotate60cw(h);
720
721 // start with the "home" face and ijk+ coordinates for the base cell of c
722 *fijk = baseCellData[baseCell].homeFijk;
723 if (!_h3ToFaceIjkWithInitializedFijk(h, fijk))
724 return; // no overage is possible; h lies on this face
725
726 // if we're here we have the potential for an "overage"; i.e., it is
727 // possible that c lies on an adjacent face
728
729 CoordIJK origIJK = fijk->coord;
730
731 // if we're in Class III, drop into the next finer Class II grid
732 int res = H3_GET_RESOLUTION(h);
733 if (isResClassIII(res)) {
734 // Class III
735 _downAp7r(&fijk->coord);
736 res++;
737 }
738
739 // adjust for overage if needed
740 // a pentagon base cell with a leading 4 digit requires special handling
741 int pentLeading4 =
742 (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 4);
743 if (_adjustOverageClassII(fijk, res, pentLeading4, 0)) {
744 // if the base cell is a pentagon we have the potential for secondary
745 // overages
746 if (_isBaseCellPentagon(baseCell)) {
747 while (1) {
748 if (!_adjustOverageClassII(fijk, res, 0, 0)) break;
749 }
750 }
751
752 if (res != H3_GET_RESOLUTION(h)) _upAp7r(&fijk->coord);
753 } else if (res != H3_GET_RESOLUTION(h)) {
754 fijk->coord = origIJK;
755 }
756}
757
758/**
759 * Determines the spherical coordinates of the center point of an H3 index.
760 *
761 * @param h3 The H3 index.
762 * @param g The spherical coordinates of the H3 cell center.
763 */
764void H3_EXPORT(h3ToGeo)(H3Index h3, GeoCoord* g) {
765 FaceIJK fijk;
766 _h3ToFaceIjk(h3, &fijk);
767 _faceIjkToGeo(&fijk, H3_GET_RESOLUTION(h3), g);
768}
769
770/**
771 * Determines the cell boundary in spherical coordinates for an H3 index.
772 *
773 * @param h3 The H3 index.
774 * @param gb The boundary of the H3 cell in spherical coordinates.
775 */
776void H3_EXPORT(h3ToGeoBoundary)(H3Index h3, GeoBoundary* gb) {
777 FaceIJK fijk;
778 _h3ToFaceIjk(h3, &fijk);
779 _faceIjkToGeoBoundary(&fijk, H3_GET_RESOLUTION(h3),
780 H3_EXPORT(h3IsPentagon)(h3), gb);
781}
782
783/**
784 * Returns whether or not a resolution is a Class III grid. Note that odd
785 * resolutions are Class III and even resolutions are Class II.
786 * @param res The H3 resolution.
787 * @return 1 if the resolution is a Class III grid, and 0 if the resolution is
788 * a Class II grid.
789 */
790int isResClassIII(int res) { return res % 2; }
791