10239454666

Committed 04 Aug 2024 09:35PM UTC coverage: 98.761% (-0.07%) from 98.826%

Build # 10239454666

Build Type

Pull #800

github

Committed by

web-flow

Commit Message

Merge e25e8fadc into 25160b947

Pull Request Pull Request #800: Polygon to cells experimental fuzzer

Run Details

1637 of 1673 branches covered (97.85%)

Branch coverage included in aggregate %.

1 of 2 new or added lines in 1 file covered. (50.0%)

1 existing line in 1 file now uncovered.

2826 of 2846 relevant lines covered (99.3%)

35334849.45 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.47

/src/h3lib/include/polygonAlgos.h

/*
 * Copyright 2018, 2020-2021 Uber Technologies, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/** @file
 * @brief Include file for poylgon algorithms. This includes the core
 *        logic for algorithms acting over loops of coordinates,
 *        allowing them to be reused for both GeoLoop and
 *        LinkegGeoLoop structures. This file is intended to be
 *        included inline in a file that defines the type-specific
 *        macros required for iteration.
 */

#include <float.h>
#include <math.h>
#include <stdbool.h>

#include "bbox.h"
#include "constants.h"
#include "h3api.h"
#include "latLng.h"
#include "linkedGeo.h"
#include "polygon.h"

#ifndef TYPE
#error "TYPE must be defined before including this header"
#endif

#ifndef IS_EMPTY
#error "IS_EMPTY must be defined before including this header"
#endif

#ifndef INIT_ITERATION
#error "INIT_ITERATION must be defined before including this header"
#endif

#ifndef ITERATE
#error "ITERATE must be defined before including this header"
#endif

#define LOOP_ALGO_XTJOIN(a, b) a##b
#define LOOP_ALGO_TJOIN(a, b) LOOP_ALGO_XTJOIN(a, b)
#define GENERIC_LOOP_ALGO(func) LOOP_ALGO_TJOIN(func, TYPE)

/** Macro: Normalize longitude, dealing with transmeridian arcs */
#define NORMALIZE_LNG(lng, isTransmeridian) \
    (isTransmeridian && lng < 0 ? lng + (double)M_2PI : lng)

/**
 * pointInside is the core loop of the point-in-poly algorithm
 * @param loop  The loop to check
 * @param bbox  The bbox for the loop being tested
 * @param coord The coordinate to check
 * @return      Whether the point is contained
 */
bool GENERIC_LOOP_ALGO(pointInside)(const TYPE *loop, const BBox *bbox,
                                    const LatLng *coord) {
    // fail fast if we're outside the bounding box
    if (!bboxContains(bbox, coord)) {
        return false;
    }
    bool isTransmeridian = bboxIsTransmeridian(bbox);
    bool contains = false;

    double lat = coord->lat;
    double lng = NORMALIZE_LNG(coord->lng, isTransmeridian);

    LatLng a;
    LatLng b;

    INIT_ITERATION;

    while (true) {
        ITERATE(loop, a, b);

        // Ray casting algo requires the second point to always be higher
        // than the first, so swap if needed
        if (a.lat > b.lat) {
            LatLng tmp = a;
            a = b;
            b = tmp;
        }

        // If the latitude matches exactly, we'll hit an edge case where
        // the ray passes through the vertex twice on successive segment
        // checks. To avoid this, adjust the latiude northward if needed.
        //
        // NOTE: This currently means that a point at the north pole cannot
        // be contained in any polygon. This is acceptable in current usage,
        // because the point we test in this function at present is always
        // a cell center or vertex, and no cell has a center or vertex on the
        // north pole. If we need to expand this algo to more generic uses we
        // might need to handle this edge case.
        if (lat == a.lat || lat == b.lat) {
            lat += DBL_EPSILON;
        }

        // If we're totally above or below the latitude ranges, the test
        // ray cannot intersect the line segment, so let's move on
        if (lat < a.lat || lat > b.lat) {
            continue;
        }

        double aLng = NORMALIZE_LNG(a.lng, isTransmeridian);
        double bLng = NORMALIZE_LNG(b.lng, isTransmeridian);

        // Rays are cast in the longitudinal direction, in case a point
        // exactly matches, to decide tiebreakers, bias westerly
        if (aLng == lng || bLng == lng) {
            lng -= DBL_EPSILON;
        }

        // Illegal input, reject.
        if (fabs(aLng) > M_2PI || fabs(bLng) > M_2PI) {
            return false;
        }

        // For the latitude of the point, compute the longitude of the
        // point that lies on the line segment defined by a and b
        // This is done by computing the percent above a the lat is,
        // and traversing the same percent in the longitudinal direction
        // of a to b
        double ratio = (lat - a.lat) / (b.lat - a.lat);
        double testLng =
            NORMALIZE_LNG(aLng + (bLng - aLng) * ratio, isTransmeridian);

        // Intersection of the ray
        if (testLng > lng) {
            contains = !contains;
        }
    }

    return contains;
}

