Coverage Report

Created: 2026-11-20 06:52

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/h3/src/h3lib/lib/vertex.c
Line
Count
Source
1
/*
2
 * Copyright 2020-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  vertex.h
17
 *  @brief Functions for working with cell vertexes.
18
 */
19
20
#include "vertex.h"
21
22
#include <assert.h>
23
#include <stdbool.h>
24
25
#include "algos.h"
26
#include "baseCells.h"
27
#include "faceijk.h"
28
#include "h3Assert.h"
29
#include "h3Index.h"
30
#include "latLng.h"
31
32
0
#define DIRECTION_INDEX_OFFSET 2
33
34
/** @brief Table of direction-to-face mapping for each pentagon
35
 *
36
 * Note that faces are in directional order, starting at J_AXES_DIGIT.
37
 * This table is generated by the generatePentagonDirectionFaces script.
38
 */
39
static const PentagonDirectionFaces pentagonDirectionFaces[NUM_PENTAGONS] = {
40
    {4, {4, 0, 2, 1, 3}},       {14, {6, 11, 2, 7, 1}},
41
    {24, {5, 10, 1, 6, 0}},     {38, {7, 12, 3, 8, 2}},
42
    {49, {9, 14, 0, 5, 4}},     {58, {8, 13, 4, 9, 3}},
43
    {63, {11, 6, 15, 10, 16}},  {72, {12, 7, 16, 11, 17}},
44
    {83, {10, 5, 19, 14, 15}},  {97, {13, 8, 17, 12, 18}},
45
    {107, {14, 9, 18, 13, 19}}, {117, {15, 19, 17, 18, 16}},
46
};
47
48
/**
49
 * Get the number of CCW rotations of the cell's vertex numbers
50
 * compared to the directional layout of its neighbors.
51
 * @param out Number of CCW rotations for the cell
52
 */
53
0
static H3Error vertexRotations(H3Index cell, int *out) {
54
    // Get the face and other info for the origin
55
0
    FaceIJK fijk;
56
0
    H3Error err = _h3ToFaceIjk(cell, &fijk);
57
0
    if (err) {
58
0
        return err;
59
0
    }
60
0
    int baseCell = H3_EXPORT(getBaseCellNumber)(cell);
61
0
    int cellLeadingDigit = _h3LeadingNonZeroDigit(cell);
62
63
    // get the base cell face
64
0
    FaceIJK baseFijk;
65
0
    _baseCellToFaceIjk(baseCell, &baseFijk);
66
67
0
    int ccwRot60 = _baseCellToCCWrot60(baseCell, fijk.face);
68
69
0
    if (_isBaseCellPentagon(baseCell)) {
70
        // Find the appropriate direction-to-face mapping
71
        // Zero-initialized to silence a spurious maybe-uninitialized warning.
72
0
        PentagonDirectionFaces dirFaces = {0, {0}};
73
        // We never hit the end condition
74
0
        int p = 0;
75
        // Don't use a for loop here, for coverage reasons.
76
0
        while (ALWAYS(p < NUM_PENTAGONS)) {
77
0
            if (pentagonDirectionFaces[p].baseCell == baseCell) {
78
0
                dirFaces = pentagonDirectionFaces[p];
79
0
                break;
80
0
            }
81
0
            p++;
82
0
        }
83
0
        if (NEVER(p == NUM_PENTAGONS)) {
84
0
            return E_FAILED;
85
0
        }
86
87
        // additional CCW rotation for polar neighbors or IK neighbors
88
0
        if (fijk.face != baseFijk.face &&
89
0
            (_isBaseCellPolarPentagon(baseCell) ||
90
0
             fijk.face ==
91
0
                 dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET])) {
92
0
            ccwRot60 = (ccwRot60 + 1) % 6;
93
0
        }
94
95
        // Check whether the cell crosses a deleted pentagon subsequence
96
0
        if (cellLeadingDigit == JK_AXES_DIGIT &&
97
0
            fijk.face ==
98
0
                dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) {
99
            // Crosses from JK to IK: Rotate CW
100
0
            ccwRot60 = (ccwRot60 + 5) % 6;
101
0
        } else if (cellLeadingDigit == IK_AXES_DIGIT &&
102
0
                   fijk.face ==
103
0
                       dirFaces.faces[JK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) {
104
            // Crosses from IK to JK: Rotate CCW
105
0
            ccwRot60 = (ccwRot60 + 1) % 6;
106
0
        }
107
0
    }
108
0
    *out = ccwRot60;
109
0
    return E_SUCCESS;
110
0
}
111
112
/** @brief Hexagon direction to vertex number relationships (same face).
113
 *         Note that we don't use direction 0 (center).
114
 */
