/src/h3/src/h3lib/lib/vertex.c
Line | Count | Source (jump to first uncovered line) |
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 | 2.08k | #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 | 6.04k | static H3Error vertexRotations(H3Index cell, int *out) { |
54 | | // Get the face and other info for the origin |
55 | 6.04k | FaceIJK fijk; |
56 | 6.04k | H3Error err = _h3ToFaceIjk(cell, &fijk); |
57 | 6.04k | if (err) { |
58 | 9 | return err; |
59 | 9 | } |
60 | 6.03k | int baseCell = H3_EXPORT(getBaseCellNumber)(cell); |
61 | 6.03k | int cellLeadingDigit = _h3LeadingNonZeroDigit(cell); |
62 | | |
63 | | // get the base cell face |
64 | 6.03k | FaceIJK baseFijk; |
65 | 6.03k | _baseCellToFaceIjk(baseCell, &baseFijk); |
66 | | |
67 | 6.03k | int ccwRot60 = _baseCellToCCWrot60(baseCell, fijk.face); |
68 | | |
69 | 6.03k | if (_isBaseCellPentagon(baseCell)) { |
70 | | // Find the appropriate direction-to-face mapping |
71 | 2.23k | PentagonDirectionFaces dirFaces; |
72 | | // We never hit the end condition |
73 | 2.23k | int p = 0; |
74 | 14.3k | for (; p < NUM_PENTAGONS; p++) { |
75 | 14.3k | if (pentagonDirectionFaces[p].baseCell == baseCell) { |
76 | 2.23k | dirFaces = pentagonDirectionFaces[p]; |
77 | 2.23k | break; |
78 | 2.23k | } |
79 | 14.3k | } |
80 | 2.23k | if (p == NUM_PENTAGONS) { |
81 | 0 | return E_FAILED; |
82 | 0 | } |
83 | | |
84 | | // additional CCW rotation for polar neighbors or IK neighbors |
85 | 2.23k | if (fijk.face != baseFijk.face && |
86 | 2.23k | (_isBaseCellPolarPentagon(baseCell) || |
87 | 1.66k | fijk.face == |
88 | 1.21k | dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET])) { |
89 | 784 | ccwRot60 = (ccwRot60 + 1) % 6; |
90 | 784 | } |
91 | | |
92 | | // Check whether the cell crosses a deleted pentagon subsequence |
93 | 2.23k | if (cellLeadingDigit == JK_AXES_DIGIT && |
94 | 2.23k | fijk.face == |
95 | 468 | dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) { |
96 | | // Crosses from JK to IK: Rotate CW |
97 | 151 | ccwRot60 = (ccwRot60 + 5) % 6; |
98 | 2.08k | } else if (cellLeadingDigit == IK_AXES_DIGIT && |
99 | 2.08k | fijk.face == |
100 | 394 | dirFaces.faces[JK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) { |
101 | | // Crosses from IK to JK: Rotate CCW |
102 | 117 | ccwRot60 = (ccwRot60 + 1) % 6; |
103 | 117 | } |
104 | 2.23k | } |
105 | 6.03k | *out = ccwRot60; |
106 | 6.03k | return E_SUCCESS; |
107 | 6.03k | } |
108 | | |
109 | | /** @brief Hexagon direction to vertex number relationships (same face). |
110 | | * Note that we don't use direction 0 (center). |
111 | | */ |
112 | | static const int directionToVertexNumHex[NUM_DIGITS] = { |
113 | | INVALID_DIGIT, 3, 1, 2, 5, 4, 0}; |
114 | | |
115 | | /** @brief Pentagon direction to vertex number relationships (same face). |
116 | | * Note that we don't use directions 0 (center) or 1 (deleted K axis). |
117 | | */ |
118 | | static const int directionToVertexNumPent[NUM_DIGITS] = { |
119 | | INVALID_DIGIT, INVALID_DIGIT, 1, 2, 4, 3, 0}; |
120 | | |
121 | | /** |
122 | | * Get the first vertex number for a given direction. The neighbor in this |
123 | | * direction is located between this vertex number and the next number in |
124 | | * sequence. |
125 | | * @returns The number for the first topological vertex, or INVALID_VERTEX_NUM |
126 | | * if the direction is not valid for this cell |
127 | | */ |
128 | 1.77k | int vertexNumForDirection(const H3Index origin, const Direction direction) { |
129 | 1.77k | int isPent = H3_EXPORT(isPentagon)(origin); |
130 | | // Check for invalid directions |
131 | 1.77k | if (direction == CENTER_DIGIT || direction >= INVALID_DIGIT || |
132 | 1.77k | (isPent && direction == K_AXES_DIGIT)) |
133 | 14 | return INVALID_VERTEX_NUM; |
134 | | |
135 | | // Determine the vertex rotations for this cell |
136 | 1.75k | int rotations; |
137 | 1.75k | H3Error err = vertexRotations(origin, &rotations); |
138 | 1.75k | if (err) { |
139 | 0 | return INVALID_VERTEX_NUM; |
140 | 0 | } |
141 | | |
142 | | // Find the appropriate vertex, rotating CCW if necessary |
143 | 1.75k | if (isPent) { |
144 | 67 | return (directionToVertexNumPent[direction] + NUM_PENT_VERTS - |
145 | 67 | rotations) % |
146 | 67 | NUM_PENT_VERTS; |
147 | 1.69k | } else { |
148 | 1.69k | return (directionToVertexNumHex[direction] + NUM_HEX_VERTS - |
149 | 1.69k | rotations) % |
150 | 1.69k | NUM_HEX_VERTS; |
151 | 1.69k | } |
152 | 1.75k | } |
153 | | |
154 | | /** @brief Vertex number to hexagon direction relationships (same face). |
155 | | */ |
156 | | static const Direction vertexNumToDirectionHex[NUM_HEX_VERTS] = { |
157 | | IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, |
158 | | K_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT}; |
159 | | |
160 | | /** @brief Vertex number to pentagon direction relationships (same face). |
161 | | */ |
162 | | static const Direction vertexNumToDirectionPent[NUM_PENT_VERTS] = { |
163 | | IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT}; |
164 | | |
165 | | /** |
166 | | * Get the direction for a given vertex number. This returns the direction for |
167 | | * the neighbor between the given vertex number and the next number in sequence. |
168 | | * @returns The direction for this vertex, or INVALID_DIGIT if the vertex |
169 | | * number is invalid. |
170 | | */ |
171 | 4.28k | Direction directionForVertexNum(const H3Index origin, const int vertexNum) { |
172 | 4.28k | int isPent = H3_EXPORT(isPentagon)(origin); |
173 | | // Check for invalid vertexes |
174 | 4.28k | if (vertexNum < 0 || |
175 | 4.28k | vertexNum > (isPent ? NUM_PENT_VERTS : NUM_HEX_VERTS) - 1) |
176 | 0 | return INVALID_DIGIT; |
177 | | |
178 | | // Determine the vertex rotations for this cell |
179 | 4.28k | int rotations; |
180 | 4.28k | H3Error err = vertexRotations(origin, &rotations); |
181 | 4.28k | if (err) { |
182 | 9 | return INVALID_DIGIT; |
183 | 9 | } |
184 | | |
185 | | // Find the appropriate direction, rotating CW if necessary |
186 | 4.27k | return isPent ? vertexNumToDirectionPent[(vertexNum + rotations) % |
187 | 32 | NUM_PENT_VERTS] |
188 | 4.27k | : vertexNumToDirectionHex[(vertexNum + rotations) % |
189 | 4.24k | NUM_HEX_VERTS]; |
190 | 4.28k | } |
191 | | |
192 | | /** @brief Directions in CCW order */ |
193 | | static const Direction DIRECTIONS[NUM_HEX_VERTS] = { |
194 | | J_AXES_DIGIT, JK_AXES_DIGIT, K_AXES_DIGIT, |
195 | | IK_AXES_DIGIT, I_AXES_DIGIT, IJ_AXES_DIGIT}; |
196 | | |
197 | | /** @brief Reverse direction from neighbor in each direction, |
198 | | * given as an index into DIRECTIONS to facilitate rotation |
199 | | */ |
200 | | static const int revNeighborDirectionsHex[NUM_DIGITS] = { |
201 | | INVALID_DIGIT, 5, 3, 4, 1, 0, 2}; |
202 | | |
203 | | /** |
204 | | * Get a single vertex for a given cell, as an H3 index, or |
205 | | * H3_NULL if the vertex is invalid |
206 | | * @param cell Cell to get the vertex for |
207 | | * @param vertexNum Number (index) of the vertex to calculate |
208 | | */ |
209 | 2.97k | H3Error H3_EXPORT(cellToVertex)(H3Index cell, int vertexNum, H3Index *out) { |
210 | 2.97k | int cellIsPentagon = H3_EXPORT(isPentagon)(cell); |
211 | 2.97k | int cellNumVerts = cellIsPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS; |
212 | 2.97k | int res = H3_GET_RESOLUTION(cell); |
213 | | |
214 | | // Check for invalid vertexes |
215 | 2.97k | if (vertexNum < 0 || vertexNum > cellNumVerts - 1) return E_DOMAIN; |
216 | | |
217 | | // Default the owner and vertex number to the input cell |
218 | 2.59k | H3Index owner = cell; |
219 | 2.59k | int ownerVertexNum = vertexNum; |
220 | | |
221 | | // Determine the owner, looking at the three cells that share the vertex. |
222 | | // By convention, the owner is the cell with the lowest numerical index. |
223 | | |
224 | | // If the cell is the center child of its parent, it will always have |
225 | | // the lowest index of any neighbor, so we can skip determining the owner |
226 | 2.59k | if (res == 0 || H3_GET_INDEX_DIGIT(cell, res) != CENTER_DIGIT) { |
227 | | // Get the left neighbor of the vertex, with its rotations |
228 | 2.36k | Direction left = directionForVertexNum(cell, vertexNum); |
229 | 2.36k | if (left == INVALID_DIGIT) return E_FAILED; |
230 | 2.35k | int lRotations = 0; |
231 | 2.35k | H3Index leftNeighbor; |
232 | 2.35k | H3Error leftNeighborError = |
233 | 2.35k | h3NeighborRotations(cell, left, &lRotations, &leftNeighbor); |
234 | 2.35k | if (leftNeighborError) return leftNeighborError; |
235 | | // Set to owner if lowest index |
236 | 2.25k | if (leftNeighbor < owner) owner = leftNeighbor; |
237 | | |
238 | | // As above, skip the right neighbor if the left is known lowest |
239 | 2.25k | if (res == 0 || H3_GET_INDEX_DIGIT(leftNeighbor, res) != CENTER_DIGIT) { |
240 | | // Get the right neighbor of the vertex, with its rotations |
241 | | // Note that vertex - 1 is the right side, as vertex numbers are CCW |
242 | 1.92k | Direction right = directionForVertexNum( |
243 | 1.92k | cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts); |
244 | | // This case should be unreachable; invalid verts fail earlier |
245 | 1.92k | if (NEVER(right == INVALID_DIGIT)) return E_FAILED; |
246 | 1.92k | int rRotations = 0; |
247 | 1.92k | H3Index rightNeighbor; |
248 | 1.92k | H3Error rightNeighborError = |
249 | 1.92k | h3NeighborRotations(cell, right, &rRotations, &rightNeighbor); |
250 | 1.92k | if (rightNeighborError) return rightNeighborError; |
251 | | // Set to owner if lowest index |
252 | 1.91k | if (rightNeighbor < owner) { |
253 | 878 | owner = rightNeighbor; |
254 | 878 | Direction dir = |
255 | 878 | H3_EXPORT(isPentagon)(owner) |
256 | 878 | ? directionForNeighbor(owner, cell) |
257 | 878 | : DIRECTIONS[(revNeighborDirectionsHex[right] + |
258 | 839 | rRotations) % |
259 | 839 | NUM_HEX_VERTS]; |
260 | 878 | ownerVertexNum = vertexNumForDirection(owner, dir); |
261 | 878 | } |
262 | 1.91k | } |
263 | | |
264 | | // Determine the vertex number for the left neighbor |
265 | 2.24k | if (owner == leftNeighbor) { |
266 | 895 | int ownerIsPentagon = H3_EXPORT(isPentagon)(owner); |
267 | 895 | Direction dir = |
268 | 895 | ownerIsPentagon |
269 | 895 | ? directionForNeighbor(owner, cell) |
270 | 895 | : DIRECTIONS[(revNeighborDirectionsHex[left] + lRotations) % |
271 | 853 | NUM_HEX_VERTS]; |
272 | | |
273 | | // For the left neighbor, we need the second vertex of the |
274 | | // edge, which may involve looping around the vertex nums |
275 | 895 | ownerVertexNum = vertexNumForDirection(owner, dir) + 1; |
276 | 895 | if (ownerVertexNum == NUM_HEX_VERTS || |
277 | 895 | (ownerIsPentagon && ownerVertexNum == NUM_PENT_VERTS)) { |
278 | 155 | ownerVertexNum = 0; |
279 | 155 | } |
280 | 895 | } |
281 | 2.24k | } |
282 | | |
283 | | // Create the vertex index |
284 | 2.47k | H3Index vertex = owner; |
285 | 2.47k | H3_SET_MODE(vertex, H3_VERTEX_MODE); |
286 | 2.47k | H3_SET_RESERVED_BITS(vertex, ownerVertexNum); |
287 | 2.47k | *out = vertex; |
288 | | |
289 | 2.47k | return E_SUCCESS; |
290 | 2.59k | } |
291 | | |
292 | | /** |
293 | | * Get all vertexes for the given cell |
294 | | * @param cell Cell to get the vertexes for |
295 | | * @param vertexes Array to hold vertex output. Must have length >= 6. |
296 | | */ |
297 | 483 | H3Error H3_EXPORT(cellToVertexes)(H3Index cell, H3Index *vertexes) { |
298 | | // Get all vertexes. If the cell is a pentagon, will fill the final slot |
299 | | // with H3_NULL. |
300 | 483 | bool isPent = H3_EXPORT(isPentagon)(cell); |
301 | 2.78k | for (int i = 0; i < NUM_HEX_VERTS; i++) { |
302 | 2.41k | if (i == 5 && isPent) { |
303 | 6 | vertexes[i] = H3_NULL; |
304 | 2.40k | } else { |
305 | 2.40k | H3Error cellError = H3_EXPORT(cellToVertex)(cell, i, &vertexes[i]); |
306 | 2.40k | if (cellError) { |
307 | 106 | return cellError; |
308 | 106 | } |
309 | 2.40k | } |
310 | 2.41k | } |
311 | 377 | return E_SUCCESS; |
312 | 483 | } |
313 | | |
314 | | /** |
315 | | * Get the geocoordinates of an H3 vertex |
316 | | * @param vertex H3 index describing a vertex |
317 | | * @param coord Output geo coordinate |
318 | | */ |
319 | 483 | H3Error H3_EXPORT(vertexToLatLng)(H3Index vertex, LatLng *coord) { |
320 | | // Get the vertex number and owner from the vertex |
321 | 483 | int vertexNum = H3_GET_RESERVED_BITS(vertex); |
322 | 483 | H3Index owner = vertex; |
323 | 483 | H3_SET_MODE(owner, H3_CELL_MODE); |
324 | 483 | H3_SET_RESERVED_BITS(owner, 0); |
325 | | |
326 | | // Get the single vertex from the boundary |
327 | 483 | CellBoundary gb; |
328 | 483 | FaceIJK fijk; |
329 | 483 | H3Error fijkError = _h3ToFaceIjk(owner, &fijk); |
330 | 483 | if (fijkError) { |
331 | 10 | return fijkError; |
332 | 10 | } |
333 | 473 | int res = H3_GET_RESOLUTION(owner); |
334 | | |
335 | 473 | if (H3_EXPORT(isPentagon)(owner)) { |
336 | 6 | _faceIjkPentToCellBoundary(&fijk, res, vertexNum, 1, &gb); |
337 | 467 | } else { |
338 | 467 | _faceIjkToCellBoundary(&fijk, res, vertexNum, 1, &gb); |
339 | 467 | } |
340 | | |
341 | | // Copy from boundary to output coord |
342 | 473 | *coord = gb.verts[0]; |
343 | 473 | return E_SUCCESS; |
344 | 483 | } |
345 | | |
346 | | /** |
347 | | * Whether the input is a valid H3 vertex |
348 | | * @param vertex H3 index possibly describing a vertex |
349 | | * @return Whether the input is valid |
350 | | */ |
351 | 483 | int H3_EXPORT(isValidVertex)(H3Index vertex) { |
352 | 483 | if (H3_GET_MODE(vertex) != H3_VERTEX_MODE) { |
353 | 315 | return 0; |
354 | 315 | } |
355 | | |
356 | 168 | int vertexNum = H3_GET_RESERVED_BITS(vertex); |
357 | 168 | H3Index owner = vertex; |
358 | 168 | H3_SET_MODE(owner, H3_CELL_MODE); |
359 | 168 | H3_SET_RESERVED_BITS(owner, 0); |
360 | | |
361 | 168 | if (!H3_EXPORT(isValidCell)(owner)) { |
362 | 79 | return 0; |
363 | 79 | } |
364 | | |
365 | | // The easiest way to ensure that the owner + vertex number is valid, |
366 | | // and that the vertex is canonical, is to recreate and compare. |
367 | 89 | H3Index canonical; |
368 | 89 | if (H3_EXPORT(cellToVertex)(owner, vertexNum, &canonical)) { |
369 | 2 | return 0; |
370 | 2 | } |
371 | | |
372 | 87 | return vertex == canonical ? 1 : 0; |
373 | 89 | } |