/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 | } |