115
static const int directionToVertexNumHex[NUM_DIGITS] = {
116
    INVALID_DIGIT, 3, 1, 2, 5, 4, 0};
117
118
/** @brief Pentagon direction to vertex number relationships (same face).
119
 *         Note that we don't use directions 0 (center) or 1 (deleted K axis).
120
 */
121
static const int directionToVertexNumPent[NUM_DIGITS] = {
122
    INVALID_DIGIT, INVALID_DIGIT, 1, 2, 4, 3, 0};
123
124
/**
125
 * Get the first vertex number for a given direction. The neighbor in this
126
 * direction is located between this vertex number and the next number in
127
 * sequence.
128
 * @returns The number for the first topological vertex, or INVALID_VERTEX_NUM
129
 *          if the direction is not valid for this cell
130
 */
131
0
int vertexNumForDirection(const H3Index origin, const Direction direction) {
132
0
    int isPent = H3_EXPORT(isPentagon)(origin);
133
    // Check for invalid directions
134
0
    if (direction == CENTER_DIGIT || direction >= INVALID_DIGIT ||
135
0
        (isPent && direction == K_AXES_DIGIT))
136
0
        return INVALID_VERTEX_NUM;
137
138
    // Determine the vertex rotations for this cell
139
0
    int rotations;
140
0
    H3Error err = vertexRotations(origin, &rotations);
141
0
    if (err) {
142
0
        return INVALID_VERTEX_NUM;
143
0
    }
144
145
    // Find the appropriate vertex, rotating CCW if necessary
146
0
    if (isPent) {
147
0
        return (directionToVertexNumPent[direction] + NUM_PENT_VERTS -
148
0
                rotations) %
149
0
               NUM_PENT_VERTS;
150
0
    } else {
151
0
        return (directionToVertexNumHex[direction] + NUM_HEX_VERTS -
152
0
                rotations) %
153
0
               NUM_HEX_VERTS;
154
0
    }
155
0
}
156
157
/** @brief Vertex number to hexagon direction relationships (same face).
158
 */
159
static const Direction vertexNumToDirectionHex[NUM_HEX_VERTS] = {
160
    IJ_AXES_DIGIT, J_AXES_DIGIT,  JK_AXES_DIGIT,
161
    K_AXES_DIGIT,  IK_AXES_DIGIT, I_AXES_DIGIT};
162
163
/** @brief Vertex number to pentagon direction relationships (same face).
164
 */
165
static const Direction vertexNumToDirectionPent[NUM_PENT_VERTS] = {
166
    IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT};
167
168
/**
169
 * Get the direction for a given vertex number. This returns the direction for
170
 * the neighbor between the given vertex number and the next number in sequence.
171
 * @returns The direction for this vertex, or INVALID_DIGIT if the vertex
172
 * number is invalid.
173
 */