/**
 * Create a bounding box from a simple polygon loop.
 * Known limitations:
 * - Does not support polygons with two adjacent points > 180 degrees of
 *   longitude apart. These will be interpreted as crossing the antimeridian.
 * - Does not currently support polygons containing a pole.
 * @param loop     Loop of coordinates
 * @param bbox     Output bbox
 */
void GENERIC_LOOP_ALGO(bboxFrom)(const TYPE *loop, BBox *bbox) {
    // Early exit if there are no vertices
    if (IS_EMPTY(loop)) {
        *bbox = (BBox){0};
        return;
    }

    bbox->south = DBL_MAX;
    bbox->west = DBL_MAX;
    bbox->north = -DBL_MAX;
    bbox->east = -DBL_MAX;
    double minPosLng = DBL_MAX;
    double maxNegLng = -DBL_MAX;
    bool isTransmeridian = false;

    double lat;
    double lng;
    LatLng coord;
    LatLng next;

    INIT_ITERATION;

    while (true) {
        ITERATE(loop, coord, next);

        lat = coord.lat;
        lng = coord.lng;
        if (lat < bbox->south) bbox->south = lat;
        if (lng < bbox->west) bbox->west = lng;
        if (lat > bbox->north) bbox->north = lat;
        if (lng > bbox->east) bbox->east = lng;
        // Save the min positive and max negative longitude for
        // use in the transmeridian case
        if (lng > 0 && lng < minPosLng) minPosLng = lng;
        if (lng < 0 && lng > maxNegLng) maxNegLng = lng;
        // check for arcs > 180 degrees longitude, flagging as transmeridian
        if (fabs(lng - next.lng) > M_PI) {
            isTransmeridian = true;
        }
    }
    // Swap east and west if transmeridian
    if (isTransmeridian) {
        bbox->east = maxNegLng;
        bbox->west = minPosLng;
    }
}

/**
 * Whether the winding order of a given loop is clockwise, with normalization
 * for loops crossing the antimeridian.
 * @param loop              The loop to check
 * @param isTransmeridian   Whether the loop crosses the antimeridian
 * @return                  Whether the loop is clockwise
 */
static bool GENERIC_LOOP_ALGO(isClockwiseNormalized)(const TYPE *loop,
                                                     bool isTransmeridian) {
    double sum = 0;
    LatLng a;
    LatLng b;

    INIT_ITERATION;
    while (true) {
        ITERATE(loop, a, b);
        // If we identify a transmeridian arc (> 180 degrees longitude),
        // start over with the transmeridian flag set
        if (!isTransmeridian && fabs(a.lng - b.lng) > M_PI) {
            return GENERIC_LOOP_ALGO(isClockwiseNormalized)(loop, true);
        }
        sum += ((NORMALIZE_LNG(b.lng, isTransmeridian) -
                 NORMALIZE_LNG(a.lng, isTransmeridian)) *
                (b.lat + a.lat));
    }

    return sum > 0;
}

/**
 * Whether the winding order of a given loop is clockwise. In GeoJSON,
 * clockwise loops are always inner loops (holes).
 * @param loop  The loop to check
 * @return      Whether the loop is clockwise
 */
bool GENERIC_LOOP_ALGO(isClockwise)(const TYPE *loop) {
    return GENERIC_LOOP_ALGO(isClockwiseNormalized)(loop, false);
}

