1/*
2 * Copyright 2017-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 h3UniEdge.c
17 * @brief H3UniEdge functions for manipulating unidirectional edge indexes.
18 */
19
20#include <inttypes.h>
21#include <stdbool.h>
22#include "algos.h"
23#include "constants.h"
24#include "coordijk.h"
25#include "geoCoord.h"
26#include "h3Index.h"
27
28/**
29 * Returns whether or not the provided H3Indexes are neighbors.
30 * @param origin The origin H3 index.
31 * @param destination The destination H3 index.
32 * @return 1 if the indexes are neighbors, 0 otherwise;
33 */
34int H3_EXPORT(h3IndexesAreNeighbors)(H3Index origin, H3Index destination) {
35 // Make sure they're hexagon indexes
36 if (H3_GET_MODE(origin) != H3_HEXAGON_MODE ||
37 H3_GET_MODE(destination) != H3_HEXAGON_MODE) {
38 return 0;
39 }
40
41 // Hexagons cannot be neighbors with themselves
42 if (origin == destination) {
43 return 0;
44 }
45
46 // Only hexagons in the same resolution can be neighbors
47 if (H3_GET_RESOLUTION(origin) != H3_GET_RESOLUTION(destination)) {
48 return 0;
49 }
50
51 // H3 Indexes that share the same parent are very likely to be neighbors
52 // Child 0 is neighbor with all of its parent's 'offspring', the other
53 // children are neighbors with 3 of the 7 children. So a simple comparison
54 // of origin and destination parents and then a lookup table of the children
55 // is a super-cheap way to possibly determine they are neighbors.
56 int parentRes = H3_GET_RESOLUTION(origin) - 1;
57 if (parentRes > 0 && (H3_EXPORT(h3ToParent)(origin, parentRes) ==
58 H3_EXPORT(h3ToParent)(destination, parentRes))) {
59 Direction originResDigit = H3_GET_INDEX_DIGIT(origin, parentRes + 1);
60 Direction destinationResDigit =
61 H3_GET_INDEX_DIGIT(destination, parentRes + 1);
62 if (originResDigit == CENTER_DIGIT ||
63 destinationResDigit == CENTER_DIGIT) {
64 return 1;
65 }
66 // These sets are the relevant neighbors in the clockwise
67 // and counter-clockwise
68 const Direction neighborSetClockwise[] = {
69 CENTER_DIGIT, JK_AXES_DIGIT, IJ_AXES_DIGIT, J_AXES_DIGIT,
70 IK_AXES_DIGIT, K_AXES_DIGIT, I_AXES_DIGIT};
71 const Direction neighborSetCounterclockwise[] = {
72 CENTER_DIGIT, IK_AXES_DIGIT, JK_AXES_DIGIT, K_AXES_DIGIT,
73 IJ_AXES_DIGIT, I_AXES_DIGIT, J_AXES_DIGIT};
74 if (neighborSetClockwise[originResDigit] == destinationResDigit ||
75 neighborSetCounterclockwise[originResDigit] ==
76 destinationResDigit) {
77 return 1;
78 }
79 }
80
81 // Otherwise, we have to determine the neighbor relationship the "hard" way.
82 H3Index neighborRing[7] = {0};
83 H3_EXPORT(kRing)(origin, 1, neighborRing);
84 for (int i = 0; i < 7; i++) {
85 if (neighborRing[i] == destination) {
86 return 1;
87 }
88 }
89
90 // Made it here, they definitely aren't neighbors
91 return 0;
92}
93
94/**
95 * Returns a unidirectional edge H3 index based on the provided origin and
96 * destination
97 * @param origin The origin H3 hexagon index
98 * @param destination The destination H3 hexagon index
99 * @return The unidirectional edge H3Index, or 0 on failure.
100 */
101H3Index H3_EXPORT(getH3UnidirectionalEdge)(H3Index origin,
102 H3Index destination) {
103 // Short-circuit and return an invalid index value if they are not neighbors
104 if (H3_EXPORT(h3IndexesAreNeighbors)(origin, destination) == 0) {
105 return H3_INVALID_INDEX;
106 }
107
108 // Otherwise, determine the IJK direction from the origin to the destination
109 H3Index output = origin;
110 H3_SET_MODE(output, H3_UNIEDGE_MODE);
111
112 // Checks each neighbor, in order, to determine which direction the
113 // destination neighbor is located. Skips CENTER_DIGIT since that
114 // would be this index.
115 H3Index neighbor;
116 for (Direction direction = K_AXES_DIGIT; direction < NUM_DIGITS;
117 direction++) {
118 int rotations = 0;
119 neighbor = h3NeighborRotations(origin, direction, &rotations);
120 if (neighbor == destination) {
121 H3_SET_RESERVED_BITS(output, direction);
122 return output;
123 }
124 }
125
126 // This should be impossible, return an invalid H3Index in this case;
127 return H3_INVALID_INDEX; // LCOV_EXCL_LINE
128}
129
130/**
131 * Returns the origin hexagon from the unidirectional edge H3Index
132 * @param edge The edge H3 index
133 * @return The origin H3 hexagon index
134 */
135H3Index H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(H3Index edge) {
136 if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
137 return H3_INVALID_INDEX;
138 }
139 H3Index origin = edge;
140 H3_SET_MODE(origin, H3_HEXAGON_MODE);
141 H3_SET_RESERVED_BITS(origin, 0);
142 return origin;
143}
144
145/**
146 * Returns the destination hexagon from the unidirectional edge H3Index
147 * @param edge The edge H3 index
148 * @return The destination H3 hexagon index
149 */
150H3Index H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(H3Index edge) {
151 if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
152 return H3_INVALID_INDEX;
153 }
154 Direction direction = H3_GET_RESERVED_BITS(edge);
155 int rotations = 0;
156 H3Index destination = h3NeighborRotations(
157 H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge), direction,
158 &rotations);
159 return destination;
160}
161
162/**
163 * Determines if the provided H3Index is a valid unidirectional edge index
164 * @param edge The unidirectional edge H3Index
165 * @return 1 if it is a unidirectional edge H3Index, otherwise 0.
166 */
167int H3_EXPORT(h3UnidirectionalEdgeIsValid)(H3Index edge) {
168 if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
169 return 0;
170 }
171
172 Direction neighborDirection = H3_GET_RESERVED_BITS(edge);
173 if (neighborDirection <= CENTER_DIGIT || neighborDirection >= NUM_DIGITS) {
174 return 0;
175 }
176
177 H3Index origin = H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge);
178 if (H3_EXPORT(h3IsPentagon)(origin) && neighborDirection == K_AXES_DIGIT) {
179 return 0;
180 }
181
182 return H3_EXPORT(h3IsValid)(origin);
183}
184
185/**
186 * Returns the origin, destination pair of hexagon IDs for the given edge ID
187 * @param edge The unidirectional edge H3Index
188 * @param originDestination Pointer to memory to store origin and destination
189 * IDs
190 */
191void H3_EXPORT(getH3IndexesFromUnidirectionalEdge)(H3Index edge,
192 H3Index* originDestination) {
193 originDestination[0] =
194 H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge);
195 originDestination[1] =
196 H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(edge);
197}
198
199/**
200 * Provides all of the unidirectional edges from the current H3Index.
201 * @param origin The origin hexagon H3Index to find edges for.
202 * @param edges The memory to store all of the edges inside.
203 */
204void H3_EXPORT(getH3UnidirectionalEdgesFromHexagon)(H3Index origin,
205 H3Index* edges) {
206 // Determine if the origin is a pentagon and special treatment needed.
207 int isPentagon = H3_EXPORT(h3IsPentagon)(origin);
208
209 // This is actually quite simple. Just modify the bits of the origin
210 // slightly for each direction, except the 'k' direction in pentagons,
211 // which is zeroed.
212 for (int i = 0; i < 6; i++) {
213 if (isPentagon && i == 0) {
214 edges[i] = H3_INVALID_INDEX;
215 } else {
216 edges[i] = origin;
217 H3_SET_MODE(edges[i], H3_UNIEDGE_MODE);
218 H3_SET_RESERVED_BITS(edges[i], i + 1);
219 }
220 }
221}
222
223/**
224 * Whether the given coordinate has a matching vertex in the given geo boundary.
225 * @param vertex Coordinate to check
226 * @param boundary Geo boundary to look in
227 * @return Whether a match was found
228 */
229static bool _hasMatchingVertex(const GeoCoord* vertex,
230 const GeoBoundary* boundary) {
231 for (int i = 0; i < boundary->numVerts; i++) {
232 if (geoAlmostEqualThreshold(vertex, &boundary->verts[i], 0.000001)) {
233 return true;
234 }
235 }
236 return false;
237}
238
239/**
240 * Provides the coordinates defining the unidirectional edge.
241 * @param edge The unidirectional edge H3Index
242 * @param gb The geoboundary object to store the edge coordinates.
243 */
244void H3_EXPORT(getH3UnidirectionalEdgeBoundary)(H3Index edge, GeoBoundary* gb) {
245 // TODO: More efficient solution :)
246 GeoBoundary origin = {0};
247 GeoBoundary destination = {0};
248 GeoCoord postponedVertex = {0};
249 bool hasPostponedVertex = false;
250
251 H3_EXPORT(h3ToGeoBoundary)
252 (H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge), &origin);
253 H3_EXPORT(h3ToGeoBoundary)
254 (H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(edge),
255 &destination);
256
257 int k = 0;
258 for (int i = 0; i < origin.numVerts; i++) {
259 if (_hasMatchingVertex(&origin.verts[i], &destination)) {
260 // If we are on vertex 0, we need to handle the case where it's the
261 // end of the edge, not the beginning.
262 if (i == 0 &&
263 !_hasMatchingVertex(&origin.verts[i + 1], &destination)) {
264 postponedVertex = origin.verts[i];
265 hasPostponedVertex = true;
266 } else {
267 gb->verts[k] = origin.verts[i];
268 k++;
269 }
270 }
271 }
272 // If we postponed adding the last vertex, add it now
273 if (hasPostponedVertex) {
274 gb->verts[k] = postponedVertex;
275 k++;
276 }
277 gb->numVerts = k;
278}
279