174
0
Direction directionForVertexNum(const H3Index origin, const int vertexNum) {
175
0
    int isPent = H3_EXPORT(isPentagon)(origin);
176
    // Check for invalid vertexes
177
0
    if (vertexNum < 0 ||
178
0
        vertexNum > (isPent ? NUM_PENT_VERTS : NUM_HEX_VERTS) - 1)
179
0
        return INVALID_DIGIT;
180
181
    // Determine the vertex rotations for this cell
182
0
    int rotations;
183
0
    H3Error err = vertexRotations(origin, &rotations);
184
0
    if (err) {
185
0
        return INVALID_DIGIT;
186
0
    }
187
188
    // Find the appropriate direction, rotating CW if necessary
189
0
    return isPent ? vertexNumToDirectionPent[(vertexNum + rotations) %
190
0
                                             NUM_PENT_VERTS]
191
0
                  : vertexNumToDirectionHex[(vertexNum + rotations) %
192
0
                                            NUM_HEX_VERTS];
193
0
}
194
195
/** @brief Directions in CCW order */
196
static const Direction DIRECTIONS[NUM_HEX_VERTS] = {
197
    J_AXES_DIGIT,  JK_AXES_DIGIT, K_AXES_DIGIT,
198
    IK_AXES_DIGIT, I_AXES_DIGIT,  IJ_AXES_DIGIT};
199
200
/** @brief Reverse direction from neighbor in each direction,
201
 *         given as an index into DIRECTIONS to facilitate rotation
202
 */
203
static const int revNeighborDirectionsHex[NUM_DIGITS] = {
204
    INVALID_DIGIT, 5, 3, 4, 1, 0, 2};
205
206
/**
207
 * Get a single vertex for a given cell, as an H3 index, or
208
 * H3_NULL if the vertex is invalid
209
 * @param cell    Cell to get the vertex for
210
 * @param vertexNum Number (index) of the vertex to calculate
211
 * @param out Output: The vertex index
212
 */
213
0
H3Error H3_EXPORT(cellToVertex)(H3Index cell, int vertexNum, H3Index *out) {
214
0
    int cellIsPentagon = H3_EXPORT(isPentagon)(cell);
215
0
    int cellNumVerts = cellIsPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS;
216
0
    int res = H3_GET_RESOLUTION(cell);
217
218
    // Check for invalid vertexes
219
0
    if (vertexNum < 0 || vertexNum > cellNumVerts - 1) return E_DOMAIN;
220
221
    // Default the owner and vertex number to the input cell
222
0
    H3Index owner = cell;
223
0
    int ownerVertexNum = vertexNum;
224
225
    // Determine the owner, looking at the three cells that share the vertex.
226
    // By convention, the owner is the cell with the lowest numerical index.
227
228
    // If the cell is the center child of its parent, it will always have
229
    // the lowest index of any neighbor, so we can skip determining the owner
230
0
    if (res == 0 || H3_GET_INDEX_DIGIT(cell, res) != CENTER_DIGIT) {
231
        // Get the left neighbor of the vertex, with its rotations
232
0
        Direction left = directionForVertexNum(cell, vertexNum);
233
0
        if (left == INVALID_DIGIT) return E_FAILED;
234
0
        int lRotations = 0;
235
0
        H3Index leftNeighbor;
236
0
        H3Error leftNeighborError =
237
0
            h3NeighborRotations(cell, left, &lRotations, &leftNeighbor);
238
0
        if (leftNeighborError) return leftNeighborError;
239
        // Set to owner if lowest index
240
0
        if (leftNeighbor < owner) owner = leftNeighbor;
241
242
        // As above, skip the right neighbor if the left is known lowest
243
0
        if (res == 0 || H3_GET_INDEX_DIGIT(leftNeighbor, res) != CENTER_DIGIT) {
244
            // Get the right neighbor of the vertex, with its rotations
245
            // Note that vertex - 1 is the right side, as vertex numbers are CCW
246
0
            Direction right = directionForVertexNum(
247
0
                cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts);
248
            // This case should be unreachable; invalid verts fail earlier
249
0
            if (NEVER(right == INVALID_DIGIT)) return E_FAILED;
250
0
            int rRotations = 0;
251
0
            H3Index rightNeighbor;
252
0
            H3Error rightNeighborError =
253
0
                h3NeighborRotations(cell, right, &rRotations, &rightNeighbor);
254
0
            if (rightNeighborError) return rightNeighborError;
255
            // Set to owner if lowest index
256
0
            if (rightNeighbor < owner) {
257
0
                owner = rightNeighbor;
258
0
                Direction dir =
259
0
                    H3_EXPORT(isPentagon)(owner)
260
0
                        ? directionForNeighbor(owner, cell)
261
0
                        : DIRECTIONS[(revNeighborDirectionsHex[right] +
262
0
                                      rRotations) %
263
0
                                     NUM_HEX_VERTS];
264
0
                ownerVertexNum = vertexNumForDirection(owner, dir);
265
0
            }
266
0
        }
267
268
        // Determine the vertex number for the left neighbor
269
0
        if (owner == leftNeighbor) {
270
0
            int ownerIsPentagon = H3_EXPORT(isPentagon)(owner);
271
0
            Direction dir =
272
0
                ownerIsPentagon
273
0
                    ? directionForNeighbor(owner, cell)
274
0
                    : DIRECTIONS[(revNeighborDirectionsHex[left] + lRotations) %
275
0
                                 NUM_HEX_VERTS];
276
277
            // For the left neighbor, we need the second vertex of the
278
            // edge, which may involve looping around the vertex nums
279
0
            ownerVertexNum = vertexNumForDirection(owner, dir) + 1;
280
0
            if (ownerVertexNum == NUM_HEX_VERTS ||
281
0
                (ownerIsPentagon && ownerVertexNum == NUM_PENT_VERTS)) {
282
0
                ownerVertexNum = 0;
283
0
            }
284
0
        }
285
0
    }
286
287
    // Create the vertex index
288
0
    H3Index vertex = owner;
289
0
    H3_SET_MODE(vertex, H3_VERTEX_MODE);
290
0
    H3_SET_RESERVED_BITS(vertex, ownerVertexNum);
291
0
    *out = vertex;
292
293
0
    return E_SUCCESS;
294
0
}
295
296
/**
297
 * Get all vertexes for the given cell
298
 * @param cell      Cell to get the vertexes for
299
 * @param vertexes  Array to hold vertex output. Must have length >= 6.
300
 */