1	/*
2	* Copyright 2018, 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
17	* @brief Include file for poylgon algorithms. This includes the core
18	* logic for algorithms acting over loops of coordinates,
19	* allowing them to be reused for both GeoLoop and
20	* LinkegGeoLoop structures. This file is intended to be
21	* included inline in a file that defines the type-specific
22	* macros required for iteration.
23	*/
24
25	#include <float.h>
26	#include <math.h>
27	#include <stdbool.h>
28
29	#include "bbox.h"
30	#include "constants.h"
31	#include "h3api.h"
32	#include "latLng.h"
33	#include "linkedGeo.h"
34	#include "polygon.h"
35
36	#ifndef TYPE
37	#error "TYPE must be defined before including this header"
38	#endif
39
40	#ifndef IS_EMPTY
41	#error "IS_EMPTY must be defined before including this header"
42	#endif
43
44	#ifndef INIT_ITERATION
45	#error "INIT_ITERATION must be defined before including this header"
46	#endif
47
48	#ifndef ITERATE
49	#error "ITERATE must be defined before including this header"
50	#endif
51
52	#define LOOP_ALGO_XTJOIN(a, b) a##b
53	#define LOOP_ALGO_TJOIN(a, b) LOOP_ALGO_XTJOIN(a, b)
54	#define GENERIC_LOOP_ALGO(func) LOOP_ALGO_TJOIN(func, TYPE)
55
56	/** Macro: Normalize longitude, dealing with transmeridian arcs */
57	#define NORMALIZE_LNG(lng, isTransmeridian) \
58	(isTransmeridian && lng < 0 ? lng + (double)M_2PI : lng)
59
60	/**
61	* pointInside is the core loop of the point-in-poly algorithm
62	* @param loop The loop to check
63	* @param bbox The bbox for the loop being tested
64	* @param coord The coordinate to check
65	* @return Whether the point is contained
66	*/
67	bool GENERIC_LOOP_ALGO(pointInside)(const TYPE loop, const BBox bbox,	1,950,148✔
68	const LatLng *coord) {
69	// fail fast if we're outside the bounding box
70	if (!bboxContains(bbox, coord)) {	1,950,148✔
71	return false;	1,368,391✔
72	}
73	bool isTransmeridian = bboxIsTransmeridian(bbox);	581,757✔
74	bool contains = false;	581,757✔
75
76	double lat = coord->lat;	581,757✔
77	double lng = NORMALIZE_LNG(coord->lng, isTransmeridian);	581,757✔
78
79	LatLng a;
80	LatLng b;
81
82	INIT_ITERATION;	581,757✔
83
84	while (true) {	2,920,121✔
85	ITERATE(loop, a, b);	3,501,878✔
86
87	// Ray casting algo requires the second point to always be higher
88	// than the first, so swap if needed
89	if (a.lat > b.lat) {	2,920,121✔
90	LatLng tmp = a;	1,443,213✔
91	a = b;	1,443,213✔
92	b = tmp;	1,443,213✔
93	}
94
95	// If the latitude matches exactly, we'll hit an edge case where
96	// the ray passes through the vertex twice on successive segment
97	// checks. To avoid this, adjust the latiude northward if needed.
98	//
99	// NOTE: This currently means that a point at the north pole cannot
100	// be contained in any polygon. This is acceptable in current usage,
101	// because the point we test in this function at present is always
102	// a cell center or vertex, and no cell has a center or vertex on the
103	// north pole. If we need to expand this algo to more generic uses we
104	// might need to handle this edge case.
105	if (lat == a.lat \|\| lat == b.lat) {	2,920,121✔
106	lat += DBL_EPSILON;	13✔
107	}
108
109	// If we're totally above or below the latitude ranges, the test
110	// ray cannot intersect the line segment, so let's move on
111	if (lat < a.lat \|\| lat > b.lat) {	2,920,121✔
112	continue;	1,756,601✔
113	}
114
115	double aLng = NORMALIZE_LNG(a.lng, isTransmeridian);	1,163,520✔
116	double bLng = NORMALIZE_LNG(b.lng, isTransmeridian);	1,163,520✔
117
118	// Rays are cast in the longitudinal direction, in case a point
119	// exactly matches, to decide tiebreakers, bias westerly
120	if (aLng == lng \|\| bLng == lng) {	1,163,520✔
121	lng -= DBL_EPSILON;	10✔
122	}
123
124	// Illegal input, reject.
125	if (fabs(aLng) > M_2PI \|\| fabs(bLng) > M_2PI) {	1,163,520!
NEW UNCOV 126	return false;	×
127	}
128
129	// For the latitude of the point, compute the longitude of the
130	// point that lies on the line segment defined by a and b
131	// This is done by computing the percent above a the lat is,
132	// and traversing the same percent in the longitudinal direction
133	// of a to b
134	double ratio = (lat - a.lat) / (b.lat - a.lat);	1,163,520✔
135	double testLng =	1,163,520✔
136	NORMALIZE_LNG(aLng + (bLng - aLng) * ratio, isTransmeridian);	1,163,520!
137
138	// Intersection of the ray
139	if (testLng > lng) {	1,163,520✔
140	contains = !contains;	582,120✔
141	}
142	}
143
144	return contains;	581,757✔
145	}
146
147	/**
148	* Create a bounding box from a simple polygon loop.
149	* Known limitations:
150	* - Does not support polygons with two adjacent points > 180 degrees of
151	* longitude apart. These will be interpreted as crossing the antimeridian.
152	* - Does not currently support polygons containing a pole.
153	* @param loop Loop of coordinates
154	* @param bbox Output bbox
155	*/
156	void GENERIC_LOOP_ALGO(bboxFrom)(const TYPE loop, BBox bbox) {	67,679✔
157	// Early exit if there are no vertices
158	if (IS_EMPTY(loop)) {	67,679✔
159	*bbox = (BBox){0};	74✔
160	return;	74✔
161	}
162
163	bbox->south = DBL_MAX;	67,605✔
164	bbox->west = DBL_MAX;	67,605✔
165	bbox->north = -DBL_MAX;	67,605✔
166	bbox->east = -DBL_MAX;	67,605✔
167	double minPosLng = DBL_MAX;	67,605✔
168	double maxNegLng = -DBL_MAX;	67,605✔
169	bool isTransmeridian = false;	67,605✔
170
171	double lat;
172	double lng;
173	LatLng coord;
174	LatLng next;
175
176	INIT_ITERATION;	67,605✔
177
178	while (true) {
179	ITERATE(loop, coord, next);	474,765✔
180
181	lat = coord.lat;	407,160✔
182	lng = coord.lng;	407,160✔
183	if (lat < bbox->south) bbox->south = lat;	407,160✔
184	if (lng < bbox->west) bbox->west = lng;	407,160✔
185	if (lat > bbox->north) bbox->north = lat;	407,160✔
186	if (lng > bbox->east) bbox->east = lng;	407,160✔
187	// Save the min positive and max negative longitude for
188	// use in the transmeridian case
189	if (lng > 0 && lng < minPosLng) minPosLng = lng;	407,160✔
190	if (lng < 0 && lng > maxNegLng) maxNegLng = lng;	407,160✔
191	// check for arcs > 180 degrees longitude, flagging as transmeridian
192	if (fabs(lng - next.lng) > M_PI) {	407,160✔
193	isTransmeridian = true;	66✔
194	}
195	}
196	// Swap east and west if transmeridian
197	if (isTransmeridian) {	67,605✔
198	bbox->east = maxNegLng;	33✔
199	bbox->west = minPosLng;	33✔
200	}
201	}
202
203	/**
204	* Whether the winding order of a given loop is clockwise, with normalization
205	* for loops crossing the antimeridian.
206	* @param loop The loop to check
207	* @param isTransmeridian Whether the loop crosses the antimeridian
208	* @return Whether the loop is clockwise
209	*/
210	static bool GENERIC_LOOP_ALGO(isClockwiseNormalized)(const TYPE *loop,	49✔
211	bool isTransmeridian) {
212	double sum = 0;	49✔
213	LatLng a;
214	LatLng b;
215
216	INIT_ITERATION;	49✔
217	while (true) {
218	ITERATE(loop, a, b);	422✔
219	// If we identify a transmeridian arc (> 180 degrees longitude),
220	// start over with the transmeridian flag set
221	if (!isTransmeridian && fabs(a.lng - b.lng) > M_PI) {	381✔
222	return GENERIC_LOOP_ALGO(isClockwiseNormalized)(loop, true);	8✔
223	}
224	sum += ((NORMALIZE_LNG(b.lng, isTransmeridian) -	373✔
225	NORMALIZE_LNG(a.lng, isTransmeridian)) *	373✔
226	(b.lat + a.lat));	373✔
227	}
228
229	return sum > 0;	41✔
230	}
231
232	/**
233	* Whether the winding order of a given loop is clockwise. In GeoJSON,
234	* clockwise loops are always inner loops (holes).
235	* @param loop The loop to check
236	* @return Whether the loop is clockwise
237	*/
238	bool GENERIC_LOOP_ALGO(isClockwise)(const TYPE *loop) {	41✔
239	return GENERIC_LOOP_ALGO(isClockwiseNormalized)(loop, false);	41✔
240	}

uber / h3 / 10239454666

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous