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 linkedGeo.c
17 * @brief Linked data structure for geo data
18 */
19
20#include "linkedGeo.h"
21#include <assert.h>
22#include <stdlib.h>
23#include "geoCoord.h"
24#include "h3api.h"
25
26/**
27 * Add a linked polygon to the current polygon
28 * @param polygon Polygon to add link to
29 * @return Pointer to new polygon
30 */
31LinkedGeoPolygon* addNewLinkedPolygon(LinkedGeoPolygon* polygon) {
32 assert(polygon->next == NULL);
33 LinkedGeoPolygon* next = calloc(1, sizeof(*next));
34 assert(next != NULL);
35 polygon->next = next;
36 return next;
37}
38
39/**
40 * Add a new linked loop to the current polygon
41 * @param polygon Polygon to add loop to
42 * @return Pointer to loop
43 */
44LinkedGeoLoop* addNewLinkedLoop(LinkedGeoPolygon* polygon) {
45 LinkedGeoLoop* loop = calloc(1, sizeof(*loop));
46 assert(loop != NULL);
47 return addLinkedLoop(polygon, loop);
48}
49
50/**
51 * Add an existing linked loop to the current polygon
52 * @param polygon Polygon to add loop to
53 * @return Pointer to loop
54 */
55LinkedGeoLoop* addLinkedLoop(LinkedGeoPolygon* polygon, LinkedGeoLoop* loop) {
56 LinkedGeoLoop* last = polygon->last;
57 if (last == NULL) {
58 assert(polygon->first == NULL);
59 polygon->first = loop;
60 } else {
61 last->next = loop;
62 }
63 polygon->last = loop;
64 return loop;
65}
66
67/**
68 * Add a new linked coordinate to the current loop
69 * @param loop Loop to add coordinate to
70 * @param vertex Coordinate to add
71 * @return Pointer to the coordinate
72 */
73LinkedGeoCoord* addLinkedCoord(LinkedGeoLoop* loop, const GeoCoord* vertex) {
74 LinkedGeoCoord* coord = malloc(sizeof(*coord));
75 assert(coord != NULL);
76 *coord = (LinkedGeoCoord){.vertex = *vertex, .next = NULL};
77 LinkedGeoCoord* last = loop->last;
78 if (last == NULL) {
79 assert(loop->first == NULL);
80 loop->first = coord;
81 } else {
82 last->next = coord;
83 }
84 loop->last = coord;
85 return coord;
86}
87
88/**
89 * Free all allocated memory for a linked geo loop. The caller is
90 * responsible for freeing memory allocated to input loop struct.
91 * @param loop Loop to free
92 */
93void destroyLinkedGeoLoop(LinkedGeoLoop* loop) {
94 LinkedGeoCoord* nextCoord;
95 for (LinkedGeoCoord* currentCoord = loop->first; currentCoord != NULL;
96 currentCoord = nextCoord) {
97 nextCoord = currentCoord->next;
98 free(currentCoord);
99 }
100}
101
102/**
103 * Free all allocated memory for a linked geo structure. The caller is
104 * responsible for freeing memory allocated to input polygon struct.
105 * @param polygon Pointer to the first polygon in the structure
106 */
107void H3_EXPORT(destroyLinkedPolygon)(LinkedGeoPolygon* polygon) {
108 // flag to skip the input polygon
109 bool skip = true;
110 LinkedGeoPolygon* nextPolygon;
111 LinkedGeoLoop* nextLoop;
112 for (LinkedGeoPolygon* currentPolygon = polygon; currentPolygon != NULL;
113 currentPolygon = nextPolygon) {
114 for (LinkedGeoLoop* currentLoop = currentPolygon->first;
115 currentLoop != NULL; currentLoop = nextLoop) {
116 destroyLinkedGeoLoop(currentLoop);
117 nextLoop = currentLoop->next;
118 free(currentLoop);
119 }
120 nextPolygon = currentPolygon->next;
121 if (skip) {
122 // do not free the input polygon
123 skip = false;
124 } else {
125 free(currentPolygon);
126 }
127 }
128}
129
130/**
131 * Count the number of polygons in a linked list
132 * @param polygon Starting polygon
133 * @return Count
134 */
135int countLinkedPolygons(LinkedGeoPolygon* polygon) {
136 int count = 0;
137 while (polygon != NULL) {
138 count++;
139 polygon = polygon->next;
140 }
141 return count;
142}
143
144/**
145 * Count the number of linked loops in a polygon
146 * @param polygon Polygon to count loops for
147 * @return Count
148 */
149int countLinkedLoops(LinkedGeoPolygon* polygon) {
150 LinkedGeoLoop* loop = polygon->first;
151 int count = 0;
152 while (loop != NULL) {
153 count++;
154 loop = loop->next;
155 }
156 return count;
157}
158
159/**
160 * Count the number of coordinates in a loop
161 * @param loop Loop to count coordinates for
162 * @return Count
163 */
164int countLinkedCoords(LinkedGeoLoop* loop) {
165 LinkedGeoCoord* coord = loop->first;
166 int count = 0;
167 while (coord != NULL) {
168 count++;
169 coord = coord->next;
170 }
171 return count;
172}
173
174/**
175 * Count the number of polygons containing a given loop.
176 * @param loop Loop to count containers for
177 * @param polygons Polygons to test
178 * @param bboxes Bounding boxes for polygons, used in point-in-poly check
179 * @param polygonCount Number of polygons in the test array
180 * @return Number of polygons containing the loop
181 */
182static int countContainers(const LinkedGeoLoop* loop,
183 const LinkedGeoPolygon** polygons,
184 const BBox** bboxes, const int polygonCount) {
185 int containerCount = 0;
186 for (int i = 0; i < polygonCount; i++) {
187 if (loop != polygons[i]->first &&
188 pointInsideLinkedGeoLoop(polygons[i]->first, bboxes[i],
189 &loop->first->vertex)) {
190 containerCount++;
191 }
192 }
193 return containerCount;
194}
195
196/**
197 * Given a list of nested containers, find the one most deeply nested.
198 * @param polygons Polygon containers to check
199 * @param bboxes Bounding boxes for polygons, used in point-in-poly check
200 * @param polygonCount Number of polygons in the list
201 * @return Deepest container, or null if list is empty
202 */
203static const LinkedGeoPolygon* findDeepestContainer(
204 const LinkedGeoPolygon** polygons, const BBox** bboxes,
205 const int polygonCount) {
206 // Set the initial return value to the first candidate
207 const LinkedGeoPolygon* parent = polygonCount > 0 ? polygons[0] : NULL;
208
209 // If we have multiple polygons, they must be nested inside each other.
210 // Find the innermost polygon by taking the one with the most containers
211 // in the list.
212 if (polygonCount > 1) {
213 int max = -1;
214 for (int i = 0; i < polygonCount; i++) {
215 int count = countContainers(polygons[i]->first, polygons, bboxes,
216 polygonCount);
217 if (count > max) {
218 parent = polygons[i];
219 max = count;
220 }
221 }
222 }
223
224 return parent;
225}
226
227/**
228 * Find the polygon to which a given hole should be allocated. Note that this
229 * function will return null if no parent is found.
230 * @param loop Inner loop describing a hole
231 * @param polygon Head of a linked list of polygons to check
232 * @param bboxes Bounding boxes for polygons, used in point-in-poly check
233 * @param polygonCount Number of polygons to check
234 * @return Pointer to parent polygon, or null if not found
235 */
236static const LinkedGeoPolygon* findPolygonForHole(
237 const LinkedGeoLoop* loop, const LinkedGeoPolygon* polygon,
238 const BBox* bboxes, const int polygonCount) {
239 // Early exit with no polygons
240 if (polygonCount == 0) {
241 return NULL;
242 }
243 // Initialize arrays for candidate loops and their bounding boxes
244 const LinkedGeoPolygon** candidates =
245 malloc(polygonCount * sizeof(LinkedGeoPolygon*));
246 assert(candidates != NULL);
247 const BBox** candidateBBoxes = malloc(polygonCount * sizeof(BBox*));
248 assert(candidateBBoxes != NULL);
249
250 // Find all polygons that contain the loop
251 int candidateCount = 0;
252 int index = 0;
253 while (polygon) {
254 // We are guaranteed not to overlap, so just test the first point
255 if (pointInsideLinkedGeoLoop(polygon->first, &bboxes[index],
256 &loop->first->vertex)) {
257 candidates[candidateCount] = polygon;
258 candidateBBoxes[candidateCount] = &bboxes[index];
259 candidateCount++;
260 }
261 polygon = polygon->next;
262 index++;
263 }
264
265 // The most deeply nested container is the immediate parent
266 const LinkedGeoPolygon* parent =
267 findDeepestContainer(candidates, candidateBBoxes, candidateCount);
268
269 // Free allocated memory
270 free(candidates);
271 free(candidateBBoxes);
272
273 return parent;
274}
275
276/**
277 * Normalize a LinkedGeoPolygon in-place into a structure following GeoJSON
278 * MultiPolygon rules: Each polygon must have exactly one outer loop, which
279 * must be first in the list, followed by any holes. Holes in this algorithm
280 * are identified by winding order (holes are clockwise), which is guaranteed
281 * by the h3SetToVertexGraph algorithm.
282 *
283 * Input to this function is assumed to be a single polygon including all
284 * loops to normalize. It's assumed that a valid arrangement is possible.
285 *
286 * @param root Root polygon including all loops
287 * @return 0 on success, or an error code > 0 for invalid input
288 */
289int normalizeMultiPolygon(LinkedGeoPolygon* root) {
290 // We assume that the input is a single polygon with loops;
291 // if it has multiple polygons, don't touch it
292 if (root->next) {
293 return NORMALIZATION_ERR_MULTIPLE_POLYGONS;
294 }
295
296 // Count loops, exiting early if there's only one
297 int loopCount = countLinkedLoops(root);
298 if (loopCount <= 1) {
299 return NORMALIZATION_SUCCESS;
300 }
301
302 int resultCode = NORMALIZATION_SUCCESS;
303 LinkedGeoPolygon* polygon = NULL;
304 LinkedGeoLoop* next;
305 int innerCount = 0;
306 int outerCount = 0;
307
308 // Create an array to hold all of the inner loops. Note that
309 // this array will never be full, as there will always be fewer
310 // inner loops than outer loops.
311 LinkedGeoLoop** innerLoops = malloc(loopCount * sizeof(LinkedGeoLoop*));
312 assert(innerLoops != NULL);
313
314 // Create an array to hold the bounding boxes for the outer loops
315 BBox* bboxes = malloc(loopCount * sizeof(BBox));
316 assert(bboxes != NULL);
317
318 // Get the first loop and unlink it from root
319 LinkedGeoLoop* loop = root->first;
320 *root = (LinkedGeoPolygon){0};
321
322 // Iterate over all loops, moving inner loops into an array and
323 // assigning outer loops to new polygons
324 while (loop) {
325 if (isClockwiseLinkedGeoLoop(loop)) {
326 innerLoops[innerCount] = loop;
327 innerCount++;
328 } else {
329 polygon = polygon == NULL ? root : addNewLinkedPolygon(polygon);
330 addLinkedLoop(polygon, loop);
331 bboxFromLinkedGeoLoop(loop, &bboxes[outerCount]);
332 outerCount++;
333 }
334 // get the next loop and unlink it from this one
335 next = loop->next;
336 loop->next = NULL;
337 loop = next;
338 }
339
340 // Find polygon for each inner loop and assign the hole to it
341 for (int i = 0; i < innerCount; i++) {
342 polygon = (LinkedGeoPolygon*)findPolygonForHole(innerLoops[i], root,
343 bboxes, outerCount);
344 if (polygon) {
345 addLinkedLoop(polygon, innerLoops[i]);
346 } else {
347 // If we can't find a polygon (possible with invalid input), then
348 // we need to release the memory for the hole, because the loop has
349 // been unlinked from the root and the caller will no longer have
350 // a way to destroy it with destroyLinkedPolygon.
351 destroyLinkedGeoLoop(innerLoops[i]);
352 free(innerLoops[i]);
353 resultCode = NORMALIZATION_ERR_UNASSIGNED_HOLES;
354 }
355 }
356
357 // Free allocated memory
358 free(innerLoops);
359 free(bboxes);
360
361 return resultCode;
362}
363
364// Define macros used in polygon algos for LinkedGeoLoop
365#define TYPE LinkedGeoLoop
366#define INIT_ITERATION INIT_ITERATION_LINKED_LOOP
367#define ITERATE ITERATE_LINKED_LOOP
368#define IS_EMPTY IS_EMPTY_LINKED_LOOP
369
370#include "polygonAlgos.h"
371
372#undef TYPE
373#undef IS_EMPTY
374#undef INIT_ITERATION
375#undef ITERATE
376