301
0
H3Error H3_EXPORT(cellToVertexes)(H3Index cell, H3Index *vertexes) {
302
    // Get all vertexes. If the cell is a pentagon, will fill the final slot
303
    // with H3_NULL.
304
0
    bool isPent = H3_EXPORT(isPentagon)(cell);
305
0
    for (int i = 0; i < NUM_HEX_VERTS; i++) {
306
0
        if (i == 5 && isPent) {
307
0
            vertexes[i] = H3_NULL;
308
0
        } else {
309
0
            H3Error cellError = H3_EXPORT(cellToVertex)(cell, i, &vertexes[i]);
310
0
            if (cellError) {
311
0
                return cellError;
312
0
            }
313
0
        }
314
0
    }
315
0
    return E_SUCCESS;
316
0
}
317
318
/**
319
 * Get the start and end vertexes of a directed edge, as H3 indexes. The
320
 * vertexes are ordered according to the right-hand rule: the start vertex
321
 * is the first topological vertex of the edge's origin cell in the edge's
322
 * direction, and the end vertex is the next vertex in CCW order.
323
 * @param edge Directed edge to get the vertexes for
324
 * @param v1   Output: The start vertex index
325
 * @param v2   Output: The end vertex index
326
 */
327
0
H3Error H3_EXPORT(edgeToVertexes)(H3Index edge, H3Index *v1, H3Index *v2) {
328
    // Validate the edge and get its origin cell
329
0
    if (!H3_EXPORT(isValidDirectedEdge)(edge)) {
330
0
        return E_DIR_EDGE_INVALID;
331
0
    }
332
0
    H3Index origin;
333
0
    H3Error originError = H3_EXPORT(getDirectedEdgeOrigin)(edge, &origin);
334
0
    if (originError) {
335
0
        return originError;
336
0
    }
337
338
    // Get the first (start) vertex number for the edge's direction
339
0
    Direction direction = H3_GET_RESERVED_BITS(edge);
340
0
    int startVertexNum = vertexNumForDirection(origin, direction);
341
    // This is unreachable, since isValidDirectedEdge validates the direction
342
0
    if (NEVER(startVertexNum == INVALID_VERTEX_NUM)) {
343
0
        return E_DIR_EDGE_INVALID;
344
0
    }
345
346
    // The second (end) vertex is the next one in CCW order
347
0
    int cellNumVerts =
348
0
        H3_EXPORT(isPentagon)(origin) ? NUM_PENT_VERTS : NUM_HEX_VERTS;
349
0
    int endVertexNum = (startVertexNum + 1) % cellNumVerts;
350
351
    // Convert the vertex numbers to H3 vertex indexes
352
0
    H3Error v1Error = H3_EXPORT(cellToVertex)(origin, startVertexNum, v1);
353
0
    if (v1Error) {
354
0
        return v1Error;
355
0
    }
356
0
    return H3_EXPORT(cellToVertex)(origin, endVertexNum, v2);
357
0
}
358
359
/**
360
 * Get the geocoordinates of an H3 vertex
361
 * @param vertex H3 index describing a vertex
362
 * @param coord  Output geo coordinate
363
 */
