/src/h3/src/h3lib/lib/polygon.c
Line | Count | Source |
1 | | /* |
2 | | * Copyright 2018-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 polygon.c |
17 | | * @brief Polygon (GeoLoop) algorithms |
18 | | */ |
19 | | |
20 | | #include "polygon.h" |
21 | | |
22 | | #include <float.h> |
23 | | #include <math.h> |
24 | | #include <stdbool.h> |
25 | | |
26 | | #include "bbox.h" |
27 | | #include "constants.h" |
28 | | #include "h3api.h" |
29 | | #include "latLng.h" |
30 | | #include "linkedGeo.h" |
31 | | |
32 | | // Define macros used in polygon algos for GeoLoop |
33 | | #define TYPE GeoLoop |
34 | 24.6M | #define INIT_ITERATION INIT_ITERATION_GEOFENCE |
35 | 1.01G | #define ITERATE ITERATE_GEOFENCE |
36 | 9.23k | #define IS_EMPTY IS_EMPTY_GEOFENCE |
37 | | |
38 | | #include "polygonAlgos.h" |
39 | | |
40 | | #undef TYPE |
41 | | #undef INIT_ITERATION |
42 | | #undef ITERATE |
43 | | #undef IS_EMPTY |
44 | | |
45 | | /** |
46 | | * Create a bounding box from a GeoPolygon |
47 | | * @param polygon Input GeoPolygon |
48 | | * @param bboxes Output bboxes, one for the outer loop and one for each hole |
49 | | */ |
50 | 908 | void bboxesFromGeoPolygon(const GeoPolygon *polygon, BBox *bboxes) { |
51 | 908 | bboxFromGeoLoop(&polygon->geoloop, &bboxes[0]); |
52 | 7.28k | for (int i = 0; i < polygon->numHoles; i++) { |
53 | 6.37k | bboxFromGeoLoop(&polygon->holes[i], &bboxes[i + 1]); |
54 | 6.37k | } |
55 | 908 | } |
56 | | |
57 | | /** |
58 | | * pointInsidePolygon takes a given GeoPolygon data structure and |
59 | | * checks if it contains a given geo coordinate. |
60 | | * |
61 | | * @param geoPolygon The geoloop and holes defining the relevant area |
62 | | * @param bboxes The bboxes for the main geoloop and each of its holes |
63 | | * @param coord The coordinate to check |
64 | | * @return Whether the point is contained |
65 | | */ |
66 | | bool pointInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, |
67 | 42.5M | const LatLng *coord) { |
68 | | // Start with contains state of primary geoloop |
69 | 42.5M | bool contains = |
70 | 42.5M | pointInsideGeoLoop(&(geoPolygon->geoloop), &bboxes[0], coord); |
71 | | |
72 | | // If the point is contained in the primary geoloop, but there are holes in |
73 | | // the geoloop iterate through all holes and return false if the point is |
74 | | // contained in any hole |
75 | 42.5M | if (contains && geoPolygon->numHoles > 0) { |
76 | 4.26M | for (int i = 0; i < geoPolygon->numHoles; i++) { |
77 | 2.92M | if (pointInsideGeoLoop(&(geoPolygon->holes[i]), &bboxes[i + 1], |
78 | 2.92M | coord)) { |
79 | 468k | return false; |
80 | 468k | } |
81 | 2.92M | } |
82 | 1.80M | } |
83 | | |
84 | 42.1M | return contains; |
85 | 42.5M | } |