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