364
0
H3Error H3_EXPORT(vertexToLatLng)(H3Index vertex, LatLng *coord) {
365
    // Get the vertex number and owner from the vertex
366
0
    int vertexNum = H3_GET_RESERVED_BITS(vertex);
367
0
    H3Index owner = vertex;
368
0
    H3_SET_MODE(owner, H3_CELL_MODE);
369
0
    H3_SET_RESERVED_BITS(owner, 0);
370
371
    // Get the single vertex from the boundary
372
0
    CellBoundary gb;
373
0
    FaceIJK fijk;
374
0
    H3Error fijkError = _h3ToFaceIjk(owner, &fijk);
375
0
    if (fijkError) {
376
0
        return fijkError;
377
0
    }
378
0
    int res = H3_GET_RESOLUTION(owner);
379
380
0
    if (H3_EXPORT(isPentagon)(owner)) {
381
0
        _faceIjkPentToCellBoundary(&fijk, res, vertexNum, 1, &gb);
382
0
    } else {
383
0
        _faceIjkToCellBoundary(&fijk, res, vertexNum, 1, &gb);
384
0
    }
385
386
    // Copy from boundary to output coord
387
0
    *coord = gb.verts[0];
388
0
    return E_SUCCESS;
389
0
}
390
391
/**
392
 * Whether the input is a valid H3 vertex
393
 * @param  vertex H3 index possibly describing a vertex
394
 * @return        Whether the input is valid
395
 */
396
0
int H3_EXPORT(isValidVertex)(H3Index vertex) {
397
0
    if (H3_GET_MODE(vertex) != H3_VERTEX_MODE) {
398
0
        return 0;
399
0
    }
400
401
0
    int vertexNum = H3_GET_RESERVED_BITS(vertex);
402
0
    H3Index owner = vertex;
403
0
    H3_SET_MODE(owner, H3_CELL_MODE);
404
0
    H3_SET_RESERVED_BITS(owner, 0);
405
406
0
    if (!H3_EXPORT(isValidCell)(owner)) {
407
0
        return 0;
408
0
    }
409
410
    // The easiest way to ensure that the owner + vertex number is valid,
411
    // and that the vertex is canonical, is to recreate and compare.
412
0
    H3Index canonical;
413
0
    if (H3_EXPORT(cellToVertex)(owner, vertexNum, &canonical)) {
414
0
        return 0;
415
0
    }
416
417
0
    return vertex == canonical ? 1 : 0;
418
0
}